oj.uz

Submission #785691

# Submission time Handle Problem Language Result Execution time Memory
785691 2023-07-17T13:05:18 Z Soumya1 Nice sequence (IZhO18_sequence) C++17
100 / 100
 972 ms 32748 KB 
#include <bits/stdc++.h>
#ifdef __LOCAL__
  #include <debug_local.h>
#endif
using namespace std;
void testCase() {
  int n, m;
  cin >> n >> m;
  int lo = 0, hi = 2 * (n + m);
  vector<int> q;
  auto check = [&](int l) {
    vector<int> deg(l + 1);
    for (int i = 0; i <= l; i++) {
      if (i - n >= 0) deg[i - n]++;
      if (i + m <= l) deg[i + m]++;
    }
    q.clear();
    for (int i = 0; i <= l; i++) {
      if (!deg[i]) q.push_back(i);
    }
    for (int i = 0; i < q.size(); i++) {
      int u = q[i];
      for (int v : {u - n, u + m}) {
        if (v >= 0 && v <= l) {
          deg[v]--;
          if (!deg[v]) q.push_back(v);
        }
      }
    }
    return (q.size() == l + 1);
  };
  while (lo < hi) {
    int mid = (lo + hi + 1) >> 1;
    if (check(mid)) lo = mid;
    else hi = mid - 1;
  }
  check(lo);
  vector<int> ans(lo + 1);
  for (int i = 0; i <= lo; i++) {
    ans[q[i]] = i;
  }
  cout << lo << "\n";
  for (int i = 1; i <= lo; i++) {
    cout << ans[i] - ans[i - 1] << " ";
  }
  cout << "\n";
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int tc;
  cin >> tc;
  while (tc--) {
    testCase();
  }
  return 0;
}

Compilation message

sequence.cpp: In lambda function:
sequence.cpp:21:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |     for (int i = 0; i < q.size(); i++) {
      |                     ~~^~~~~~~~~~
sequence.cpp:30:22: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   30 |     return (q.size() == l + 1);
      |             ~~~~~~~~~^~~~~~~~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Ok
2 Correct 1 ms 212 KB Ok
3 Correct 1 ms 212 KB Ok
4 Correct 1 ms 212 KB Ok
5 Correct 1 ms 212 KB Ok
6 Correct 1 ms 316 KB Ok
7 Correct 1 ms 212 KB Ok
8 Correct 1 ms 212 KB Ok
9 Correct 1 ms 212 KB Ok
10 Correct 1 ms 212 KB Ok
11 Correct 1 ms 212 KB Ok
12 Correct 1 ms 212 KB Ok

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Ok
2 Correct 1 ms 212 KB Ok
3 Correct 1 ms 328 KB Ok
4 Correct 1 ms 212 KB Ok
5 Correct 1 ms 212 KB Ok
6 Correct 3 ms 340 KB Ok
7 Correct 14 ms 800 KB Ok
8 Correct 6 ms 468 KB Ok
9 Correct 17 ms 780 KB Ok
10 Correct 9 ms 560 KB Ok

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Ok
2 Correct 1 ms 212 KB Ok
3 Correct 1 ms 212 KB Ok
4 Correct 0 ms 212 KB Ok
5 Correct 0 ms 212 KB Ok
6 Correct 1 ms 212 KB Ok
7 Correct 1 ms 320 KB Ok
8 Correct 1 ms 212 KB Ok
9 Correct 1 ms 320 KB Ok
10 Correct 0 ms 212 KB Ok
11 Correct 1 ms 320 KB Ok

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Ok
2 Correct 1 ms 212 KB Ok
3 Correct 0 ms 212 KB Ok
4 Correct 0 ms 212 KB Ok
5 Correct 1 ms 212 KB Ok
6 Correct 159 ms 4624 KB Ok
7 Correct 147 ms 3600 KB Ok
8 Correct 279 ms 6744 KB Ok
9 Correct 194 ms 6936 KB Ok
10 Correct 117 ms 2632 KB Ok
11 Correct 193 ms 5980 KB Ok

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Ok
2 Correct 1 ms 212 KB Ok
3 Correct 1 ms 212 KB Ok
4 Correct 1 ms 212 KB Ok
5 Correct 1 ms 212 KB Ok
6 Correct 1 ms 316 KB Ok
7 Correct 1 ms 212 KB Ok
8 Correct 1 ms 212 KB Ok
9 Correct 1 ms 212 KB Ok
10 Correct 1 ms 212 KB Ok
11 Correct 1 ms 212 KB Ok
12 Correct 1 ms 212 KB Ok
13 Correct 0 ms 212 KB Ok
14 Correct 1 ms 212 KB Ok
15 Correct 1 ms 212 KB Ok
16 Correct 0 ms 212 KB Ok
17 Correct 0 ms 212 KB Ok
18 Correct 1 ms 212 KB Ok
19 Correct 1 ms 320 KB Ok
20 Correct 1 ms 212 KB Ok
21 Correct 1 ms 320 KB Ok
22 Correct 0 ms 212 KB Ok
23 Correct 1 ms 320 KB Ok
24 Correct 3 ms 340 KB Ok
25 Correct 3 ms 340 KB Ok
26 Correct 3 ms 340 KB Ok
27 Correct 3 ms 320 KB Ok
28 Correct 2 ms 340 KB Ok
29 Correct 3 ms 364 KB Ok
30 Correct 2 ms 340 KB Ok
31 Correct 3 ms 340 KB Ok
32 Correct 3 ms 340 KB Ok
33 Correct 3 ms 340 KB Ok
34 Correct 5 ms 468 KB Ok
35 Correct 5 ms 444 KB Ok
36 Correct 5 ms 468 KB Ok
37 Correct 5 ms 468 KB Ok
38 Correct 5 ms 468 KB Ok
39 Correct 5 ms 468 KB Ok
40 Correct 7 ms 468 KB Ok
41 Correct 5 ms 452 KB Ok
42 Correct 5 ms 468 KB Ok
43 Correct 5 ms 468 KB Ok

Subtask #6
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Ok
2 Correct 1 ms 212 KB Ok
3 Correct 1 ms 212 KB Ok
4 Correct 1 ms 212 KB Ok
5 Correct 1 ms 212 KB Ok
6 Correct 1 ms 316 KB Ok
7 Correct 1 ms 212 KB Ok
8 Correct 1 ms 212 KB Ok
9 Correct 1 ms 212 KB Ok
10 Correct 1 ms 212 KB Ok
11 Correct 1 ms 212 KB Ok
12 Correct 1 ms 212 KB Ok
13 Correct 1 ms 212 KB Ok
14 Correct 1 ms 212 KB Ok
15 Correct 1 ms 328 KB Ok
16 Correct 1 ms 212 KB Ok
17 Correct 1 ms 212 KB Ok
18 Correct 3 ms 340 KB Ok
19 Correct 14 ms 800 KB Ok
20 Correct 6 ms 468 KB Ok
21 Correct 17 ms 780 KB Ok
22 Correct 9 ms 560 KB Ok
23 Correct 0 ms 212 KB Ok
24 Correct 1 ms 212 KB Ok
25 Correct 1 ms 212 KB Ok
26 Correct 0 ms 212 KB Ok
27 Correct 0 ms 212 KB Ok
28 Correct 1 ms 212 KB Ok
29 Correct 1 ms 320 KB Ok
30 Correct 1 ms 212 KB Ok
31 Correct 1 ms 320 KB Ok
32 Correct 0 ms 212 KB Ok
33 Correct 1 ms 320 KB Ok
34 Correct 3 ms 340 KB Ok
35 Correct 3 ms 340 KB Ok
36 Correct 3 ms 340 KB Ok
37 Correct 3 ms 320 KB Ok
38 Correct 2 ms 340 KB Ok
39 Correct 3 ms 364 KB Ok
40 Correct 2 ms 340 KB Ok
41 Correct 3 ms 340 KB Ok
42 Correct 3 ms 340 KB Ok
43 Correct 3 ms 340 KB Ok
44 Correct 5 ms 468 KB Ok
45 Correct 5 ms 444 KB Ok
46 Correct 5 ms 468 KB Ok
47 Correct 5 ms 468 KB Ok
48 Correct 5 ms 468 KB Ok
49 Correct 5 ms 468 KB Ok
50 Correct 7 ms 468 KB Ok
51 Correct 5 ms 452 KB Ok
52 Correct 5 ms 468 KB Ok
53 Correct 5 ms 468 KB Ok
54 Correct 110 ms 2904 KB Ok
55 Correct 128 ms 2892 KB Ok
56 Correct 122 ms 3000 KB Ok
57 Correct 97 ms 2284 KB Ok
58 Correct 113 ms 2888 KB Ok
59 Correct 119 ms 2708 KB Ok
60 Correct 99 ms 2692 KB Ok
61 Correct 96 ms 2656 KB Ok
62 Correct 131 ms 3068 KB Ok
63 Correct 106 ms 2608 KB Ok
64 Correct 123 ms 2912 KB Ok
65 Correct 120 ms 2740 KB Ok
66 Correct 111 ms 2664 KB Ok
67 Correct 98 ms 2672 KB Ok
68 Correct 120 ms 2768 KB Ok
69 Correct 186 ms 6892 KB Ok
70 Correct 185 ms 7972 KB Ok
71 Correct 179 ms 6176 KB Ok
72 Correct 184 ms 7308 KB Ok
73 Correct 179 ms 6508 KB Ok
74 Correct 179 ms 5544 KB Ok
75 Correct 200 ms 5804 KB Ok
76 Correct 183 ms 7872 KB Ok
77 Correct 169 ms 5136 KB Ok
78 Correct 184 ms 7432 KB Ok
79 Correct 180 ms 7096 KB Ok
80 Correct 183 ms 6700 KB Ok
81 Correct 179 ms 7176 KB Ok
82 Correct 192 ms 6912 KB Ok
83 Correct 173 ms 5880 KB Ok

Subtask #7
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Ok
2 Correct 1 ms 212 KB Ok
3 Correct 1 ms 212 KB Ok
4 Correct 1 ms 212 KB Ok
5 Correct 1 ms 212 KB Ok
6 Correct 1 ms 316 KB Ok
7 Correct 1 ms 212 KB Ok
8 Correct 1 ms 212 KB Ok
9 Correct 1 ms 212 KB Ok
10 Correct 1 ms 212 KB Ok
11 Correct 1 ms 212 KB Ok
12 Correct 1 ms 212 KB Ok
13 Correct 1 ms 212 KB Ok
14 Correct 1 ms 212 KB Ok
15 Correct 1 ms 328 KB Ok
16 Correct 1 ms 212 KB Ok
17 Correct 1 ms 212 KB Ok
18 Correct 3 ms 340 KB Ok
19 Correct 14 ms 800 KB Ok
20 Correct 6 ms 468 KB Ok
21 Correct 17 ms 780 KB Ok
22 Correct 9 ms 560 KB Ok
23 Correct 0 ms 212 KB Ok
24 Correct 1 ms 212 KB Ok
25 Correct 1 ms 212 KB Ok
26 Correct 0 ms 212 KB Ok
27 Correct 0 ms 212 KB Ok
28 Correct 1 ms 212 KB Ok
29 Correct 1 ms 320 KB Ok
30 Correct 1 ms 212 KB Ok
31 Correct 1 ms 320 KB Ok
32 Correct 0 ms 212 KB Ok
33 Correct 1 ms 320 KB Ok
34 Correct 0 ms 212 KB Ok
35 Correct 1 ms 212 KB Ok
36 Correct 0 ms 212 KB Ok
37 Correct 0 ms 212 KB Ok
38 Correct 1 ms 212 KB Ok
39 Correct 159 ms 4624 KB Ok
40 Correct 147 ms 3600 KB Ok
41 Correct 279 ms 6744 KB Ok
42 Correct 194 ms 6936 KB Ok
43 Correct 117 ms 2632 KB Ok
44 Correct 193 ms 5980 KB Ok
45 Correct 3 ms 340 KB Ok
46 Correct 3 ms 340 KB Ok
47 Correct 3 ms 340 KB Ok
48 Correct 3 ms 320 KB Ok
49 Correct 2 ms 340 KB Ok
50 Correct 3 ms 364 KB Ok
51 Correct 2 ms 340 KB Ok
52 Correct 3 ms 340 KB Ok
53 Correct 3 ms 340 KB Ok
54 Correct 3 ms 340 KB Ok
55 Correct 5 ms 468 KB Ok
56 Correct 5 ms 444 KB Ok
57 Correct 5 ms 468 KB Ok
58 Correct 5 ms 468 KB Ok
59 Correct 5 ms 468 KB Ok
60 Correct 5 ms 468 KB Ok
61 Correct 7 ms 468 KB Ok
62 Correct 5 ms 452 KB Ok
63 Correct 5 ms 468 KB Ok
64 Correct 5 ms 468 KB Ok
65 Correct 110 ms 2904 KB Ok
66 Correct 128 ms 2892 KB Ok
67 Correct 122 ms 3000 KB Ok
68 Correct 97 ms 2284 KB Ok
69 Correct 113 ms 2888 KB Ok
70 Correct 119 ms 2708 KB Ok
71 Correct 99 ms 2692 KB Ok
72 Correct 96 ms 2656 KB Ok
73 Correct 131 ms 3068 KB Ok
74 Correct 106 ms 2608 KB Ok
75 Correct 123 ms 2912 KB Ok
76 Correct 120 ms 2740 KB Ok
77 Correct 111 ms 2664 KB Ok
78 Correct 98 ms 2672 KB Ok
79 Correct 120 ms 2768 KB Ok
80 Correct 186 ms 6892 KB Ok
81 Correct 185 ms 7972 KB Ok
82 Correct 179 ms 6176 KB Ok
83 Correct 184 ms 7308 KB Ok
84 Correct 179 ms 6508 KB Ok
85 Correct 179 ms 5544 KB Ok
86 Correct 200 ms 5804 KB Ok
87 Correct 183 ms 7872 KB Ok
88 Correct 169 ms 5136 KB Ok
89 Correct 184 ms 7432 KB Ok
90 Correct 180 ms 7096 KB Ok
91 Correct 183 ms 6700 KB Ok
92 Correct 179 ms 7176 KB Ok
93 Correct 192 ms 6912 KB Ok
94 Correct 173 ms 5880 KB Ok
95 Correct 305 ms 6132 KB Ok
96 Correct 420 ms 8944 KB Ok
97 Correct 410 ms 8124 KB Ok
98 Correct 328 ms 6908 KB Ok
99 Correct 383 ms 7572 KB Ok
100 Correct 383 ms 7784 KB Ok
101 Correct 391 ms 9500 KB Ok
102 Correct 372 ms 8416 KB Ok
103 Correct 372 ms 8088 KB Ok
104 Correct 442 ms 9408 KB Ok
105 Correct 419 ms 9292 KB Ok
106 Correct 357 ms 7468 KB Ok
107 Correct 410 ms 9604 KB Ok
108 Correct 435 ms 10072 KB Ok
109 Correct 398 ms 8468 KB Ok
110 Correct 784 ms 22872 KB Ok
111 Correct 816 ms 32748 KB Ok
112 Correct 783 ms 25044 KB Ok
113 Correct 795 ms 29160 KB Ok
114 Correct 795 ms 31388 KB Ok
115 Correct 800 ms 30648 KB Ok
116 Correct 800 ms 30468 KB Ok
117 Correct 801 ms 31284 KB Ok
118 Correct 786 ms 26804 KB Ok
119 Correct 820 ms 31608 KB Ok
120 Correct 797 ms 26204 KB Ok
121 Correct 773 ms 24968 KB Ok
122 Correct 778 ms 29032 KB Ok
123 Correct 804 ms 32712 KB Ok
124 Correct 774 ms 22608 KB Ok
125 Correct 972 ms 15972 KB Ok