oj.uz

Submission #395441

# Submission time Handle Problem Language Result Execution time Memory
395441 2021-04-28T11:08:39 Z rama_pang Nice sequence (IZhO18_sequence) C++17
76 / 100
 2000 ms 48136 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)).

    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 lo = 0, hi = N + M;
    while (lo < hi) {
      int md = (lo + hi + 1) / 2;
      if (Calc(md)) {
        lo = md;
      } else {
        hi = md - 1;
      }
    }

    Calc(lo);
    cout << lo << '\n';
    for (int i = 1; i <= lo; i++) {
      cout << (P[i] - P[i - 1]) << " \n"[i == lo];
    }
  }
  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 332 KB Ok
4 Correct 1 ms 332 KB Ok
5 Correct 1 ms 320 KB Ok
6 Correct 1 ms 332 KB Ok
7 Correct 1 ms 332 KB Ok
8 Correct 1 ms 332 KB Ok
9 Correct 1 ms 332 KB Ok
10 Correct 1 ms 316 KB Ok
11 Correct 1 ms 332 KB Ok
12 Correct 1 ms 332 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 312 KB Ok
6 Correct 8 ms 600 KB Ok
7 Correct 39 ms 1796 KB Ok
8 Correct 17 ms 1004 KB Ok
9 Correct 48 ms 2100 KB Ok
10 Correct 25 ms 1300 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 208 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 204 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 312 KB Ok
4 Correct 1 ms 204 KB Ok
5 Correct 1 ms 204 KB Ok
6 Correct 610 ms 24688 KB Ok
7 Correct 464 ms 28416 KB Ok
8 Correct 918 ms 34880 KB Ok
9 Correct 665 ms 29408 KB Ok
10 Correct 422 ms 17256 KB Ok
11 Correct 725 ms 31716 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 332 KB Ok
4 Correct 1 ms 332 KB Ok
5 Correct 1 ms 320 KB Ok
6 Correct 1 ms 332 KB Ok
7 Correct 1 ms 332 KB Ok
8 Correct 1 ms 332 KB Ok
9 Correct 1 ms 332 KB Ok
10 Correct 1 ms 316 KB Ok
11 Correct 1 ms 332 KB Ok
12 Correct 1 ms 332 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 208 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 204 KB Ok
24 Correct 9 ms 588 KB Ok
25 Correct 8 ms 588 KB Ok
26 Correct 9 ms 588 KB Ok
27 Correct 8 ms 616 KB Ok
28 Correct 7 ms 588 KB Ok
29 Correct 7 ms 588 KB Ok
30 Correct 7 ms 464 KB Ok
31 Correct 8 ms 588 KB Ok
32 Correct 9 ms 588 KB Ok
33 Correct 8 ms 588 KB Ok
34 Correct 17 ms 936 KB Ok
35 Correct 17 ms 1016 KB Ok
36 Correct 17 ms 1020 KB Ok
37 Correct 17 ms 956 KB Ok
38 Correct 19 ms 1020 KB Ok
39 Correct 20 ms 980 KB Ok
40 Correct 18 ms 988 KB Ok
41 Correct 17 ms 924 KB Ok
42 Correct 18 ms 972 KB Ok
43 Correct 18 ms 972 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 332 KB Ok
4 Correct 1 ms 332 KB Ok
5 Correct 1 ms 320 KB Ok
6 Correct 1 ms 332 KB Ok
7 Correct 1 ms 332 KB Ok
8 Correct 1 ms 332 KB Ok
9 Correct 1 ms 332 KB Ok
10 Correct 1 ms 316 KB Ok
11 Correct 1 ms 332 KB Ok
12 Correct 1 ms 332 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 312 KB Ok
18 Correct 8 ms 600 KB Ok
19 Correct 39 ms 1796 KB Ok
20 Correct 17 ms 1004 KB Ok
21 Correct 48 ms 2100 KB Ok
22 Correct 25 ms 1300 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 208 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 204 KB Ok
34 Correct 9 ms 588 KB Ok
35 Correct 8 ms 588 KB Ok
36 Correct 9 ms 588 KB Ok
37 Correct 8 ms 616 KB Ok
38 Correct 7 ms 588 KB Ok
39 Correct 7 ms 588 KB Ok
40 Correct 7 ms 464 KB Ok
41 Correct 8 ms 588 KB Ok
42 Correct 9 ms 588 KB Ok
43 Correct 8 ms 588 KB Ok
44 Correct 17 ms 936 KB Ok
45 Correct 17 ms 1016 KB Ok
46 Correct 17 ms 1020 KB Ok
47 Correct 17 ms 956 KB Ok
48 Correct 19 ms 1020 KB Ok
49 Correct 20 ms 980 KB Ok
50 Correct 18 ms 988 KB Ok
51 Correct 17 ms 924 KB Ok
52 Correct 18 ms 972 KB Ok
53 Correct 18 ms 972 KB Ok
54 Correct 379 ms 9500 KB Ok
55 Correct 430 ms 10144 KB Ok
56 Correct 429 ms 10056 KB Ok
57 Correct 327 ms 8788 KB Ok
58 Correct 419 ms 9928 KB Ok
59 Correct 400 ms 9768 KB Ok
60 Correct 347 ms 8988 KB Ok
61 Correct 324 ms 9408 KB Ok
62 Correct 466 ms 10312 KB Ok
63 Correct 384 ms 9012 KB Ok
64 Correct 460 ms 9956 KB Ok
65 Correct 417 ms 9928 KB Ok
66 Correct 387 ms 9468 KB Ok
67 Correct 336 ms 10640 KB Ok
68 Correct 414 ms 9748 KB Ok
69 Correct 1276 ms 20416 KB Ok
70 Correct 1178 ms 20860 KB Ok
71 Correct 1113 ms 20464 KB Ok
72 Correct 1082 ms 20220 KB Ok
73 Correct 1500 ms 20464 KB Ok
74 Correct 1285 ms 20204 KB Ok
75 Correct 1176 ms 20360 KB Ok
76 Correct 1267 ms 20572 KB Ok
77 Correct 1230 ms 20320 KB Ok
78 Correct 1248 ms 20360 KB Ok
79 Correct 1264 ms 20644 KB Ok
80 Correct 1123 ms 20304 KB Ok
81 Correct 959 ms 20756 KB Ok
82 Correct 1244 ms 20504 KB Ok
83 Correct 1122 ms 20516 KB Ok

Subtask #7
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 332 KB Ok
4 Correct 1 ms 332 KB Ok
5 Correct 1 ms 320 KB Ok
6 Correct 1 ms 332 KB Ok
7 Correct 1 ms 332 KB Ok
8 Correct 1 ms 332 KB Ok
9 Correct 1 ms 332 KB Ok
10 Correct 1 ms 316 KB Ok
11 Correct 1 ms 332 KB Ok
12 Correct 1 ms 332 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 312 KB Ok
18 Correct 8 ms 600 KB Ok
19 Correct 39 ms 1796 KB Ok
20 Correct 17 ms 1004 KB Ok
21 Correct 48 ms 2100 KB Ok
22 Correct 25 ms 1300 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 208 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 204 KB Ok
34 Correct 1 ms 204 KB Ok
35 Correct 1 ms 204 KB Ok
36 Correct 1 ms 312 KB Ok
37 Correct 1 ms 204 KB Ok
38 Correct 1 ms 204 KB Ok
39 Correct 610 ms 24688 KB Ok
40 Correct 464 ms 28416 KB Ok
41 Correct 918 ms 34880 KB Ok
42 Correct 665 ms 29408 KB Ok
43 Correct 422 ms 17256 KB Ok
44 Correct 725 ms 31716 KB Ok
45 Correct 9 ms 588 KB Ok
46 Correct 8 ms 588 KB Ok
47 Correct 9 ms 588 KB Ok
48 Correct 8 ms 616 KB Ok
49 Correct 7 ms 588 KB Ok
50 Correct 7 ms 588 KB Ok
51 Correct 7 ms 464 KB Ok
52 Correct 8 ms 588 KB Ok
53 Correct 9 ms 588 KB Ok
54 Correct 8 ms 588 KB Ok
55 Correct 17 ms 936 KB Ok
56 Correct 17 ms 1016 KB Ok
57 Correct 17 ms 1020 KB Ok
58 Correct 17 ms 956 KB Ok
59 Correct 19 ms 1020 KB Ok
60 Correct 20 ms 980 KB Ok
61 Correct 18 ms 988 KB Ok
62 Correct 17 ms 924 KB Ok
63 Correct 18 ms 972 KB Ok
64 Correct 18 ms 972 KB Ok
65 Correct 379 ms 9500 KB Ok
66 Correct 430 ms 10144 KB Ok
67 Correct 429 ms 10056 KB Ok
68 Correct 327 ms 8788 KB Ok
69 Correct 419 ms 9928 KB Ok
70 Correct 400 ms 9768 KB Ok
71 Correct 347 ms 8988 KB Ok
72 Correct 324 ms 9408 KB Ok
73 Correct 466 ms 10312 KB Ok
74 Correct 384 ms 9012 KB Ok
75 Correct 460 ms 9956 KB Ok
76 Correct 417 ms 9928 KB Ok
77 Correct 387 ms 9468 KB Ok
78 Correct 336 ms 10640 KB Ok
79 Correct 414 ms 9748 KB Ok
80 Correct 1276 ms 20416 KB Ok
81 Correct 1178 ms 20860 KB Ok
82 Correct 1113 ms 20464 KB Ok
83 Correct 1082 ms 20220 KB Ok
84 Correct 1500 ms 20464 KB Ok
85 Correct 1285 ms 20204 KB Ok
86 Correct 1176 ms 20360 KB Ok
87 Correct 1267 ms 20572 KB Ok
88 Correct 1230 ms 20320 KB Ok
89 Correct 1248 ms 20360 KB Ok
90 Correct 1264 ms 20644 KB Ok
91 Correct 1123 ms 20304 KB Ok
92 Correct 959 ms 20756 KB Ok
93 Correct 1244 ms 20504 KB Ok
94 Correct 1122 ms 20516 KB Ok
95 Correct 1170 ms 28020 KB Ok
96 Correct 1701 ms 37100 KB Ok
97 Correct 1601 ms 33176 KB Ok
98 Correct 1208 ms 35572 KB Ok
99 Correct 1347 ms 29432 KB Ok
100 Correct 1470 ms 30372 KB Ok
101 Correct 1423 ms 34980 KB Ok
102 Correct 1444 ms 34840 KB Ok
103 Correct 1495 ms 30996 KB Ok
104 Correct 1746 ms 36036 KB Ok
105 Correct 1600 ms 36024 KB Ok
106 Correct 1417 ms 32324 KB Ok
107 Correct 1605 ms 33916 KB Ok
108 Correct 1727 ms 35516 KB Ok
109 Correct 1527 ms 34292 KB Ok
110 Execution timed out 2041 ms 48136 KB Time limit exceeded
111 Halted 0 ms 0 KB -