Submission #993138

#	Time	Username	Problem	Language	Result	Execution time	Memory
993138		tch1cherin	Nice sequence (IZhO18_sequence)	C++17	76 / 100	2024 ms	57988 KiB

sequence

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