Submission #993150

#	Time	Username	Problem	Language	Result	Execution time	Memory
993150		tch1cherin	Nice sequence (IZhO18_sequence)	C++17	100 / 100	965 ms	52696 KiB

sequence

#include <bits/stdc++.h>
using namespace std;
 
vector<bool> used;
vector<int> tout;
int T = 0;
 
void dfs(int u, int N, int M) {
  used[u] = true;
  if (u - M >= 0 && !used[u - M]) {
    dfs(u - M, N, M);
  }
  if (u + N < (int)used.size() && !used[u + N]) {
    dfs(u + N, N, M);
  }
  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;
      used.assign(mid + 1, false);
      tout.resize(mid + 1);
      used.assign(mid + 1, false);
      for (int i = 0; i <= mid; i++) {
        if (!used[i]) {
          dfs(i, N, M);
        }
      }
      bool good = true;
      for (int i = 0; i <= mid; i++) {
        if (i + N <= mid && tout[i + N] > tout[i]) {
          good = false;
        }
        if (i - M >= 0 && tout[i - M] > tout[i]) {
          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: 24 / 24