제출 #1191124

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1191124		lopkus	Nice sequence (IZhO18_sequence)	C++20	0 / 100	17 ms	13640 KiB

sequence

#include <bits/stdc++.h>

const int N = 3e5 + 5;

std::vector<std::vector<int>> adj(N);
std::vector<int> was(N, 1);
std::vector<int> in(N);
std::vector<int64_t> pref(N);


void solve() {
  int n, m;
  std::cin >> n >> m;
  int l = 1, r = 1e5, ans = 0;
  while(l <= r) {
    int mid = (l + r) / 2;
    int64_t t = 0;
    for(int i = 1; i + n - 1 <= mid; i++) {
      adj[i + n - 1].push_back(i - 1);
      in[i - 1] += 1;
    }
    for(int i = 1; i + m - 1 <= mid; i++) {
      adj[i - 1].push_back(i + m - 1);
      in[i + m - 1] += 1;
    }
    std::queue<int> Q;
    for(int i = 0; i <= mid; i++) {
      if(in[i] == 0) {
        Q.push(i);
      }
    }
    int cycle = 0;
    while(!Q.empty()) {
      int now = (Q.front());
      was[now] = 0;
      pref[now] = ++t;
      Q.pop();
      for(auto u : adj[now]) {
        in[u]--;
        if(in[u] == 0) {
          Q.push(u);
        }
      }
    }
    for(int i = 0; i <= mid; i++) {
      cycle |= was[i];
    }
    if(cycle) {
      r = mid - 1;
    }
    else {
      l = mid + 1;
      ans = mid;
    }
    for(int i = 0; i <= mid; i++) {
      adj[i].clear();
      was[i] = 1;
      in[i] = 0;
    }
  }
  std::cout << ans << "\n";
  for(int i = 1; i <= ans; i++) {
    std::cout << (pref[i] - pref[i - 1] == 0 ? 1 : pref[i] - pref[i - 1]) << " ";
  }
  std::cout << "\n";
}

signed main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);

  int t = 1;
  std::cin >> t;
  while (t--) {
      solve();
  }

  return 0;
}

• Subtask 1: 0 / 6
• Subtask 2: 0 / 9
• Subtask 3: 0 / 14
• Subtask 4: 0 / 15
• Subtask 5: 0 / 14
• Subtask 6: 0 / 18
• Subtask 7: 0 / 24