Submission #1086399

#	Time	Username	Problem	Language	Result	Execution time	Memory
1086399		8pete8	Nice sequence (IZhO18_sequence)	C++17	76 / 100	143 ms	28496 KiB

sequence

#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)

sequence.cpp: In function 'void solve()':
sequence.cpp:23:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   23 |     int n,m;scanf("%lld %lld",&n,&m);
      |             ~~~~~^~~~~~~~~~~~~~~~~~~
sequence.cpp: In function 'int32_t main()':
sequence.cpp:54:16: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   54 |     int t;scanf("%lld",&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: 0 / 24