Submission #395448

#	Time	Username	Problem	Language	Result	Execution time	Memory
395448		rama_pang	Nice sequence (IZhO18_sequence)	C++17	100 / 100	1750 ms	82596 KiB

sequence

#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 / 6
• Subtask 2: 9 / 9
• Subtask 3: 14 / 14
• Subtask 4: 15 / 15
• Subtask 5: 14 / 14
• Subtask 6: 18 / 18
• Subtask 7: 24 / 24