#include<bits/stdc++.h>
using namespace std;
int a,b,c,d,e,lef,rig,mid,tes,t,n,m,i,j,p[500009],pi,pr[500009],ans[500009],pas,zx,xc;
int bo[500009],fls;
deque <int> de;
deque <int> v[500009];
void dfs(int q){
bo[q]=i;
pi++;
p[pi]=q;
for(int it=0; it<v[q].size(); it++){
if(bo[v[q][it]]==i){
fls=1;return;
}
if(bo[v[q][it]]==-1) dfs(v[q][it]);
if(fls==1) return;
}
}
int main(){
ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
cin>>tes;
// scanf("%d\n",&tes);
for(t=1; t<=tes; t++){
cin>>n>>m;
// scanf("%d %d\n",&n,&m);
lef=0;rig=400001;
pas=0;
// long long lonn=n,lonm=m;
// long long lon=lonn*lonm/__gcd(lonn,lonm),lonrg=rig;
// if(lonrg>lon) rig=lon;
/* if(rig==1){
// printf("0\n");
cout<<0<<endl;
continue;
}*/
// return 0;
while(1){
if(lef+1>=rig) break;
mid=(lef+rig)/2;
de.clear();
for(i=0; i<=mid+1; i++) v[i].clear();
for(i=0; i<=mid; i++){
pr[i]=0;bo[i]=-1;
}
for(i=1; i<=mid; i++){
if(i>=n) v[i-n].push_back(i);
if(i>=m) v[i].push_back(i-m);
}
fls=0;
for(i=0; i<=mid; i++){
if(bo[i]==-1){
pi=0;
dfs(i);
if(fls==1) break;
for(j=pi; j>=1; j--){
de.push_front(p[j]);
}
}
}
if(fls==1){
rig=mid;
continue;
}
de.push_front(-1);
for(i=1; i<de.size(); i++){
if(de[i]==0){
zx=i;break;
}
}
for(i=1; i<de.size(); i++){
pr[de[i]]=zx-i;
}
pas=mid;
for(i=1; i<=mid; i++){
ans[i]=pr[i]-pr[i-1];
}
lef=mid;
}
// printf("%d\n",pas);
cout<<pas<<endl;
for(i=1; i<pas; i++) /*printf("%d ",ans[i]);*/cout<<ans[i]<<" ";
if(pas!=0){
// printf("%d\n",ans[pas]);
cout<<ans[pas]<<endl;
}
}
return 0;
}
Compilation message
sequence.cpp: In function 'void dfs(int)':
sequence.cpp:11:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int it=0; it<v[q].size(); it++){
~~^~~~~~~~~~~~
sequence.cpp: In function 'int main()':
sequence.cpp:65:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(i=1; i<de.size(); i++){
~^~~~~~~~~~
sequence.cpp:70:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(i=1; i<de.size(); i++){
~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
224 ms |
262148 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
221 ms |
262148 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
221 ms |
262144 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
221 ms |
262144 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
224 ms |
262148 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
224 ms |
262148 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
224 ms |
262148 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
