Submission #1203709

#	Time	Username	Problem	Language	Result	Execution time	Memory
1203709		repmann	Nice sequence (IZhO18_sequence)	C++20	100 / 100	581 ms	53104 KiB

sequence

#include <bits/stdc++.h>
#define ll long long
using namespace std;
int T, N, M, K;
int IN[400096], D[400096];
vector <int> VG[400096];
inline int GCD(int X, int Y)
{
  if(!Y) return X;
  return GCD(Y, X % Y);
}
inline void Topological()
{
  for(int i = 0; i <= K; i++) IN[i] = 0;
  for(int i = 0; i <= K; i++) for(int x : VG[i]) IN[x]++;
  queue <int> Q;
  int node, counter = 0;
  for(int i = 0; i <= K; i++) if(!IN[i]) Q.push(i);
  while(Q.size())
  {
    node = Q.front();
    D[node] = ++counter;
    for(int x : VG[node])
    {
      IN[x]--;
      if(!IN[x]) Q.push(x);
    }
    Q.pop();
  }
  return;
}
inline void Solve()
{
  cin >> N >> M;
  K = N + M - GCD(N, M) - 1;
  for(int i = 0; i <= K; i++) VG[i] = vector <int>();
  for(int i = N; i <= K; i++) VG[i].push_back(i - N);
  for(int i = M; i <= K; i++) VG[i - M].push_back(i);
  Topological();
  cout << K << '\n';
  for(int i = 1; i <= K; i++) cout << D[i] - D[i - 1] << " \n"[i == K];
  return;
}
int main()
{
  ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  cin >> T;
  while(T--) Solve();

  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