oj.uz

Submission #395439

# Submission time Handle Problem Language Result Execution time Memory
395439 2021-04-28T11:05:30 Z rama_pang Nice sequence (IZhO18_sequence) C++17
0 / 100
 1 ms 460 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);
    }
    const auto Calc = [&](int sz) -> bool {
      static vector<int> topo; topo.clear();
      static vector<int> vis(N + M + 1, 0); 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));
      static vector<int> pos_in_topo(N + M + 1);
      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
0 / 6.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 460 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 460 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Ok
2 Runtime error 1 ms 332 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 460 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #5
0 / 14.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 460 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #6
0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 460 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #7
0 / 24.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 460 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -