Submission #173122

#	Time	Username	Problem	Language	Result	Execution time	Memory
173122		mosiashvililuka	Nice sequence (IZhO18_sequence)	C++14	76 / 100	2058 ms	34192 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;
int bo[500009],fls;
deque <int> de;
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(){
    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; 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--){
                        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 (stderr)

sequence.cpp: In function 'int main()':
sequence.cpp:68:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(i=1; i<de.size(); i++){
                      ~^~~~~~~~~~
sequence.cpp:73:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(i=1; i<de.size(); i++){
                      ~^~~~~~~~~~

• 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