# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
513594 | Killer2501 | Nice sequence (IZhO18_sequence) | C++14 | 1345 ms | 71112 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define ull unsigned long long
#define pb push_back
#define pll pair<ll, ll>
#define pii pair<int, int>
#define fi first
#define se second
using namespace std;
const int N = 5e5+5;
const int M = (1<<17);
const ll inf = 1e15;
const ll mod = 1e15+7;
int n, t, k, m, d[N], in[N], out[N];
ll ans, tong, a[N], b[N], c[N];
string s[N];
struct node
{
int x[2];
set<int> vi;
node(){}
node( int _x, int _y)
{
x[0] = _x;
x[1] = _y;
}
};
vector<node> q;
vector<int> adj[N], kq;
void dfs(int u)
{
a[u] = ++t;
if(u+m <= k && a[u+m] == 0)dfs(u+m);
if(u-n >= 0 && a[u-n] == 0)dfs(u-n);
}
bool check(int mid)
{
k = mid;
for(int i = 0; i <= k; i ++)adj[i].clear();
fill_n(a, k+1, 0);
t = 0;
for(int i = 0; i <= k; i ++)
{
if(i+m <= k)
{
adj[i].pb(i+m);
++a[i+m];
}
if(i >= n)
{
adj[i].pb(i-n);
++a[i-n];
}
}
queue<int> q;
for(int i = 0; i <= k; i ++)if(a[i] == 0)q.push(i);
while(!q.empty())
{
int u = q.front();
q.pop();
a[u] = ++t;
for(int v: adj[u])
{
--a[v];
if(a[v] == 0)q.push(v);
}
}
if(t == k+1)return true;
return false;
}
void sol()
{
cin >> n >> m;
ans = n+m-__gcd(m,n)-1;
check(ans);
cout << ans << '\n';
for(int i = 1; i <= ans; i ++)cout << a[i]-a[i-1] <<" ";
cout << '\n';
}
int main()
{
cin.tie(0);
cout.tie(0);
ios_base::sync_with_stdio(0);
#define task "test"
if(fopen(task".inp", "r"))
{
freopen(task".inp", "r", stdin);
freopen(task".out", "w", stdout);
}
int ntest = 1;
cin >> ntest;
while(ntest -- > 0)
sol();
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |