oj.uz

Submission #1092554

# Submission time Handle Problem Language Result Execution time Memory
1092554 2024-09-24T11:33:09 Z juicy Nice sequence (IZhO18_sequence) C++17
100 / 100
 1550 ms 60504 KB 
#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif

const int N = 4e5 + 5;

int a, b;
int lt[N], rt[N], vis[N], pf[N];
bool cyc;

int timer;

void dfs(int u) {
  vis[u] = 1;
  for (auto v : {lt[u], rt[u]}) {
    if (~v) {
      if (!vis[v]) {
        dfs(v);
        if (cyc) {
          return;
        }
      } else if (vis[v] == 1) {
        cyc = 1;
        return;
      }
    }
  }
  vis[u] = 2;
  pf[u] = ++timer;
}

void add(int n) {
  memset(vis, 0, sizeof(vis));
  for (int i = 0; i <= n; ++i) {
    lt[i] = i >= b ? i - b : -1;
    rt[i] = i + a <= n ? i + a : -1;
  }
  timer = 0;
}

bool check(int n) {
  cyc = 0;
  for (int i = 0; i <= n; ++i) {
    if (!vis[i]) {
      dfs(i);
      if (cyc) {
        return 0;
      }
    }
  }
  return 1;
}

int main() {
  ios::sync_with_stdio(false); cin.tie(nullptr);

  int t; cin >> t;
  while (t--) {
    cin >> a >> b;
    int l = 1, r = a + b - 1, res = 0;
    while (l <= r) {
      int m = (l + r) / 2;
      add(m);
      if (check(m)) {
        res = m;
        l = m + 1;
      } else {
        r = m - 1;
      }
    }
    cout << res << "\n";
    add(res);
    for (int i = 0; i <= res; ++i) {
      if (!vis[i]) {
        dfs(i);
      }
    }
    for (int i = 1; i <= res; ++i) {
      pf[i] -= pf[0];
    }
    pf[0] = 0;
    for (int i = 1; i <= res; ++i) { 
      cout << pf[i] - pf[i - 1] << " ";
    }
    cout << "\n";
  }
  return 0;
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1880 KB Ok
2 Correct 4 ms 1884 KB Ok
3 Correct 3 ms 1884 KB Ok
4 Correct 4 ms 1884 KB Ok
5 Correct 4 ms 1884 KB Ok
6 Correct 4 ms 1880 KB Ok
7 Correct 4 ms 1884 KB Ok
8 Correct 3 ms 1884 KB Ok
9 Correct 4 ms 1884 KB Ok
10 Correct 4 ms 2040 KB Ok
11 Correct 4 ms 2044 KB Ok
12 Correct 4 ms 1884 KB Ok

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1884 KB Ok
2 Correct 3 ms 2004 KB Ok
3 Correct 3 ms 1884 KB Ok
4 Correct 3 ms 1884 KB Ok
5 Correct 3 ms 2004 KB Ok
6 Correct 7 ms 2136 KB Ok
7 Correct 16 ms 2908 KB Ok
8 Correct 10 ms 2484 KB Ok
9 Correct 18 ms 3164 KB Ok
10 Correct 12 ms 2648 KB Ok

Subtask #3
14.0 / 14.0

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

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1884 KB Ok
2 Correct 3 ms 1884 KB Ok
3 Correct 3 ms 1884 KB Ok
4 Correct 3 ms 1884 KB Ok
5 Correct 4 ms 1884 KB Ok
6 Correct 126 ms 16788 KB Ok
7 Correct 135 ms 18760 KB Ok
8 Correct 247 ms 21072 KB Ok
9 Correct 162 ms 19124 KB Ok
10 Correct 94 ms 10604 KB Ok
11 Correct 145 ms 20064 KB Ok

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1880 KB Ok
2 Correct 4 ms 1884 KB Ok
3 Correct 3 ms 1884 KB Ok
4 Correct 4 ms 1884 KB Ok
5 Correct 4 ms 1884 KB Ok
6 Correct 4 ms 1880 KB Ok
7 Correct 4 ms 1884 KB Ok
8 Correct 3 ms 1884 KB Ok
9 Correct 4 ms 1884 KB Ok
10 Correct 4 ms 2040 KB Ok
11 Correct 4 ms 2044 KB Ok
12 Correct 4 ms 1884 KB Ok
13 Correct 1 ms 1884 KB Ok
14 Correct 2 ms 1884 KB Ok
15 Correct 2 ms 1884 KB Ok
16 Correct 3 ms 1880 KB Ok
17 Correct 2 ms 1884 KB Ok
18 Correct 3 ms 1884 KB Ok
19 Correct 2 ms 1840 KB Ok
20 Correct 3 ms 1884 KB Ok
21 Correct 3 ms 1884 KB Ok
22 Correct 4 ms 1884 KB Ok
23 Correct 3 ms 1884 KB Ok
24 Correct 6 ms 1880 KB Ok
25 Correct 6 ms 1884 KB Ok
26 Correct 7 ms 1884 KB Ok
27 Correct 7 ms 1880 KB Ok
28 Correct 6 ms 2060 KB Ok
29 Correct 6 ms 2140 KB Ok
30 Correct 6 ms 1884 KB Ok
31 Correct 7 ms 1884 KB Ok
32 Correct 6 ms 2004 KB Ok
33 Correct 7 ms 2084 KB Ok
34 Correct 9 ms 2396 KB Ok
35 Correct 9 ms 2404 KB Ok
36 Correct 9 ms 2452 KB Ok
37 Correct 9 ms 2396 KB Ok
38 Correct 9 ms 2424 KB Ok
39 Correct 9 ms 2392 KB Ok
40 Correct 11 ms 2392 KB Ok
41 Correct 9 ms 2256 KB Ok
42 Correct 9 ms 2396 KB Ok
43 Correct 10 ms 2436 KB Ok

Subtask #6
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1880 KB Ok
2 Correct 4 ms 1884 KB Ok
3 Correct 3 ms 1884 KB Ok
4 Correct 4 ms 1884 KB Ok
5 Correct 4 ms 1884 KB Ok
6 Correct 4 ms 1880 KB Ok
7 Correct 4 ms 1884 KB Ok
8 Correct 3 ms 1884 KB Ok
9 Correct 4 ms 1884 KB Ok
10 Correct 4 ms 2040 KB Ok
11 Correct 4 ms 2044 KB Ok
12 Correct 4 ms 1884 KB Ok
13 Correct 3 ms 1884 KB Ok
14 Correct 3 ms 2004 KB Ok
15 Correct 3 ms 1884 KB Ok
16 Correct 3 ms 1884 KB Ok
17 Correct 3 ms 2004 KB Ok
18 Correct 7 ms 2136 KB Ok
19 Correct 16 ms 2908 KB Ok
20 Correct 10 ms 2484 KB Ok
21 Correct 18 ms 3164 KB Ok
22 Correct 12 ms 2648 KB Ok
23 Correct 1 ms 1884 KB Ok
24 Correct 2 ms 1884 KB Ok
25 Correct 2 ms 1884 KB Ok
26 Correct 3 ms 1880 KB Ok
27 Correct 2 ms 1884 KB Ok
28 Correct 3 ms 1884 KB Ok
29 Correct 2 ms 1840 KB Ok
30 Correct 3 ms 1884 KB Ok
31 Correct 3 ms 1884 KB Ok
32 Correct 4 ms 1884 KB Ok
33 Correct 3 ms 1884 KB Ok
34 Correct 6 ms 1880 KB Ok
35 Correct 6 ms 1884 KB Ok
36 Correct 7 ms 1884 KB Ok
37 Correct 7 ms 1880 KB Ok
38 Correct 6 ms 2060 KB Ok
39 Correct 6 ms 2140 KB Ok
40 Correct 6 ms 1884 KB Ok
41 Correct 7 ms 1884 KB Ok
42 Correct 6 ms 2004 KB Ok
43 Correct 7 ms 2084 KB Ok
44 Correct 9 ms 2396 KB Ok
45 Correct 9 ms 2404 KB Ok
46 Correct 9 ms 2452 KB Ok
47 Correct 9 ms 2396 KB Ok
48 Correct 9 ms 2424 KB Ok
49 Correct 9 ms 2392 KB Ok
50 Correct 11 ms 2392 KB Ok
51 Correct 9 ms 2256 KB Ok
52 Correct 9 ms 2396 KB Ok
53 Correct 10 ms 2436 KB Ok
54 Correct 92 ms 4688 KB Ok
55 Correct 104 ms 4948 KB Ok
56 Correct 100 ms 4948 KB Ok
57 Correct 76 ms 4176 KB Ok
58 Correct 104 ms 4436 KB Ok
59 Correct 78 ms 4300 KB Ok
60 Correct 77 ms 4024 KB Ok
61 Correct 74 ms 4300 KB Ok
62 Correct 90 ms 4652 KB Ok
63 Correct 83 ms 4436 KB Ok
64 Correct 99 ms 5032 KB Ok
65 Correct 88 ms 4516 KB Ok
66 Correct 84 ms 4432 KB Ok
67 Correct 82 ms 4332 KB Ok
68 Correct 83 ms 4464 KB Ok
69 Correct 254 ms 15320 KB Ok
70 Correct 285 ms 15800 KB Ok
71 Correct 254 ms 15444 KB Ok
72 Correct 250 ms 15184 KB Ok
73 Correct 257 ms 15444 KB Ok
74 Correct 245 ms 15284 KB Ok
75 Correct 279 ms 14676 KB Ok
76 Correct 292 ms 15456 KB Ok
77 Correct 282 ms 14928 KB Ok
78 Correct 285 ms 15444 KB Ok
79 Correct 271 ms 15440 KB Ok
80 Correct 249 ms 15448 KB Ok
81 Correct 273 ms 15384 KB Ok
82 Correct 251 ms 15444 KB Ok
83 Correct 243 ms 14932 KB Ok

Subtask #7
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1880 KB Ok
2 Correct 4 ms 1884 KB Ok
3 Correct 3 ms 1884 KB Ok
4 Correct 4 ms 1884 KB Ok
5 Correct 4 ms 1884 KB Ok
6 Correct 4 ms 1880 KB Ok
7 Correct 4 ms 1884 KB Ok
8 Correct 3 ms 1884 KB Ok
9 Correct 4 ms 1884 KB Ok
10 Correct 4 ms 2040 KB Ok
11 Correct 4 ms 2044 KB Ok
12 Correct 4 ms 1884 KB Ok
13 Correct 3 ms 1884 KB Ok
14 Correct 3 ms 2004 KB Ok
15 Correct 3 ms 1884 KB Ok
16 Correct 3 ms 1884 KB Ok
17 Correct 3 ms 2004 KB Ok
18 Correct 7 ms 2136 KB Ok
19 Correct 16 ms 2908 KB Ok
20 Correct 10 ms 2484 KB Ok
21 Correct 18 ms 3164 KB Ok
22 Correct 12 ms 2648 KB Ok
23 Correct 1 ms 1884 KB Ok
24 Correct 2 ms 1884 KB Ok
25 Correct 2 ms 1884 KB Ok
26 Correct 3 ms 1880 KB Ok
27 Correct 2 ms 1884 KB Ok
28 Correct 3 ms 1884 KB Ok
29 Correct 2 ms 1840 KB Ok
30 Correct 3 ms 1884 KB Ok
31 Correct 3 ms 1884 KB Ok
32 Correct 4 ms 1884 KB Ok
33 Correct 3 ms 1884 KB Ok
34 Correct 2 ms 1884 KB Ok
35 Correct 3 ms 1884 KB Ok
36 Correct 3 ms 1884 KB Ok
37 Correct 3 ms 1884 KB Ok
38 Correct 4 ms 1884 KB Ok
39 Correct 126 ms 16788 KB Ok
40 Correct 135 ms 18760 KB Ok
41 Correct 247 ms 21072 KB Ok
42 Correct 162 ms 19124 KB Ok
43 Correct 94 ms 10604 KB Ok
44 Correct 145 ms 20064 KB Ok
45 Correct 6 ms 1880 KB Ok
46 Correct 6 ms 1884 KB Ok
47 Correct 7 ms 1884 KB Ok
48 Correct 7 ms 1880 KB Ok
49 Correct 6 ms 2060 KB Ok
50 Correct 6 ms 2140 KB Ok
51 Correct 6 ms 1884 KB Ok
52 Correct 7 ms 1884 KB Ok
53 Correct 6 ms 2004 KB Ok
54 Correct 7 ms 2084 KB Ok
55 Correct 9 ms 2396 KB Ok
56 Correct 9 ms 2404 KB Ok
57 Correct 9 ms 2452 KB Ok
58 Correct 9 ms 2396 KB Ok
59 Correct 9 ms 2424 KB Ok
60 Correct 9 ms 2392 KB Ok
61 Correct 11 ms 2392 KB Ok
62 Correct 9 ms 2256 KB Ok
63 Correct 9 ms 2396 KB Ok
64 Correct 10 ms 2436 KB Ok
65 Correct 92 ms 4688 KB Ok
66 Correct 104 ms 4948 KB Ok
67 Correct 100 ms 4948 KB Ok
68 Correct 76 ms 4176 KB Ok
69 Correct 104 ms 4436 KB Ok
70 Correct 78 ms 4300 KB Ok
71 Correct 77 ms 4024 KB Ok
72 Correct 74 ms 4300 KB Ok
73 Correct 90 ms 4652 KB Ok
74 Correct 83 ms 4436 KB Ok
75 Correct 99 ms 5032 KB Ok
76 Correct 88 ms 4516 KB Ok
77 Correct 84 ms 4432 KB Ok
78 Correct 82 ms 4332 KB Ok
79 Correct 83 ms 4464 KB Ok
80 Correct 254 ms 15320 KB Ok
81 Correct 285 ms 15800 KB Ok
82 Correct 254 ms 15444 KB Ok
83 Correct 250 ms 15184 KB Ok
84 Correct 257 ms 15444 KB Ok
85 Correct 245 ms 15284 KB Ok
86 Correct 279 ms 14676 KB Ok
87 Correct 292 ms 15456 KB Ok
88 Correct 282 ms 14928 KB Ok
89 Correct 285 ms 15444 KB Ok
90 Correct 271 ms 15440 KB Ok
91 Correct 249 ms 15448 KB Ok
92 Correct 273 ms 15384 KB Ok
93 Correct 251 ms 15444 KB Ok
94 Correct 243 ms 14932 KB Ok
95 Correct 248 ms 9128 KB Ok
96 Correct 317 ms 11756 KB Ok
97 Correct 278 ms 10552 KB Ok
98 Correct 221 ms 9580 KB Ok
99 Correct 250 ms 9988 KB Ok
100 Correct 273 ms 9812 KB Ok
101 Correct 282 ms 10580 KB Ok
102 Correct 293 ms 10580 KB Ok
103 Correct 295 ms 10580 KB Ok
104 Correct 342 ms 11852 KB Ok
105 Correct 312 ms 11604 KB Ok
106 Correct 287 ms 11348 KB Ok
107 Correct 314 ms 11088 KB Ok
108 Correct 332 ms 11860 KB Ok
109 Correct 293 ms 11840 KB Ok
110 Correct 1347 ms 56400 KB Ok
111 Correct 1500 ms 59472 KB Ok
112 Correct 1339 ms 59220 KB Ok
113 Correct 1428 ms 58452 KB Ok
114 Correct 1346 ms 60504 KB Ok
115 Correct 1550 ms 58192 KB Ok
116 Correct 1448 ms 59696 KB Ok
117 Correct 1459 ms 58196 KB Ok
118 Correct 1282 ms 58196 KB Ok
119 Correct 1480 ms 58192 KB Ok
120 Correct 1412 ms 57936 KB Ok
121 Correct 1358 ms 56500 KB Ok
122 Correct 1336 ms 58956 KB Ok
123 Correct 1477 ms 59468 KB Ok
124 Correct 1405 ms 56644 KB Ok
125 Correct 954 ms 41692 KB Ok