Submission #1203709

#TimeUsernameProblemLanguageResultExecution timeMemory
1203709repmannNice sequence (IZhO18_sequence)C++20
100 / 100
581 ms53104 KiB
#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;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...