# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1086399 | 8pete8 | Nice sequence (IZhO18_sequence) | C++17 | 143 ms | 28496 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<stdio.h>
#include <stdlib.h>
#define int long long
int compare(const void* a, const void* b){
return (*(int*)a - *(int*)b);
}
const int mx=1e9,mxn=2e5;
int k=0;
int *adj[mxn+10],sz[mxn+10],vis[mxn+10],ord[mxn+10],cnt=0;
int what[mxn+10];
void ts(int cur){
vis[cur]=1;
for(int i=0;i<sz[cur];i++)if(!vis[adj[cur][i]])ts(adj[cur][i]);
ord[cnt++]=cur;
}
void re(int m,int n){
//get length
k+=(m/n)*n;
if(m%n)re(n,m%n);
}
void solve(){
k=0,cnt=0;
int n,m;scanf("%lld %lld",&n,&m);
int mul=-1;
if(n>m){
n^=m,m^=n,n^=m;
mul=1;
}
re(m,n);
k--;
for(int i=0;i<=k;i++){
if(i-m>=0){
adj[i] = (int *)realloc(adj[i],(sz[i] + 1)*sizeof(int));
adj[i][sz[i]++]=i-m;
}
if(i-n>=0){
adj[i-n]=(int *)realloc(adj[i-n],(sz[i-n] + 1)*sizeof(int));
adj[i-n][sz[i-n]++]=i;
}
}
//get length
printf("%lld\n",k);
for(int i=0;i<=k;i++)if(!vis[i])ts(i);
for(int i=cnt;i>=0;i--)what[ord[i]]=(k-i);
for(int i=1;i<=k;i++)printf("%lld ",mul*(what[i]-what[i-1]));
for(int i=0;i<=k;i++){
if(adj[i]!=NULL)free(adj[i]);
adj[i]=NULL;
sz[i]=what[i]=vis[i]=0;
}
printf("\n");
}
int32_t main(){
int t;scanf("%lld",&t);
while(t--)solve();
}
/*
+++-
3
3 1
2 3
1 1
case
*/
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... |