fork download 
  1. #include <bits/stdc++.h>
  2. #include <algorithm>
  3. using namespace std;
  4.  
  5. #include <ext/pb_ds/assoc_container.hpp>
  6. #include <ext/pb_ds/tree_policy.hpp>
  7. #define deb(...) logger(#__VA_ARGS__, __VA_ARGS__)
  8.  
  9. template<typename... Args>
  10. void logger(string vars, Args &&... values) {
  11.     cout << vars << " = ";
  12.     string delim = "";
  13.     (..., (cout << delim << values, delim = ", "));
  14.     cout << '\n';
  15. }
  16.  
  17. using namespace __gnu_pbds;
  18. template<typename T>
  19. using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
  20. #define int long long
  21. #define ll long long
  22. #define ull unsigned long long
  23. #define ld long double
  24. #define yes cout << "YES"<<'\n';
  25. #define no cout << "NO"<<'\n';
  26. #define nl "\n"
  27. #define sz(s) (int) (s).size()
  28. #define fr(n) for (int i = 0; i < n; ++i)
  29. #define aw3dni_ink_tet3aleg ios_base::sync_with_stdio(false), cout.tie(NULL), cin.tie(NULL);
  30. const double PI = 3.14159265358979323846264338327950288419716939937510L;;
  31. #define sp(x) fixed << setprecision(x)
  32. #define all(v) v.begin(), v.end()
  33. #define ff first
  34. #define ss second
  35. #define pii pair<ll,ll>
  36. #define put(x) return void(cout << x)
  37. #define all(v) v.begin(), v.end()
  38. #define allr(v) v.rbegin(), v.rend()
  39. #define cin(vec)                                                                                                       \
  40.     for (auto &i: vec)                                                                                                 \
  41.     cin >> i
  42. #define cout(vec)                                                                                                      \
  43.     for (auto &i: vec)                                                                                                 \
  44.         cout << i << " ";                                                                                              \
  45.     cout << "\n";
  46. #define ON(n, k) ((n) | (1ll << (k)))
  47. #define OFF(n, k) ((n) & ~(1ll << (k)))
  48. #define isON(n, k) (((n) >> (k)) & 1)
  49. #define flip(n, k) ((n) ^ (1ll << (k)))
  50. #define popcnt(x) (__builtin_popcountll(x))
  51.  
  52. template<typename T = int>
  53. istream &operator>>(istream &in, vector<T> &v) {
  54.     for (auto &x: v)in >> x;
  55.     return in;
  56. }
  57.  
  58. template<typename T = int>
  59. ostream &operator<<(ostream &out, const vector<T> &v) {
  60.     for (const T &x: v)out << x << ' ';
  61.     return out;
  62. }
  63.  
  64. void FILES() {
  65.     aw3dni_ink_tet3aleg
  66. #ifndef ONLINE_JUDGE
  67.     freopen("input.txt", "r", stdin);
  68.     freopen("output.txt", "w", stdout);
  69. #endif
  70.     // freopen("angle3.in", "r", stdin);
  71.     // freopen("angle3.out", "w", stdout);
  72. }
  73.  
  74. #define ceil_i(a, b) (((ll) (a) + (ll) (b - 1)) / (ll) (b))
  75. #define floor_i(a, b) (a / b)
  76. #define round_i(a, b) ((a + (b / 2)) / b)
  77.  
  78. ll OO = 0x3f3f3f3f3f3f3f3f, MOD = 1e9 + 7; //1e9 + 7 ,,998244353
  79. //
  80. // int add(int a, int b) { return ((a % MOD) + (b % MOD) + MOD) % MOD; }
  81.  
  82. // int mul(int a, int b) { return (((a % MOD) * (b % MOD))) % MOD; }
  83. // int add(int a, int b) {
  84. //     if (a < 0)
  85. //         a += MOD;
  86. //     if (a >= MOD)
  87. //         a -= MOD;
  88. //     if (b < 0)
  89. //         b += MOD;
  90. //     if (b >= MOD)
  91. //         b -= MOD;
  92. //     if (a + b >= MOD)
  93. //         return a + b - MOD;
  94. //     return a + b;
  95. // }
  96.  
  97. int add(int a, int b) {
  98.     return (0ll + a + b + MOD) % MOD;
  99. }
  100.  
  101. int sub(int a, int b) {
  102.     return add(a, -b);
  103. }
  104.  
  105. int mul(int a, int b) {
  106.     return (1ll * a * b) % MOD;
  107. }
  108.  
  109. // int sub(int a, int b) { return (((a % MOD) - (b % MOD)) + MOD) % MOD; }
  110.  
  111.  
  112. #define INF 1e18
  113.  
  114. int dx[] = {1, -1, 0, 0, -1, -1, 1, 1};
  115. int dy[] = {0, 0, -1, 1, -1, 1, -1, 1};
  116. int dx_knight[8] = {2, 1, -1, -2, -2, -1, 1, 2};
  117. int dy_knight[8] = {1, 2, 2, 1, -1, -2, -2, -1};
  118. char di[] = {'D', 'L', 'U', 'R'};
  119. // up right down left
  120.  
  121. const int N = 4e5 + 10, XX = 101, EPS = 1e-12;
  122.  
  123. // وَقُلْ رَبِّ زِدْنِي عِلْمًا
  124. struct SegmentTree {
  125. private:
  126. #define L 2*node+1
  127. #define R 2*node+2
  128. #define mid (l+r)/2
  129.  
  130.     vector<int> seg;
  131.     int size;
  132.     int merge(int a,int b) {
  133.         return max(a, b);
  134.     }
  135.  
  136.     void build(int l, int r,int node, vector<int> &v) {
  137.         if (l == r) {
  138.             seg[node] = 0;
  139.             return;
  140.         }
  141.         build(l,mid,L, v);
  142.         build(mid + 1, r,R, v);
  143.         seg[node] = merge(seg[L], seg[R]);
  144.     }
  145.  
  146.     int query(int l, int r, int node,int lq, int rq) {
  147.         if (lq <= l && r <= rq) return seg[node];
  148.         if (l > rq || r < lq)
  149.             return 0;
  150.         int lft = query(l,mid,L, lq, rq);
  151.         int rgt = query(mid + 1, r,R, lq, rq);
  152.         return merge(lft, rgt);
  153.     }
  154.  
  155.     void update(int l, int r, int node, int idx,int val) {
  156.         if (l == r) {
  157.             seg[node] = val;
  158.             return;
  159.         }
  160.         if (idx <= mid) update(l, mid, L, idx, val);
  161.         else update(mid + 1, r, R, idx, val);
  162.         seg[node] = merge(seg[L], seg[R]);
  163.     }
  164.  
  165. public:
  166.     SegmentTree(int n) {
  167.         size = 1;
  168.         while (size < n) size <<= 1;
  169.         seg = vector<int>(size * 2, 0);
  170.     }
  171.  
  172.     int query(int l, int r) {
  173.         return query(0, size - 1, 0, l, r);
  174.     }
  175.  
  176.     void update(int idx,int val) {
  177.         update(0, size - 1, 0, idx, val);
  178.     }
  179. #undef L
  180. #undef R
  181. #undef mid
  182. };
  183.  
  184. void solve() {
  185.     int n, k;
  186.     cin >> n >> k;
  187.     vector<int> v(n);
  188.     map<ll,ll> frq, frq2;
  189.     ll mex = 0;
  190.     for (int i = 0; i < n; i++)
  191.         cin >> v[i], frq[v[i]]++;
  192.     for (auto it: frq) {
  193.         if (it.ff != mex) {
  194.             break;
  195.         }
  196.         mex++;
  197.     }
  198.     vector<ll> neww(n);
  199.     for (int i = 0; i < n; i++) {
  200.         if (frq[v[i]] > 1) {
  201.             neww[i] = mex;
  202.         } else if (v[i] > mex) {
  203.             neww[i] = mex;
  204.         } else {
  205.             neww[i] = v[i];
  206.         }
  207.         frq2[neww[i]]++;
  208.     }
  209.     ll mex2 = 0;
  210.     for (auto it: frq2) {
  211.         if (it.ff != mex2) {
  212.             break;
  213.         }
  214.         mex2++;
  215.     }
  216.     // cout << mex2 << nl;
  217.     vector<ll> neww2(n);
  218.     for (int i = 0; i < n; i++) {
  219.         if (frq2[neww[i]] > 1) {
  220.             neww2[i] = mex2;
  221.         } else if (neww[i] > mex2) {
  222.             neww2[i] = mex2;
  223.         } else {
  224.             neww2[i] = neww[i];
  225.         }
  226.     }
  227.     // cout <<neww<<nl;
  228.     if (k == 1) {
  229.         ll sum = accumulate(all(neww), 0ll);
  230.         cout << sum;
  231.     } else if (k==2) {
  232.         ll sum = accumulate(all(neww2), 0ll);
  233.         cout << sum;
  234.     }
  235.     else {
  236.         if (mex2 == 0 ) {
  237.             if (k&1) {
  238.                 cout << n;
  239.             }
  240.             else {
  241.                 cout << 0 ;
  242.             }
  243.         }
  244.         else {
  245.             if (k&1) {
  246.                 ll sum = accumulate(all(neww), 0ll);
  247.                 cout << sum;
  248.             }
  249.             else {
  250.                 ll sum = accumulate(all(neww2), 0ll);
  251.                 cout << sum;
  252.             }
  253.         }
  254.     }
  255. }
  256.  
  257.  
  258. signed main() {
  259.     //=========================================================================
  260.     FILES();
  261.     //=========================================================================
  262.     int T = 1, t = 1;
  263.     // phi_1_to_n();
  264.     // linear_sieve(1e6);
  265.     // pre_count();
  266.     // sieve();
  267.     // PascalPyramid();
  268.     // computeCatalan();
  269.     // preprocess(50);
  270.     // totient_sieve();
  271.     // build_spf(2000000);
  272.     cin >> T;
  273.     while (T--) {
  274.         solve();
  275.         t++;
  276.         // vid++;
  277.         cout << nl;
  278.     }
  279.     return 0;
  280. }
  281.  
Success #stdin #stdout 0s 5316KB
comments (?)
stdin 
Standard input is empty
stdout 
0
https://ideone.com/TDkBuH
language:
C++ (gcc 8.3)
created:
2 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!