Submission #1132987

#	Time	Username	Problem	Language	Result	Execution time	Memory
1132987		aykhn	Nice sequence (IZhO18_sequence)	C++20	100 / 100	666 ms	94168 KiB

sequence

#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--)
  {
    _();
  }
}

• 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