Submission #173123

#	Time	Username	Problem	Language	Result	Execution time	Memory
173123		mosiashvililuka	Nice sequence (IZhO18_sequence)	C++14	76 / 100	2021 ms	34276 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++){
                      ~^~~~~~~~~~
sequence.cpp:30:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d\n",&tes);
     ~~~~~^~~~~~~~~~~~~
sequence.cpp:33: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: 0 / 24