fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define ll long long
  5. #define all(a) (a).begin(), (a).end()
  6. #define rall(a) (a).rbegin(), (a).rend()
  7. #define el '\n'
  8. #define sz(a) (int)(a).size()
  9. #define pi acos(-1)
  10. // #define int ll
  11.  
  12. #ifdef LOCAL
  13. #include "debug.hpp"
  14. #else
  15. #define debug(...) 0
  16. #define debug_itr(...) 0
  17. #define debug_bits(...) 0
  18. #endif
  19.  
  20. const ll mod = 998244353, N = 1e5 + 2;
  21.  
  22. void solve() {
  23.   int n;
  24.   cin >> n;
  25.   int mx = -1;
  26.   vector<int> a(n);
  27.   for (int &i : a)
  28.     cin >> i, mx = max(mx, i);
  29.   int N = 1e6;
  30.  
  31.   vector<int> f(mx + 3);
  32.   int mxx = 0;
  33.   for (int &i : a) {
  34.     f[i]++;
  35.   }
  36.   int l = 0, r = mx;
  37.   while (l < r) {
  38.     if (!f[l]) {
  39.       if (l > (r + 1) / 2 - 1)
  40.         break;
  41.       f[l] = 1, f[r]--;
  42.     }
  43.     while (!f[r] && r > l)
  44.       r--;
  45.     l++;
  46.   }
  47.   debug(f);
  48.   for (int i = 0; i <= mx + 1; ++i)
  49.     if (!f[i]) {
  50.       cout << i << el;
  51.       break;
  52.     }
  53. }
  54.  
  55. int32_t main() {
  56.   cin.tie(0)->sync_with_stdio(0);
  57.   int t = 1;
  58.   cin >> t;
  59.   while (t--)
  60.     solve();
  61. #ifdef LOCAL
  62.   debug((float)clock() / CLOCKS_PER_SEC);
  63. #endif
  64.   return 0;
  65. }
  66.  
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1
https://ideone.com/RookP9
language:
C++14 (gcc 8.3)
created:
1 day 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!