oj.uz

Submission #343790

# Submission time Handle Problem Language Result Execution time Memory
343790 2021-01-04T13:29:47 Z Pety Nice sequence (IZhO18_sequence) C++14
100 / 100
 1450 ms 52988 KB 
#include <bits/stdc++.h>
#pragma GCC optimize ("O1")
#pragma GCC optimize ("O3")

using namespace std;

int k, ans[500002], val[500002], n, m, i;
bool viz[500002];
int top[500002];

void dfs (int x, int len) {
  viz[x] = 1;
  if (x + n <= len && !viz[x + n])
    dfs(x + n, len);
  if (x - m >= 0 && !viz[x - m])
    dfs(x - m, len);
  top[++k] = x;
}

bool ok (int len) {
  for (i = 0;i <= len; i++)
    val[i] = viz[i] = 0;
  k = 0;
  for (i = 0; i <= len; i++)
    if (!viz[i])
      dfs(i, len);
  for (i = 1; i <= len + 1; i++)
    val[top[i]] = i;
  for (i = 0; i <= len; i++) {
    if (i >= n && val[i] > val[i - n])
      return false;
    if (i + m <= len && val[i] > val[i + m])
      return false;
  }
  for (i = 1; i <= len; i++)
    ans[i] = val[i] - val[i - 1];
  return true;
}

int main()
{
  ios_base::sync_with_stdio(false);
  cin.tie(0); cout.tie(0);
  int t;
  cin >> t;
  for (int T = 1; T <= t; T++) {
    cin >> n >> m;
    int sol = 0;
    for (int pas = (1 << 19); pas; (pas >>= 1))
      if (sol + pas <= n + m && ok(sol + pas))
        sol += pas;
    cout << sol << "\n";
    ok(sol);
    for (int j = 1; j <= sol; j++)
      cout << ans[j] << " ";
    cout << "\n";
  }
  return 0;
}

Subtask #1
6.0 / 6.0

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

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Ok
2 Correct 1 ms 364 KB Ok
3 Correct 1 ms 364 KB Ok
4 Correct 1 ms 364 KB Ok
5 Correct 1 ms 364 KB Ok
6 Correct 5 ms 492 KB Ok
7 Correct 17 ms 1260 KB Ok
8 Correct 9 ms 748 KB Ok
9 Correct 22 ms 1388 KB Ok
10 Correct 12 ms 1004 KB Ok

Subtask #3
14.0 / 14.0

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

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Ok
2 Correct 1 ms 364 KB Ok
3 Correct 1 ms 364 KB Ok
4 Correct 1 ms 364 KB Ok
5 Correct 1 ms 364 KB Ok
6 Correct 193 ms 13036 KB Ok
7 Correct 198 ms 14316 KB Ok
8 Correct 390 ms 16932 KB Ok
9 Correct 266 ms 15084 KB Ok
10 Correct 136 ms 7788 KB Ok
11 Correct 248 ms 15852 KB Ok

Subtask #5
14.0 / 14.0

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

Subtask #6
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Ok
2 Correct 1 ms 364 KB Ok
3 Correct 1 ms 364 KB Ok
4 Correct 1 ms 364 KB Ok
5 Correct 1 ms 492 KB Ok
6 Correct 1 ms 364 KB Ok
7 Correct 1 ms 364 KB Ok
8 Correct 1 ms 364 KB Ok
9 Correct 1 ms 364 KB Ok
10 Correct 1 ms 364 KB Ok
11 Correct 1 ms 364 KB Ok
12 Correct 1 ms 364 KB Ok
13 Correct 1 ms 364 KB Ok
14 Correct 1 ms 364 KB Ok
15 Correct 1 ms 364 KB Ok
16 Correct 1 ms 364 KB Ok
17 Correct 1 ms 364 KB Ok
18 Correct 5 ms 492 KB Ok
19 Correct 17 ms 1260 KB Ok
20 Correct 9 ms 748 KB Ok
21 Correct 22 ms 1388 KB Ok
22 Correct 12 ms 1004 KB Ok
23 Correct 1 ms 364 KB Ok
24 Correct 1 ms 364 KB Ok
25 Correct 1 ms 364 KB Ok
26 Correct 1 ms 364 KB Ok
27 Correct 1 ms 364 KB Ok
28 Correct 1 ms 364 KB Ok
29 Correct 1 ms 364 KB Ok
30 Correct 1 ms 364 KB Ok
31 Correct 1 ms 364 KB Ok
32 Correct 1 ms 364 KB Ok
33 Correct 1 ms 364 KB Ok
34 Correct 4 ms 492 KB Ok
35 Correct 4 ms 492 KB Ok
36 Correct 5 ms 492 KB Ok
37 Correct 4 ms 492 KB Ok
38 Correct 5 ms 492 KB Ok
39 Correct 4 ms 492 KB Ok
40 Correct 3 ms 364 KB Ok
41 Correct 4 ms 492 KB Ok
42 Correct 4 ms 492 KB Ok
43 Correct 4 ms 492 KB Ok
44 Correct 8 ms 748 KB Ok
45 Correct 7 ms 748 KB Ok
46 Correct 8 ms 748 KB Ok
47 Correct 8 ms 748 KB Ok
48 Correct 8 ms 748 KB Ok
49 Correct 8 ms 748 KB Ok
50 Correct 9 ms 748 KB Ok
51 Correct 8 ms 748 KB Ok
52 Correct 8 ms 748 KB Ok
53 Correct 8 ms 748 KB Ok
54 Correct 176 ms 3308 KB Ok
55 Correct 207 ms 3564 KB Ok
56 Correct 199 ms 3512 KB Ok
57 Correct 158 ms 2924 KB Ok
58 Correct 175 ms 3052 KB Ok
59 Correct 159 ms 3052 KB Ok
60 Correct 151 ms 2668 KB Ok
61 Correct 157 ms 2924 KB Ok
62 Correct 193 ms 3308 KB Ok
63 Correct 180 ms 2980 KB Ok
64 Correct 195 ms 3564 KB Ok
65 Correct 182 ms 3308 KB Ok
66 Correct 171 ms 3052 KB Ok
67 Correct 156 ms 2924 KB Ok
68 Correct 174 ms 3052 KB Ok
69 Correct 276 ms 12396 KB Ok
70 Correct 264 ms 12908 KB Ok
71 Correct 265 ms 12396 KB Ok
72 Correct 274 ms 12268 KB Ok
73 Correct 273 ms 12396 KB Ok
74 Correct 262 ms 12140 KB Ok
75 Correct 297 ms 11756 KB Ok
76 Correct 275 ms 12524 KB Ok
77 Correct 268 ms 11884 KB Ok
78 Correct 262 ms 12396 KB Ok
79 Correct 282 ms 12652 KB Ok
80 Correct 287 ms 12524 KB Ok
81 Correct 274 ms 12524 KB Ok
82 Correct 273 ms 12652 KB Ok
83 Correct 279 ms 12012 KB Ok

Subtask #7
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Ok
2 Correct 1 ms 364 KB Ok
3 Correct 1 ms 364 KB Ok
4 Correct 1 ms 364 KB Ok
5 Correct 1 ms 492 KB Ok
6 Correct 1 ms 364 KB Ok
7 Correct 1 ms 364 KB Ok
8 Correct 1 ms 364 KB Ok
9 Correct 1 ms 364 KB Ok
10 Correct 1 ms 364 KB Ok
11 Correct 1 ms 364 KB Ok
12 Correct 1 ms 364 KB Ok
13 Correct 1 ms 364 KB Ok
14 Correct 1 ms 364 KB Ok
15 Correct 1 ms 364 KB Ok
16 Correct 1 ms 364 KB Ok
17 Correct 1 ms 364 KB Ok
18 Correct 5 ms 492 KB Ok
19 Correct 17 ms 1260 KB Ok
20 Correct 9 ms 748 KB Ok
21 Correct 22 ms 1388 KB Ok
22 Correct 12 ms 1004 KB Ok
23 Correct 1 ms 364 KB Ok
24 Correct 1 ms 364 KB Ok
25 Correct 1 ms 364 KB Ok
26 Correct 1 ms 364 KB Ok
27 Correct 1 ms 364 KB Ok
28 Correct 1 ms 364 KB Ok
29 Correct 1 ms 364 KB Ok
30 Correct 1 ms 364 KB Ok
31 Correct 1 ms 364 KB Ok
32 Correct 1 ms 364 KB Ok
33 Correct 1 ms 364 KB Ok
34 Correct 1 ms 364 KB Ok
35 Correct 1 ms 364 KB Ok
36 Correct 1 ms 364 KB Ok
37 Correct 1 ms 364 KB Ok
38 Correct 1 ms 364 KB Ok
39 Correct 193 ms 13036 KB Ok
40 Correct 198 ms 14316 KB Ok
41 Correct 390 ms 16932 KB Ok
42 Correct 266 ms 15084 KB Ok
43 Correct 136 ms 7788 KB Ok
44 Correct 248 ms 15852 KB Ok
45 Correct 4 ms 492 KB Ok
46 Correct 4 ms 492 KB Ok
47 Correct 5 ms 492 KB Ok
48 Correct 4 ms 492 KB Ok
49 Correct 5 ms 492 KB Ok
50 Correct 4 ms 492 KB Ok
51 Correct 3 ms 364 KB Ok
52 Correct 4 ms 492 KB Ok
53 Correct 4 ms 492 KB Ok
54 Correct 4 ms 492 KB Ok
55 Correct 8 ms 748 KB Ok
56 Correct 7 ms 748 KB Ok
57 Correct 8 ms 748 KB Ok
58 Correct 8 ms 748 KB Ok
59 Correct 8 ms 748 KB Ok
60 Correct 8 ms 748 KB Ok
61 Correct 9 ms 748 KB Ok
62 Correct 8 ms 748 KB Ok
63 Correct 8 ms 748 KB Ok
64 Correct 8 ms 748 KB Ok
65 Correct 176 ms 3308 KB Ok
66 Correct 207 ms 3564 KB Ok
67 Correct 199 ms 3512 KB Ok
68 Correct 158 ms 2924 KB Ok
69 Correct 175 ms 3052 KB Ok
70 Correct 159 ms 3052 KB Ok
71 Correct 151 ms 2668 KB Ok
72 Correct 157 ms 2924 KB Ok
73 Correct 193 ms 3308 KB Ok
74 Correct 180 ms 2980 KB Ok
75 Correct 195 ms 3564 KB Ok
76 Correct 182 ms 3308 KB Ok
77 Correct 171 ms 3052 KB Ok
78 Correct 156 ms 2924 KB Ok
79 Correct 174 ms 3052 KB Ok
80 Correct 276 ms 12396 KB Ok
81 Correct 264 ms 12908 KB Ok
82 Correct 265 ms 12396 KB Ok
83 Correct 274 ms 12268 KB Ok
84 Correct 273 ms 12396 KB Ok
85 Correct 262 ms 12140 KB Ok
86 Correct 297 ms 11756 KB Ok
87 Correct 275 ms 12524 KB Ok
88 Correct 268 ms 11884 KB Ok
89 Correct 262 ms 12396 KB Ok
90 Correct 282 ms 12652 KB Ok
91 Correct 287 ms 12524 KB Ok
92 Correct 274 ms 12524 KB Ok
93 Correct 273 ms 12652 KB Ok
94 Correct 279 ms 12012 KB Ok
95 Correct 550 ms 7916 KB Ok
96 Correct 677 ms 10604 KB Ok
97 Correct 628 ms 9580 KB Ok
98 Correct 523 ms 8428 KB Ok
99 Correct 587 ms 9068 KB Ok
100 Correct 548 ms 8992 KB Ok
101 Correct 612 ms 9572 KB Ok
102 Correct 580 ms 9068 KB Ok
103 Correct 588 ms 9344 KB Ok
104 Correct 744 ms 10732 KB Ok
105 Correct 649 ms 10476 KB Ok
106 Correct 583 ms 10184 KB Ok
107 Correct 659 ms 9964 KB Ok
108 Correct 725 ms 10604 KB Ok
109 Correct 656 ms 10732 KB Ok
110 Correct 1183 ms 49136 KB Ok
111 Correct 1321 ms 52132 KB Ok
112 Correct 1436 ms 51912 KB Ok
113 Correct 1340 ms 51220 KB Ok
114 Correct 1239 ms 52988 KB Ok
115 Correct 1382 ms 50940 KB Ok
116 Correct 1345 ms 52272 KB Ok
117 Correct 1250 ms 50796 KB Ok
118 Correct 1318 ms 50904 KB Ok
119 Correct 1338 ms 50828 KB Ok
120 Correct 1309 ms 50412 KB Ok
121 Correct 1348 ms 49340 KB Ok
122 Correct 1450 ms 51564 KB Ok
123 Correct 1393 ms 52076 KB Ok
124 Correct 1310 ms 49388 KB Ok
125 Correct 1335 ms 34284 KB Ok