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>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
//#pragma GCC opimize(-O3)
//#pragma GCC opimize(Ofast)
//#pragma GCC opimize(unroll-loops)
//#pragma GCC target("avx,avx2,popcnt,sse,sse2,sse3,sse4,abm,tune=native")
#define m_p make_pair
#define vec vector
#define all(x) x.begin(),x.end()
#define pb push_back
#define sz(x) (int)x.size()
#define pw(x) (1LL<<x)
#define f first
#define s second
using namespace std;
using namespace __gnu_pbds;
typedef long double ld;
typedef pair<int,int> pii;
const int N=4e5+1;
int ok=1;
int used[N];
vec<int>g[N];
int pref[N];
vec<int>ord;
void dfs(int v){
used[v]=1;
for(auto &z : g[v]){
if(used[z]==1){
ok=0;
}
else if(!used[z]){
dfs(z);
}
}
used[v]=2;
}
void dfs1(int v){
used[v]=1;
for(auto &z : g[v]){
if(!used[z]){
dfs1(z);
}
}
ord.pb(v);
}
int getlen(int n,int m){
return n+m-__gcd(n,m)-1;
}
signed main()
{
ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int q=10;
scanf("%d",&q);
// cin>>q;
// ofstream cout("out.txt");
while(q--){
int n,m;
// n=199999;m=200000;
ord.clear();
scanf("%d%d",&n,&m);
int wow=getlen(n,m);
auto check=[&](int mid){
for(int i=0;i<=mid;i++) g[i].clear(),used[i]=0;
for(int i=0;i<=mid;i++){
if(i>=n){
g[i-n].pb(i);
}
if(i>=m){
g[i].pb(i-m);
}
}
ok=1;
for(int i=0;i<=mid;i++){
if(!used[i]){
dfs(i);
}
}
return ok;
};
int l=getlen(n,m)+1,r=l;
while(l!=r){
int tm=(l+r)>>1;
if(check(tm)){
l=tm+1;
}
else{
r=tm;
}
}
l--;
assert(l==wow);
for(int i=0;i<=l;i++) g[i].clear(),used[i]=0;
for(int i=0;i<=l;i++){
if(i>=n){
g[i-n].pb(i);
}
if(i>=m){
g[i].pb(i-m);
}
}
for(int i=0;i<=l;i++){
if(!used[i]){
dfs1(i);
}
}
// reverse(all(ord));
int i=1;
for(auto &z : ord) pref[z]=i++;
// cout<<l<<'\n';
printf("%d%c",l,'\n');
// cout<<l<<'\n';
for(int i=1;i<=l;i++){
// cout<<pref[i]-pref[i-1]<<' ';
printf("%d%c",pref[i]-pref[i-1],' ');
}
printf("%c",'\n');
// cout<<'\n';
}
return 0;
}
/*
5 1
1 1 2
1 3 5
3 2 3 1
2 1
3 0 3 1
*/
Compilation message (stderr)
sequence.cpp: In function 'int main()':
sequence.cpp:55:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
55 | scanf("%d",&q);
| ~~~~~^~~~~~~~~
sequence.cpp:62:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
62 | scanf("%d%d",&n,&m);
| ~~~~~^~~~~~~~~~~~~~
# | 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... |