oj.uz

Submission #395448

# Submission time Handle Problem Language Result Execution time Memory
395448 2021-04-28T11:15:26 Z rama_pang Nice sequence (IZhO18_sequence) C++17
100 / 100
 1750 ms 82596 KB 
#include <bits/stdc++.h>
using namespace std;

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

  int T;
  cin >> T;
  while (T--) {
    int N, M;
    cin >> N >> M;

    // Let P[] be the prefix sum of A[]. In particular,
    // P[0] = 0, P[1] = A[1], P[2] = A[1] + A[2], ...
    //
    // P[] can be arbitary since A[] can be arbitary.
    // The condition is:
    // P[i + N] - P[i] < 0 -> P[i + N] < P[i]
    // P[i + M] - P[i] > 0 -> P[i + M] > P[i].
    // We draw an edge x -> y if P[x] < P[y]. Then, if there
    // is a strongly connected component, that particular size
    // is invalid.
    //
    // Now, note that if size >= N + M, there is a cycle. Proof:
    // WLOG, assume N <= M. Then, P[i] < P[i + M] and P[i] < P[i - N].
    // We start from node = 0, then node += M, then decrease by N until
    // node = (node_prv) % N. We do this again, and again. Note that
    // the maximum index is <= N + M, and eventually we will arrive back
    // at 0, since we form a cycle at modulo N.
    //
    // We can binary search for the answer, checking whether the graph
    // is a DAG or not. Time complexity: O((N + M) log (N + M)). This
    // yields 76 points.
    //
    // Can we get a tight bound? Consider the process, of +M and -N.
    // We can actually simulate this process pretty easily without DFS.
    // Time complexity: O(N + M).

    vector<int> P(N + M + 1);
    vector<vector<int>> adj(N + M + 1);
    for (int i = 0; i <= N + M; i++) {
      if (i <= N) adj[i].emplace_back(i + M);
      if (i >= N) adj[i].emplace_back(i - N);
    }

    vector<int> topo;
    vector<int> vis(N + M + 1);
    vector<int> pos_in_topo(N + M + 1);
    const auto Calc = [&](int sz) -> bool {
      topo.clear();
      fill(begin(vis), end(vis), 0);

      const auto Dfs = [&](const auto &self, int u) -> void {
        vis[u] = 1;
        for (auto v : adj[u]) if (v <= sz && !vis[v]) self(self, v);
        topo.emplace_back(u);
      };
      for (int i = 0; i <= sz; i++) if (!vis[i]) {
        Dfs(Dfs, i);
      }

      reverse(begin(topo), end(topo));
      for (int i = 0; i <= sz; i++) {
        pos_in_topo[topo[i]] = i;
      }
      for (int i = 0; i <= sz; i++) {
        for (auto j : adj[i]) if (j <= sz) {
          if (pos_in_topo[j] < pos_in_topo[i]) {
            return false;
          }
        }
      }

      for (int i = 0; i <= sz; i++) P[topo[i]] = i;
      for (int i = sz; i >= 0; i--) P[i] -= P[0];

      return true;
    };

    int ans = 0;
    int node = 0;
    fill(begin(vis), end(vis), 0);
    while (!vis[node]) {
      vis[node] = 1;
      ans = max(ans, node);
      if (node >= N) {
        node -= N;
      } else {
        node += M;
      }
    }

    ans--;
    assert(node == 0);

    Calc(ans);
    cout << ans << '\n';
    for (int i = 1; i <= ans; i++) {
      cout << (P[i] - P[i - 1]) << " \n"[i == ans];
    }
  }
  return 0;
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Ok
2 Correct 1 ms 332 KB Ok
3 Correct 1 ms 284 KB Ok
4 Correct 1 ms 332 KB Ok
5 Correct 1 ms 332 KB Ok
6 Correct 1 ms 332 KB Ok
7 Correct 1 ms 320 KB Ok
8 Correct 1 ms 332 KB Ok
9 Correct 1 ms 332 KB Ok
10 Correct 1 ms 332 KB Ok
11 Correct 1 ms 332 KB Ok
12 Correct 1 ms 320 KB Ok

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Ok
2 Correct 1 ms 204 KB Ok
3 Correct 1 ms 204 KB Ok
4 Correct 1 ms 204 KB Ok
5 Correct 1 ms 316 KB Ok
6 Correct 4 ms 460 KB Ok
7 Correct 16 ms 1668 KB Ok
8 Correct 8 ms 844 KB Ok
9 Correct 19 ms 1816 KB Ok
10 Correct 14 ms 1176 KB Ok

Subtask #3
14.0 / 14.0

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

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Ok
2 Correct 1 ms 204 KB Ok
3 Correct 1 ms 332 KB Ok
4 Correct 1 ms 204 KB Ok
5 Correct 1 ms 204 KB Ok
6 Correct 167 ms 24676 KB Ok
7 Correct 137 ms 22820 KB Ok
8 Correct 262 ms 33180 KB Ok
9 Correct 203 ms 24156 KB Ok
10 Correct 133 ms 17152 KB Ok
11 Correct 242 ms 31724 KB Ok

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Ok
2 Correct 1 ms 332 KB Ok
3 Correct 1 ms 284 KB Ok
4 Correct 1 ms 332 KB Ok
5 Correct 1 ms 332 KB Ok
6 Correct 1 ms 332 KB Ok
7 Correct 1 ms 320 KB Ok
8 Correct 1 ms 332 KB Ok
9 Correct 1 ms 332 KB Ok
10 Correct 1 ms 332 KB Ok
11 Correct 1 ms 332 KB Ok
12 Correct 1 ms 320 KB Ok
13 Correct 1 ms 204 KB Ok
14 Correct 1 ms 204 KB Ok
15 Correct 1 ms 204 KB Ok
16 Correct 1 ms 204 KB Ok
17 Correct 1 ms 204 KB Ok
18 Correct 1 ms 204 KB Ok
19 Correct 1 ms 204 KB Ok
20 Correct 1 ms 204 KB Ok
21 Correct 1 ms 204 KB Ok
22 Correct 1 ms 204 KB Ok
23 Correct 1 ms 316 KB Ok
24 Correct 5 ms 588 KB Ok
25 Correct 5 ms 572 KB Ok
26 Correct 4 ms 592 KB Ok
27 Correct 4 ms 588 KB Ok
28 Correct 4 ms 564 KB Ok
29 Correct 4 ms 588 KB Ok
30 Correct 4 ms 460 KB Ok
31 Correct 6 ms 588 KB Ok
32 Correct 4 ms 572 KB Ok
33 Correct 4 ms 588 KB Ok
34 Correct 9 ms 972 KB Ok
35 Correct 7 ms 972 KB Ok
36 Correct 7 ms 972 KB Ok
37 Correct 8 ms 844 KB Ok
38 Correct 7 ms 928 KB Ok
39 Correct 7 ms 844 KB Ok
40 Correct 8 ms 936 KB Ok
41 Correct 9 ms 876 KB Ok
42 Correct 8 ms 972 KB Ok
43 Correct 7 ms 976 KB Ok

Subtask #6
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Ok
2 Correct 1 ms 332 KB Ok
3 Correct 1 ms 284 KB Ok
4 Correct 1 ms 332 KB Ok
5 Correct 1 ms 332 KB Ok
6 Correct 1 ms 332 KB Ok
7 Correct 1 ms 320 KB Ok
8 Correct 1 ms 332 KB Ok
9 Correct 1 ms 332 KB Ok
10 Correct 1 ms 332 KB Ok
11 Correct 1 ms 332 KB Ok
12 Correct 1 ms 320 KB Ok
13 Correct 1 ms 204 KB Ok
14 Correct 1 ms 204 KB Ok
15 Correct 1 ms 204 KB Ok
16 Correct 1 ms 204 KB Ok
17 Correct 1 ms 316 KB Ok
18 Correct 4 ms 460 KB Ok
19 Correct 16 ms 1668 KB Ok
20 Correct 8 ms 844 KB Ok
21 Correct 19 ms 1816 KB Ok
22 Correct 14 ms 1176 KB Ok
23 Correct 1 ms 204 KB Ok
24 Correct 1 ms 204 KB Ok
25 Correct 1 ms 204 KB Ok
26 Correct 1 ms 204 KB Ok
27 Correct 1 ms 204 KB Ok
28 Correct 1 ms 204 KB Ok
29 Correct 1 ms 204 KB Ok
30 Correct 1 ms 204 KB Ok
31 Correct 1 ms 204 KB Ok
32 Correct 1 ms 204 KB Ok
33 Correct 1 ms 316 KB Ok
34 Correct 5 ms 588 KB Ok
35 Correct 5 ms 572 KB Ok
36 Correct 4 ms 592 KB Ok
37 Correct 4 ms 588 KB Ok
38 Correct 4 ms 564 KB Ok
39 Correct 4 ms 588 KB Ok
40 Correct 4 ms 460 KB Ok
41 Correct 6 ms 588 KB Ok
42 Correct 4 ms 572 KB Ok
43 Correct 4 ms 588 KB Ok
44 Correct 9 ms 972 KB Ok
45 Correct 7 ms 972 KB Ok
46 Correct 7 ms 972 KB Ok
47 Correct 8 ms 844 KB Ok
48 Correct 7 ms 928 KB Ok
49 Correct 7 ms 844 KB Ok
50 Correct 8 ms 936 KB Ok
51 Correct 9 ms 876 KB Ok
52 Correct 8 ms 972 KB Ok
53 Correct 7 ms 976 KB Ok
54 Correct 131 ms 9504 KB Ok
55 Correct 143 ms 10124 KB Ok
56 Correct 154 ms 10088 KB Ok
57 Correct 117 ms 8776 KB Ok
58 Correct 160 ms 9840 KB Ok
59 Correct 141 ms 9660 KB Ok
60 Correct 126 ms 8916 KB Ok
61 Correct 125 ms 9560 KB Ok
62 Correct 149 ms 10304 KB Ok
63 Correct 126 ms 9008 KB Ok
64 Correct 141 ms 9832 KB Ok
65 Correct 149 ms 9808 KB Ok
66 Correct 139 ms 9460 KB Ok
67 Correct 118 ms 10644 KB Ok
68 Correct 142 ms 9588 KB Ok
69 Correct 290 ms 20052 KB Ok
70 Correct 333 ms 19828 KB Ok
71 Correct 279 ms 17140 KB Ok
72 Correct 299 ms 20168 KB Ok
73 Correct 352 ms 17384 KB Ok
74 Correct 293 ms 18864 KB Ok
75 Correct 287 ms 19668 KB Ok
76 Correct 339 ms 20008 KB Ok
77 Correct 276 ms 18388 KB Ok
78 Correct 367 ms 20180 KB Ok
79 Correct 301 ms 18904 KB Ok
80 Correct 261 ms 17368 KB Ok
81 Correct 304 ms 19992 KB Ok
82 Correct 278 ms 19040 KB Ok
83 Correct 287 ms 20176 KB Ok

Subtask #7
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Ok
2 Correct 1 ms 332 KB Ok
3 Correct 1 ms 284 KB Ok
4 Correct 1 ms 332 KB Ok
5 Correct 1 ms 332 KB Ok
6 Correct 1 ms 332 KB Ok
7 Correct 1 ms 320 KB Ok
8 Correct 1 ms 332 KB Ok
9 Correct 1 ms 332 KB Ok
10 Correct 1 ms 332 KB Ok
11 Correct 1 ms 332 KB Ok
12 Correct 1 ms 320 KB Ok
13 Correct 1 ms 204 KB Ok
14 Correct 1 ms 204 KB Ok
15 Correct 1 ms 204 KB Ok
16 Correct 1 ms 204 KB Ok
17 Correct 1 ms 316 KB Ok
18 Correct 4 ms 460 KB Ok
19 Correct 16 ms 1668 KB Ok
20 Correct 8 ms 844 KB Ok
21 Correct 19 ms 1816 KB Ok
22 Correct 14 ms 1176 KB Ok
23 Correct 1 ms 204 KB Ok
24 Correct 1 ms 204 KB Ok
25 Correct 1 ms 204 KB Ok
26 Correct 1 ms 204 KB Ok
27 Correct 1 ms 204 KB Ok
28 Correct 1 ms 204 KB Ok
29 Correct 1 ms 204 KB Ok
30 Correct 1 ms 204 KB Ok
31 Correct 1 ms 204 KB Ok
32 Correct 1 ms 204 KB Ok
33 Correct 1 ms 316 KB Ok
34 Correct 1 ms 204 KB Ok
35 Correct 1 ms 204 KB Ok
36 Correct 1 ms 332 KB Ok
37 Correct 1 ms 204 KB Ok
38 Correct 1 ms 204 KB Ok
39 Correct 167 ms 24676 KB Ok
40 Correct 137 ms 22820 KB Ok
41 Correct 262 ms 33180 KB Ok
42 Correct 203 ms 24156 KB Ok
43 Correct 133 ms 17152 KB Ok
44 Correct 242 ms 31724 KB Ok
45 Correct 5 ms 588 KB Ok
46 Correct 5 ms 572 KB Ok
47 Correct 4 ms 592 KB Ok
48 Correct 4 ms 588 KB Ok
49 Correct 4 ms 564 KB Ok
50 Correct 4 ms 588 KB Ok
51 Correct 4 ms 460 KB Ok
52 Correct 6 ms 588 KB Ok
53 Correct 4 ms 572 KB Ok
54 Correct 4 ms 588 KB Ok
55 Correct 9 ms 972 KB Ok
56 Correct 7 ms 972 KB Ok
57 Correct 7 ms 972 KB Ok
58 Correct 8 ms 844 KB Ok
59 Correct 7 ms 928 KB Ok
60 Correct 7 ms 844 KB Ok
61 Correct 8 ms 936 KB Ok
62 Correct 9 ms 876 KB Ok
63 Correct 8 ms 972 KB Ok
64 Correct 7 ms 976 KB Ok
65 Correct 131 ms 9504 KB Ok
66 Correct 143 ms 10124 KB Ok
67 Correct 154 ms 10088 KB Ok
68 Correct 117 ms 8776 KB Ok
69 Correct 160 ms 9840 KB Ok
70 Correct 141 ms 9660 KB Ok
71 Correct 126 ms 8916 KB Ok
72 Correct 125 ms 9560 KB Ok
73 Correct 149 ms 10304 KB Ok
74 Correct 126 ms 9008 KB Ok
75 Correct 141 ms 9832 KB Ok
76 Correct 149 ms 9808 KB Ok
77 Correct 139 ms 9460 KB Ok
78 Correct 118 ms 10644 KB Ok
79 Correct 142 ms 9588 KB Ok
80 Correct 290 ms 20052 KB Ok
81 Correct 333 ms 19828 KB Ok
82 Correct 279 ms 17140 KB Ok
83 Correct 299 ms 20168 KB Ok
84 Correct 352 ms 17384 KB Ok
85 Correct 293 ms 18864 KB Ok
86 Correct 287 ms 19668 KB Ok
87 Correct 339 ms 20008 KB Ok
88 Correct 276 ms 18388 KB Ok
89 Correct 367 ms 20180 KB Ok
90 Correct 301 ms 18904 KB Ok
91 Correct 261 ms 17368 KB Ok
92 Correct 304 ms 19992 KB Ok
93 Correct 278 ms 19040 KB Ok
94 Correct 287 ms 20176 KB Ok
95 Correct 358 ms 27760 KB Ok
96 Correct 489 ms 37064 KB Ok
97 Correct 459 ms 33272 KB Ok
98 Correct 382 ms 35564 KB Ok
99 Correct 417 ms 28764 KB Ok
100 Correct 426 ms 30236 KB Ok
101 Correct 443 ms 34852 KB Ok
102 Correct 430 ms 34820 KB Ok
103 Correct 435 ms 30900 KB Ok
104 Correct 490 ms 36156 KB Ok
105 Correct 460 ms 36012 KB Ok
106 Correct 430 ms 32424 KB Ok
107 Correct 473 ms 33988 KB Ok
108 Correct 483 ms 35480 KB Ok
109 Correct 486 ms 34396 KB Ok
110 Correct 1487 ms 81656 KB Ok
111 Correct 1695 ms 82104 KB Ok
112 Correct 1624 ms 72896 KB Ok
113 Correct 1366 ms 81168 KB Ok
114 Correct 1534 ms 71188 KB Ok
115 Correct 1646 ms 81896 KB Ok
116 Correct 1663 ms 80244 KB Ok
117 Correct 1688 ms 82128 KB Ok
118 Correct 1639 ms 69464 KB Ok
119 Correct 1750 ms 81112 KB Ok
120 Correct 1610 ms 82596 KB Ok
121 Correct 1604 ms 77716 KB Ok
122 Correct 1618 ms 81448 KB Ok
123 Correct 1728 ms 77440 KB Ok
124 Correct 1595 ms 71800 KB Ok
125 Correct 760 ms 65604 KB Ok