Submission #1132987

#TimeUsernameProblemLanguageResultExecution timeMemory
1132987aykhnNice sequence (IZhO18_sequence)C++20
100 / 100
666 ms94168 KiB
#include <bits/stdc++.h>

using namespace std;

#define int long long
#define inf 0x3F3F3F3F3F3F3F3F

const int MXN = 1e6 + 5;

vector<int> adj[MXN];
int used[MXN];
vector<int> o;

void tp(int a)
{
  used[a] = 1;
  for (int &v : adj[a])
  {
    if (!used[v]) tp(v);
  }
  o.push_back(a);
}

void _()
{
  int x, y;
  cin >> x >> y;
  int res = 0, cur = 0;
  while (!(cur == 0 && res > 0))
  {
    int k = (y - cur + x - 1) / x;
    res = max(res, k * x + cur);
    cur = (cur + k * x) % y;
  }
  for (int i = 0; i < res; i++) adj[i].clear(), used[i] = 0;
  o.clear();
  for (int i = 0; i < res; i++)
  {
    if (i + x < res) adj[i + x].push_back(i);
    if (i + y < res) adj[i].push_back(i + y);
  }
  for (int i = 0; i < res; i++) 
  {
    if (!used[i]) tp(i);
  }
  reverse(o.begin(), o.end());
  int val[res];
  for (int i = 0; i < res; i++) val[o[i]] = i;
  for (int i = res - 1; i >= 1; i--) val[i] -= val[i - 1];
  cout << res - 1 << '\n';
  for (int i = 1; i < res; i++) cout << val[i] << ' ';
  cout << '\n';
}
signed main()
{
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int t;
  cin >> t;
  while (t--)
  {
    _();
  }
}

#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...