Submission #173125

#	Time	Username	Problem	Language	Result	Execution time	Memory
173125		mosiashvililuka	Nice sequence (IZhO18_sequence)	C++14	100 / 100	1829 ms	40260 KiB

sequence

#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,it,deq;
int bo[500009],fls;
int de[500009];
void dfs(int q){
    bo[q]=i;
    pi++;
    p[pi]=q;
    if(q+n<=mid){
        it=q+n;
        if(bo[it]==i){
            fls=1;return;
        }
        if(bo[it]==-1) dfs(it);
        if(fls==1) return;
    }
    if(q>=m){
        it=q-m;
        if(bo[it]==i){
            fls=1;return;
        }
        if(bo[it]==-1) dfs(it);
        if(fls==1) return;
    }
}
int main(){
    scanf("%d\n",&tes);
    for(t=1; t<=tes; t++){
        scanf("%d%d\n",&n,&m);
        lef=0;rig=400001;
        pas=0;
        while(1){
            if(lef+1>=rig) break;
            mid=(lef+rig)/2;
            deq=0;
            for(i=0; i<=mid; i++){
                pr[i]=0;bo[i]=-1;
            }
            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--){
                        deq++;
                        de[deq]=p[j];
                    }
                }
            }
            if(fls==1){
                rig=mid;
                continue;
            }
            for(i=1; i<=deq/2; i++){
                swap(de[i],de[deq-i+1]);
            }
            for(i=1; i<=deq; i++){
                if(de[i]==0){
                    zx=i;break;
                }
            }
            for(i=1; i<=deq; 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);
        for(i=1; i<pas; i++) printf("%d ",ans[i]);/*cout<<ans[i]<<" ";*/
        if(pas!=0){
            printf("%d\n",ans[pas]);
        }
    }
    return 0;
}

Compilation message (stderr)

sequence.cpp: In function 'int main()':
sequence.cpp:28:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d\n",&tes);
     ~~~~~^~~~~~~~~~~~~
sequence.cpp:30:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d\n",&n,&m);
         ~~~~~^~~~~~~~~~~~~~~~

• 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: 24 / 24