fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define read(type) readInt<type>() // Fast read
  4. #define ll long long
  5. #define nL "\n"
  6. #define pb push_back
  7. #define mk make_pair
  8. #define pii pair<int, int>
  9. #define a first
  10. #define b second
  11. #define vi vector<int>
  12. #define all(x) (x).begin(), (x).end()
  13. #define umap unordered_map
  14. #define uset unordered_set
  15. #define MOD 1000000007
  16. #define imax INT_MAX
  17. #define imin INT_MIN
  18. #define exp 1e9
  19. #define sz(x) (int((x).size()))
  20.  
  21.  
  22. void solve() {
  23.     int n; cin >> n;
  24.     map<ll,ll> d; 
  25.  
  26.     for(auto i = 0; i < n; i++) {
  27.         ll o; cin >> o;
  28.         if (d.find(o) != d.end()) {
  29.             d[o]++;
  30.         } else {d[o] = 1;}
  31.     }
  32.  
  33.     int ans = 1;
  34.     cout << "Entering" << endl;
  35.  
  36.  
  37.     pair<ll,ll> cur = *d.begin();
  38.     d[cur.a]--;
  39.     if (d[cur.a] <= 0) {d.erase(cur.a);}
  40.  
  41.     while((int)d.size() != 0) {
  42.         cout << "handling: " << cur.a << endl;
  43.         if (d.find(cur.a+1) != d.end()) {
  44.             cout << "Found " << cur.a+1 << endl;
  45.  
  46.             d[cur.a+1]--;
  47.  
  48.             if (d[cur.a+1] <= 0) {d.erase(cur.a+1);}
  49.  
  50.             cout << "CUR A: " << cur.a << endl;
  51.             cur = *d.find(cur.a+1);
  52.  
  53.  
  54.  
  55.         } else {
  56.             cout << "Not found " << cur.a+1 << endl;
  57.             ans++;
  58.             d[cur.a]--;
  59.             if (d[cur.a] <= 0) {d.erase(cur.a);}
  60.             cur = *d.begin();
  61.  
  62.         }
  63.     }
  64.  
  65.     cout << ans << endl;
  66.  
  67. }
  68.  
  69.  
  70.  
  71. int32_t main()
  72. {
  73.     ios_base::sync_with_stdio(false);
  74.     cin.tie(NULL);
  75.     int t; cin >> t;
  76.     while (t--) {
  77.         solve();
  78.     }
  79.     return 0;
  80. }
Success #stdin #stdout 0.01s 5316KB
comments (?)
stdin
copy 
10
6
2 2 3 4 3 1
5
11 8 7 10 9
6
1000000000 1000000000 1000000000 1000000000 1000000000 1000000000
8
1 1 4 4 2 3 2 3
6
1 2 3 2 3 4
7
10 11 11 12 12 13 13
7
8 8 9 9 10 10 11
8
4 14 5 15 6 16 7 17
8
5 15 6 14 8 12 9 11
5
4 2 2 3 4
stdout
copy 
Entering
handling: 1
Found 2
CUR A: 1
handling: 2
Found 3
CUR A: 2
handling: 3
Found 4
CUR A: 3
handling: 2
Found 3
CUR A: 2
handling: 1
Found 2
CUR A: 1
1
Entering
handling: 7
Found 8
CUR A: 7
handling: 3
Not found 4
handling: 9
Found 10
CUR A: 9
handling: 2
Not found 3
handling: 9
Not found 10
handling: 11
Not found 12
5
Entering
handling: 1000000000
Not found 1000000001
handling: 1000000000
Not found 1000000001
handling: 1000000000
Not found 1000000001
handling: 1000000000
Not found 1000000001
handling: 1000000000
Not found 1000000001
6
Entering
handling: 1
Found 2
CUR A: 1
handling: 2
Found 3
CUR A: 2
handling: 3
Found 4
CUR A: 3
handling: 4
Not found 5
handling: 1
Found 2
CUR A: 1
handling: 2
Found 3
CUR A: 2
handling: 1
Not found 2
3
Entering
handling: 1
Found 2
CUR A: 1
handling: 2
Found 3
CUR A: 2
handling: 3
Found 4
CUR A: 3
handling: 2
Found 3
CUR A: 2
handling: 1
Found 2
CUR A: 1
1
Entering
handling: 10
Found 11
CUR A: 10
handling: 11
Found 12
CUR A: 11
handling: 12
Found 13
CUR A: 12
handling: 13
Not found 14
handling: 11
Found 12
CUR A: 11
handling: 1
Not found 2
handling: 11
Not found 12
4
Entering
handling: 8
Found 9
CUR A: 8
handling: 9
Found 10
CUR A: 9
handling: 10
Found 11
CUR A: 10
handling: 3
Not found 4
handling: 8
Found 9
CUR A: 8
handling: 2
Not found 3
handling: 8
Not found 9
handling: 10
Not found 11
5
Entering
handling: 4
Found 5
CUR A: 4
handling: 6
Found 7
CUR A: 6
handling: 5
Found 6
CUR A: 5
handling: 4
Not found 5
handling: 14
Found 15
CUR A: 14
handling: 3
Not found 4
handling: 14
Not found 15
handling: 16
Found 17
CUR A: 16
handling: 1
Not found 2
handling: 16
Not found 17
6
Entering
handling: 5
Found 6
CUR A: 5
handling: 6
Not found 7
handling: 8
Found 9
CUR A: 8
handling: 5
Not found 6
handling: 8
Not found 9
handling: 11
Found 12
CUR A: 11
handling: 3
Not found 4
handling: 11
Not found 12
handling: 14
Found 15
CUR A: 14
handling: 1
Not found 2
handling: 14
Not found 15
8
Entering
handling: 2
Found 3
CUR A: 2
handling: 2
Not found 3
handling: 4
Not found 5
handling: 4
Not found 5
4
https://ideone.com/dgA3B3
language:
C++14 (gcc 8.3)
created:
1 year 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!