1. #include <bits/stdc++.h>
2. using namespace std;
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. cur = *d.find(cur.a+1);
48. if (d[cur.a+1] <= 0) {d.erase(cur.a+1);}
49.
50.
51.
52. } else {
54. ans++;
55. d[cur.a]--;
56. if (d[cur.a] <= 0) {d.erase(cur.a);}
57. cur = *d.begin();
58.
59. }
60. }
61.
62. cout << ans << endl;
63.
64. }
65.
66.
67.
68. int32_t main()
69. {
70. ios_base::sync_with_stdio(false);
71. cin.tie(NULL);
72. int t; cin >> t;
73. while (t--) {
74. solve();
75. }
76. return 0;
77. }
Success #stdin #stdout 0.01s 5516KB
stdin
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
Entering
handling: 1
Found 2
handling: 2
Found 3
handling: 3
Found 4
handling: 4
handling: 2
Found 3
handling: 3
handling: 2
4
Entering
handling: 7
Found 8
handling: 8
Found 9
handling: 9
Found 10
handling: 10
Found 11
handling: 11
handling: 8
Found 9
handling: 9
handling: 8
4
Entering
handling: 1000000000
handling: 1000000000
handling: 1000000000
handling: 1000000000
handling: 1000000000
6
Entering
handling: 1
Found 2
handling: 2
Found 3
handling: 3
Found 4
handling: 4
handling: 1
Found 2
handling: 2
Found 3
handling: 3
handling: 1
Found 2
handling: 2
handling: 1
5
Entering
handling: 1
Found 2
handling: 2
Found 3
handling: 3
Found 4
handling: 4
handling: 2
Found 3
handling: 3
handling: 2
4
Entering
handling: 10
Found 11
handling: 11
Found 12
handling: 12
Found 13
handling: 13
handling: 11
Found 12
handling: 12
handling: 11
4
Entering
handling: 8
Found 9
handling: 9
Found 10
handling: 10
Found 11
handling: 11
handling: 8
Found 9
handling: 9
Found 10
handling: 10
handling: 8
Found 9
handling: 9
handling: 8
5
Entering
handling: 4
Found 5
handling: 5
Found 6
handling: 6
Found 7
handling: 7
handling: 5
Found 6
handling: 6
handling: 5
handling: 14
Found 15
handling: 15
Found 16
handling: 16
Found 17
handling: 17
handling: 14
Found 15
handling: 15
handling: 14
7
Entering
handling: 5
Found 6
handling: 6
handling: 8
Found 9
handling: 9
handling: 8
handling: 11
Found 12
handling: 12
handling: 11
handling: 14
Found 15
handling: 15
handling: 14
8
Entering
handling: 2
Found 3
handling: 3
Found 4
handling: 4