oj.uz

Submission #993138

# Submission time Handle Problem Language Result Execution time Memory
993138 2024-06-05T10:57:30 Z tch1cherin Nice sequence (IZhO18_sequence) C++17
76 / 100
 2000 ms 57988 KB 
#include <bits/stdc++.h>
using namespace std;

vector<vector<int>> graph;
vector<bool> used;
vector<int> tout;
int T = 0;

void dfs(int u) {
  used[u] = true;
  for (int v : graph[u]) {
    if (!used[v]) {
      dfs(v);
    }
  }
  tout[u] = T++;
}

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  int T;
  cin >> T;
  while (T--) {
    int N, M;
    cin >> N >> M;
    int l = -1, r = 2 * (N + M) + 1;
    vector<int> answer;
    while (r > l + 1) {
      int mid = (l + r) / 2;
      graph.assign(mid + 1, {});
      used.assign(mid + 1, false);
      tout.resize(mid + 1);
      for (int i = 0; i + N <= mid; i++) {
        graph[i].push_back(i + N);
      }
      for (int i = 0; i + M <= mid; i++) {
        graph[i + M].push_back(i);
      }
      used.assign(mid + 1, false);
      for (int i = 0; i <= mid; i++) {
        if (!used[i]) {
          dfs(i);
        }
      }
      bool good = true;
      for (int i = 0; i <= mid; i++) {
        for (int j : graph[i]) {
          if (tout[i] < tout[j]) {
            good = false;
          }
        }
      }
      if (good) {
        l = mid;
        answer.resize(mid);
        for (int i = 0; i < mid; i++) {
          answer[i] = tout[i + 1] - tout[i];
        }
      } else {
        r = mid;
      }
    }
    cout << l << "\n";
    for (int i = 0; i < l; i++) {
      cout << answer[i] << " \n"[i + 1 == l];
    }
  }
}

Subtask #1
6.0 / 6.0

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

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Ok
2 Correct 0 ms 348 KB Ok
3 Correct 0 ms 348 KB Ok
4 Correct 1 ms 344 KB Ok
5 Correct 0 ms 348 KB Ok
6 Correct 5 ms 600 KB Ok
7 Correct 24 ms 1996 KB Ok
8 Correct 18 ms 1216 KB Ok
9 Correct 27 ms 2384 KB Ok
10 Correct 19 ms 1472 KB Ok

Subtask #3
14.0 / 14.0

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

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Ok
2 Correct 0 ms 348 KB Ok
3 Correct 0 ms 456 KB Ok
4 Correct 0 ms 348 KB Ok
5 Correct 0 ms 348 KB Ok
6 Correct 232 ms 19272 KB Ok
7 Correct 222 ms 22744 KB Ok
8 Correct 445 ms 29596 KB Ok
9 Correct 303 ms 26924 KB Ok
10 Correct 168 ms 15176 KB Ok
11 Correct 275 ms 25684 KB Ok

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Ok
2 Correct 1 ms 348 KB Ok
3 Correct 0 ms 348 KB Ok
4 Correct 0 ms 348 KB Ok
5 Correct 0 ms 348 KB Ok
6 Correct 1 ms 348 KB Ok
7 Correct 0 ms 348 KB Ok
8 Correct 1 ms 348 KB Ok
9 Correct 0 ms 348 KB Ok
10 Correct 0 ms 348 KB Ok
11 Correct 0 ms 348 KB Ok
12 Correct 1 ms 348 KB Ok
13 Correct 1 ms 348 KB Ok
14 Correct 0 ms 348 KB Ok
15 Correct 1 ms 856 KB Ok
16 Correct 0 ms 348 KB Ok
17 Correct 0 ms 348 KB Ok
18 Correct 1 ms 348 KB Ok
19 Correct 0 ms 348 KB Ok
20 Correct 1 ms 348 KB Ok
21 Correct 0 ms 348 KB Ok
22 Correct 0 ms 348 KB Ok
23 Correct 1 ms 348 KB Ok
24 Correct 5 ms 856 KB Ok
25 Correct 4 ms 600 KB Ok
26 Correct 5 ms 604 KB Ok
27 Correct 4 ms 604 KB Ok
28 Correct 3 ms 548 KB Ok
29 Correct 4 ms 600 KB Ok
30 Correct 3 ms 604 KB Ok
31 Correct 4 ms 604 KB Ok
32 Correct 4 ms 604 KB Ok
33 Correct 4 ms 604 KB Ok
34 Correct 9 ms 964 KB Ok
35 Correct 9 ms 1116 KB Ok
36 Correct 9 ms 1116 KB Ok
37 Correct 9 ms 1056 KB Ok
38 Correct 9 ms 1116 KB Ok
39 Correct 9 ms 860 KB Ok
40 Correct 10 ms 1064 KB Ok
41 Correct 9 ms 856 KB Ok
42 Correct 9 ms 860 KB Ok
43 Correct 10 ms 1112 KB Ok

Subtask #6
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Ok
2 Correct 1 ms 348 KB Ok
3 Correct 0 ms 348 KB Ok
4 Correct 0 ms 348 KB Ok
5 Correct 0 ms 348 KB Ok
6 Correct 1 ms 348 KB Ok
7 Correct 0 ms 348 KB Ok
8 Correct 1 ms 348 KB Ok
9 Correct 0 ms 348 KB Ok
10 Correct 0 ms 348 KB Ok
11 Correct 0 ms 348 KB Ok
12 Correct 1 ms 348 KB Ok
13 Correct 0 ms 348 KB Ok
14 Correct 0 ms 348 KB Ok
15 Correct 0 ms 348 KB Ok
16 Correct 1 ms 344 KB Ok
17 Correct 0 ms 348 KB Ok
18 Correct 5 ms 600 KB Ok
19 Correct 24 ms 1996 KB Ok
20 Correct 18 ms 1216 KB Ok
21 Correct 27 ms 2384 KB Ok
22 Correct 19 ms 1472 KB Ok
23 Correct 1 ms 348 KB Ok
24 Correct 0 ms 348 KB Ok
25 Correct 1 ms 856 KB Ok
26 Correct 0 ms 348 KB Ok
27 Correct 0 ms 348 KB Ok
28 Correct 1 ms 348 KB Ok
29 Correct 0 ms 348 KB Ok
30 Correct 1 ms 348 KB Ok
31 Correct 0 ms 348 KB Ok
32 Correct 0 ms 348 KB Ok
33 Correct 1 ms 348 KB Ok
34 Correct 5 ms 856 KB Ok
35 Correct 4 ms 600 KB Ok
36 Correct 5 ms 604 KB Ok
37 Correct 4 ms 604 KB Ok
38 Correct 3 ms 548 KB Ok
39 Correct 4 ms 600 KB Ok
40 Correct 3 ms 604 KB Ok
41 Correct 4 ms 604 KB Ok
42 Correct 4 ms 604 KB Ok
43 Correct 4 ms 604 KB Ok
44 Correct 9 ms 964 KB Ok
45 Correct 9 ms 1116 KB Ok
46 Correct 9 ms 1116 KB Ok
47 Correct 9 ms 1056 KB Ok
48 Correct 9 ms 1116 KB Ok
49 Correct 9 ms 860 KB Ok
50 Correct 10 ms 1064 KB Ok
51 Correct 9 ms 856 KB Ok
52 Correct 9 ms 860 KB Ok
53 Correct 10 ms 1112 KB Ok
54 Correct 226 ms 8652 KB Ok
55 Correct 283 ms 9396 KB Ok
56 Correct 243 ms 8424 KB Ok
57 Correct 159 ms 8280 KB Ok
58 Correct 202 ms 8516 KB Ok
59 Correct 181 ms 9124 KB Ok
60 Correct 164 ms 7688 KB Ok
61 Correct 179 ms 8724 KB Ok
62 Correct 223 ms 9480 KB Ok
63 Correct 178 ms 7048 KB Ok
64 Correct 240 ms 8424 KB Ok
65 Correct 209 ms 8612 KB Ok
66 Correct 187 ms 8044 KB Ok
67 Correct 169 ms 8492 KB Ok
68 Correct 195 ms 10156 KB Ok
69 Correct 592 ms 17748 KB Ok
70 Correct 590 ms 18532 KB Ok
71 Correct 568 ms 18780 KB Ok
72 Correct 541 ms 17504 KB Ok
73 Correct 566 ms 17712 KB Ok
74 Correct 580 ms 17568 KB Ok
75 Correct 575 ms 16712 KB Ok
76 Correct 628 ms 17856 KB Ok
77 Correct 546 ms 19080 KB Ok
78 Correct 576 ms 18960 KB Ok
79 Correct 609 ms 20268 KB Ok
80 Correct 531 ms 18012 KB Ok
81 Correct 647 ms 17856 KB Ok
82 Correct 551 ms 17776 KB Ok
83 Correct 533 ms 17420 KB Ok

Subtask #7
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Ok
2 Correct 1 ms 348 KB Ok
3 Correct 0 ms 348 KB Ok
4 Correct 0 ms 348 KB Ok
5 Correct 0 ms 348 KB Ok
6 Correct 1 ms 348 KB Ok
7 Correct 0 ms 348 KB Ok
8 Correct 1 ms 348 KB Ok
9 Correct 0 ms 348 KB Ok
10 Correct 0 ms 348 KB Ok
11 Correct 0 ms 348 KB Ok
12 Correct 1 ms 348 KB Ok
13 Correct 0 ms 348 KB Ok
14 Correct 0 ms 348 KB Ok
15 Correct 0 ms 348 KB Ok
16 Correct 1 ms 344 KB Ok
17 Correct 0 ms 348 KB Ok
18 Correct 5 ms 600 KB Ok
19 Correct 24 ms 1996 KB Ok
20 Correct 18 ms 1216 KB Ok
21 Correct 27 ms 2384 KB Ok
22 Correct 19 ms 1472 KB Ok
23 Correct 1 ms 348 KB Ok
24 Correct 0 ms 348 KB Ok
25 Correct 1 ms 856 KB Ok
26 Correct 0 ms 348 KB Ok
27 Correct 0 ms 348 KB Ok
28 Correct 1 ms 348 KB Ok
29 Correct 0 ms 348 KB Ok
30 Correct 1 ms 348 KB Ok
31 Correct 0 ms 348 KB Ok
32 Correct 0 ms 348 KB Ok
33 Correct 1 ms 348 KB Ok
34 Correct 1 ms 348 KB Ok
35 Correct 0 ms 348 KB Ok
36 Correct 0 ms 456 KB Ok
37 Correct 0 ms 348 KB Ok
38 Correct 0 ms 348 KB Ok
39 Correct 232 ms 19272 KB Ok
40 Correct 222 ms 22744 KB Ok
41 Correct 445 ms 29596 KB Ok
42 Correct 303 ms 26924 KB Ok
43 Correct 168 ms 15176 KB Ok
44 Correct 275 ms 25684 KB Ok
45 Correct 5 ms 856 KB Ok
46 Correct 4 ms 600 KB Ok
47 Correct 5 ms 604 KB Ok
48 Correct 4 ms 604 KB Ok
49 Correct 3 ms 548 KB Ok
50 Correct 4 ms 600 KB Ok
51 Correct 3 ms 604 KB Ok
52 Correct 4 ms 604 KB Ok
53 Correct 4 ms 604 KB Ok
54 Correct 4 ms 604 KB Ok
55 Correct 9 ms 964 KB Ok
56 Correct 9 ms 1116 KB Ok
57 Correct 9 ms 1116 KB Ok
58 Correct 9 ms 1056 KB Ok
59 Correct 9 ms 1116 KB Ok
60 Correct 9 ms 860 KB Ok
61 Correct 10 ms 1064 KB Ok
62 Correct 9 ms 856 KB Ok
63 Correct 9 ms 860 KB Ok
64 Correct 10 ms 1112 KB Ok
65 Correct 226 ms 8652 KB Ok
66 Correct 283 ms 9396 KB Ok
67 Correct 243 ms 8424 KB Ok
68 Correct 159 ms 8280 KB Ok
69 Correct 202 ms 8516 KB Ok
70 Correct 181 ms 9124 KB Ok
71 Correct 164 ms 7688 KB Ok
72 Correct 179 ms 8724 KB Ok
73 Correct 223 ms 9480 KB Ok
74 Correct 178 ms 7048 KB Ok
75 Correct 240 ms 8424 KB Ok
76 Correct 209 ms 8612 KB Ok
77 Correct 187 ms 8044 KB Ok
78 Correct 169 ms 8492 KB Ok
79 Correct 195 ms 10156 KB Ok
80 Correct 592 ms 17748 KB Ok
81 Correct 590 ms 18532 KB Ok
82 Correct 568 ms 18780 KB Ok
83 Correct 541 ms 17504 KB Ok
84 Correct 566 ms 17712 KB Ok
85 Correct 580 ms 17568 KB Ok
86 Correct 575 ms 16712 KB Ok
87 Correct 628 ms 17856 KB Ok
88 Correct 546 ms 19080 KB Ok
89 Correct 576 ms 18960 KB Ok
90 Correct 609 ms 20268 KB Ok
91 Correct 531 ms 18012 KB Ok
92 Correct 647 ms 17856 KB Ok
93 Correct 551 ms 17776 KB Ok
94 Correct 533 ms 17420 KB Ok
95 Correct 560 ms 28512 KB Ok
96 Correct 792 ms 34612 KB Ok
97 Correct 728 ms 31624 KB Ok
98 Correct 527 ms 31616 KB Ok
99 Correct 635 ms 24428 KB Ok
100 Correct 646 ms 22564 KB Ok
101 Correct 706 ms 34772 KB Ok
102 Correct 677 ms 29572 KB Ok
103 Correct 665 ms 28448 KB Ok
104 Correct 828 ms 37648 KB Ok
105 Correct 779 ms 35272 KB Ok
106 Correct 708 ms 36000 KB Ok
107 Correct 705 ms 27960 KB Ok
108 Correct 821 ms 27968 KB Ok
109 Correct 781 ms 27848 KB Ok
110 Execution timed out 2024 ms 57988 KB Time limit exceeded
111 Halted 0 ms 0 KB -