oj.uz

Submission #173111

# Submission time Handle Problem Language Result Execution time Memory
173111 2020-01-03T11:36:33 Z mosiashvililuka Nice sequence (IZhO18_sequence) C++14
58 / 100
 2000 ms 35676 KB 
#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;
int bo[500009],fls;
deque <int> de;
vector <int> v[500009];
void dfs(int q){
    bo[q]=i;
    pi++;
    p[pi]=q;
    for(vector <int>::iterator it=v[q].begin(); it!=v[q].end(); it++){
        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=500001;
        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+1; i++) v[i].clear();
            for(i=0; i<=mid; i++){
                pr[i]=0;bo[i]=-1;
            }
            for(i=1; i<=mid; i++){
                if(i>=n) v[i-n].push_back(i);
                if(i>=m) v[i].push_back(i-m);
            }
            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

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

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 135 ms 21880 KB Ok
2 Correct 133 ms 21880 KB Ok
3 Correct 150 ms 21880 KB Ok
4 Correct 133 ms 21880 KB Ok
5 Correct 134 ms 22008 KB Ok
6 Correct 134 ms 21884 KB Ok
7 Correct 133 ms 21880 KB Ok
8 Correct 134 ms 21972 KB Ok
9 Correct 134 ms 21880 KB Ok
10 Correct 132 ms 21880 KB Ok
11 Correct 132 ms 21880 KB Ok
12 Correct 133 ms 21908 KB Ok

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 135 ms 21952 KB Ok
2 Correct 134 ms 22032 KB Ok
3 Correct 134 ms 21924 KB Ok
4 Correct 134 ms 21880 KB Ok
5 Correct 134 ms 21880 KB Ok
6 Correct 140 ms 21980 KB Ok
7 Correct 184 ms 22776 KB Ok
8 Correct 151 ms 22388 KB Ok
9 Correct 179 ms 22812 KB Ok
10 Correct 159 ms 22492 KB Ok

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 22004 KB Ok
2 Correct 136 ms 22024 KB Ok
3 Correct 134 ms 21884 KB Ok
4 Correct 163 ms 21940 KB Ok
5 Correct 134 ms 21908 KB Ok
6 Correct 136 ms 21884 KB Ok
7 Correct 138 ms 21944 KB Ok
8 Correct 136 ms 21880 KB Ok
9 Correct 144 ms 22032 KB Ok
10 Correct 157 ms 22040 KB Ok
11 Correct 137 ms 22008 KB Ok

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 153 ms 21832 KB Ok
2 Correct 134 ms 21948 KB Ok
3 Correct 136 ms 22008 KB Ok
4 Correct 137 ms 21964 KB Ok
5 Correct 132 ms 21896 KB Ok
6 Correct 645 ms 32104 KB Ok
7 Correct 539 ms 32668 KB Ok
8 Correct 1041 ms 35676 KB Ok
9 Correct 756 ms 34032 KB Ok
10 Correct 447 ms 27772 KB Ok
11 Correct 729 ms 34136 KB Ok

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 135 ms 21880 KB Ok
2 Correct 133 ms 21880 KB Ok
3 Correct 150 ms 21880 KB Ok
4 Correct 133 ms 21880 KB Ok
5 Correct 134 ms 22008 KB Ok
6 Correct 134 ms 21884 KB Ok
7 Correct 133 ms 21880 KB Ok
8 Correct 134 ms 21972 KB Ok
9 Correct 134 ms 21880 KB Ok
10 Correct 132 ms 21880 KB Ok
11 Correct 132 ms 21880 KB Ok
12 Correct 133 ms 21908 KB Ok
13 Correct 71 ms 22004 KB Ok
14 Correct 136 ms 22024 KB Ok
15 Correct 134 ms 21884 KB Ok
16 Correct 163 ms 21940 KB Ok
17 Correct 134 ms 21908 KB Ok
18 Correct 136 ms 21884 KB Ok
19 Correct 138 ms 21944 KB Ok
20 Correct 136 ms 21880 KB Ok
21 Correct 144 ms 22032 KB Ok
22 Correct 157 ms 22040 KB Ok
23 Correct 137 ms 22008 KB Ok
24 Correct 141 ms 22020 KB Ok
25 Correct 141 ms 22144 KB Ok
26 Correct 140 ms 22000 KB Ok
27 Correct 138 ms 22032 KB Ok
28 Correct 139 ms 22136 KB Ok
29 Correct 136 ms 22096 KB Ok
30 Correct 137 ms 22140 KB Ok
31 Correct 137 ms 22008 KB Ok
32 Correct 139 ms 22016 KB Ok
33 Correct 138 ms 21980 KB Ok
34 Correct 151 ms 22312 KB Ok
35 Correct 156 ms 22328 KB Ok
36 Correct 154 ms 22168 KB Ok
37 Correct 158 ms 22216 KB Ok
38 Correct 161 ms 22264 KB Ok
39 Correct 151 ms 22176 KB Ok
40 Correct 167 ms 22236 KB Ok
41 Correct 165 ms 22236 KB Ok
42 Correct 154 ms 22264 KB Ok
43 Correct 155 ms 22284 KB Ok

Subtask #6
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 135 ms 21880 KB Ok
2 Correct 133 ms 21880 KB Ok
3 Correct 150 ms 21880 KB Ok
4 Correct 133 ms 21880 KB Ok
5 Correct 134 ms 22008 KB Ok
6 Correct 134 ms 21884 KB Ok
7 Correct 133 ms 21880 KB Ok
8 Correct 134 ms 21972 KB Ok
9 Correct 134 ms 21880 KB Ok
10 Correct 132 ms 21880 KB Ok
11 Correct 132 ms 21880 KB Ok
12 Correct 133 ms 21908 KB Ok
13 Correct 135 ms 21952 KB Ok
14 Correct 134 ms 22032 KB Ok
15 Correct 134 ms 21924 KB Ok
16 Correct 134 ms 21880 KB Ok
17 Correct 134 ms 21880 KB Ok
18 Correct 140 ms 21980 KB Ok
19 Correct 184 ms 22776 KB Ok
20 Correct 151 ms 22388 KB Ok
21 Correct 179 ms 22812 KB Ok
22 Correct 159 ms 22492 KB Ok
23 Correct 71 ms 22004 KB Ok
24 Correct 136 ms 22024 KB Ok
25 Correct 134 ms 21884 KB Ok
26 Correct 163 ms 21940 KB Ok
27 Correct 134 ms 21908 KB Ok
28 Correct 136 ms 21884 KB Ok
29 Correct 138 ms 21944 KB Ok
30 Correct 136 ms 21880 KB Ok
31 Correct 144 ms 22032 KB Ok
32 Correct 157 ms 22040 KB Ok
33 Correct 137 ms 22008 KB Ok
34 Correct 141 ms 22020 KB Ok
35 Correct 141 ms 22144 KB Ok
36 Correct 140 ms 22000 KB Ok
37 Correct 138 ms 22032 KB Ok
38 Correct 139 ms 22136 KB Ok
39 Correct 136 ms 22096 KB Ok
40 Correct 137 ms 22140 KB Ok
41 Correct 137 ms 22008 KB Ok
42 Correct 139 ms 22016 KB Ok
43 Correct 138 ms 21980 KB Ok
44 Correct 151 ms 22312 KB Ok
45 Correct 156 ms 22328 KB Ok
46 Correct 154 ms 22168 KB Ok
47 Correct 158 ms 22216 KB Ok
48 Correct 161 ms 22264 KB Ok
49 Correct 151 ms 22176 KB Ok
50 Correct 167 ms 22236 KB Ok
51 Correct 165 ms 22236 KB Ok
52 Correct 154 ms 22264 KB Ok
53 Correct 155 ms 22284 KB Ok
54 Correct 427 ms 24392 KB Ok
55 Correct 511 ms 24780 KB Ok
56 Correct 520 ms 24696 KB Ok
57 Correct 400 ms 24056 KB Ok
58 Correct 418 ms 24176 KB Ok
59 Correct 390 ms 24056 KB Ok
60 Correct 353 ms 23800 KB Ok
61 Correct 383 ms 24088 KB Ok
62 Correct 475 ms 24700 KB Ok
63 Correct 411 ms 24184 KB Ok
64 Correct 578 ms 24760 KB Ok
65 Correct 439 ms 24440 KB Ok
66 Correct 418 ms 24184 KB Ok
67 Correct 384 ms 24012 KB Ok
68 Correct 422 ms 24224 KB Ok
69 Correct 1628 ms 32340 KB Ok
70 Correct 1876 ms 33000 KB Ok
71 Correct 1338 ms 32528 KB Ok
72 Correct 1686 ms 32284 KB Ok
73 Correct 1656 ms 32520 KB Ok
74 Correct 1500 ms 32308 KB Ok
75 Correct 1511 ms 31900 KB Ok
76 Execution timed out 2016 ms 31992 KB Time limit exceeded
77 Halted 0 ms 0 KB -

Subtask #7
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 135 ms 21880 KB Ok
2 Correct 133 ms 21880 KB Ok
3 Correct 150 ms 21880 KB Ok
4 Correct 133 ms 21880 KB Ok
5 Correct 134 ms 22008 KB Ok
6 Correct 134 ms 21884 KB Ok
7 Correct 133 ms 21880 KB Ok
8 Correct 134 ms 21972 KB Ok
9 Correct 134 ms 21880 KB Ok
10 Correct 132 ms 21880 KB Ok
11 Correct 132 ms 21880 KB Ok
12 Correct 133 ms 21908 KB Ok
13 Correct 135 ms 21952 KB Ok
14 Correct 134 ms 22032 KB Ok
15 Correct 134 ms 21924 KB Ok
16 Correct 134 ms 21880 KB Ok
17 Correct 134 ms 21880 KB Ok
18 Correct 140 ms 21980 KB Ok
19 Correct 184 ms 22776 KB Ok
20 Correct 151 ms 22388 KB Ok
21 Correct 179 ms 22812 KB Ok
22 Correct 159 ms 22492 KB Ok
23 Correct 71 ms 22004 KB Ok
24 Correct 136 ms 22024 KB Ok
25 Correct 134 ms 21884 KB Ok
26 Correct 163 ms 21940 KB Ok
27 Correct 134 ms 21908 KB Ok
28 Correct 136 ms 21884 KB Ok
29 Correct 138 ms 21944 KB Ok
30 Correct 136 ms 21880 KB Ok
31 Correct 144 ms 22032 KB Ok
32 Correct 157 ms 22040 KB Ok
33 Correct 137 ms 22008 KB Ok
34 Correct 153 ms 21832 KB Ok
35 Correct 134 ms 21948 KB Ok
36 Correct 136 ms 22008 KB Ok
37 Correct 137 ms 21964 KB Ok
38 Correct 132 ms 21896 KB Ok
39 Correct 645 ms 32104 KB Ok
40 Correct 539 ms 32668 KB Ok
41 Correct 1041 ms 35676 KB Ok
42 Correct 756 ms 34032 KB Ok
43 Correct 447 ms 27772 KB Ok
44 Correct 729 ms 34136 KB Ok
45 Correct 141 ms 22020 KB Ok
46 Correct 141 ms 22144 KB Ok
47 Correct 140 ms 22000 KB Ok
48 Correct 138 ms 22032 KB Ok
49 Correct 139 ms 22136 KB Ok
50 Correct 136 ms 22096 KB Ok
51 Correct 137 ms 22140 KB Ok
52 Correct 137 ms 22008 KB Ok
53 Correct 139 ms 22016 KB Ok
54 Correct 138 ms 21980 KB Ok
55 Correct 151 ms 22312 KB Ok
56 Correct 156 ms 22328 KB Ok
57 Correct 154 ms 22168 KB Ok
58 Correct 158 ms 22216 KB Ok
59 Correct 161 ms 22264 KB Ok
60 Correct 151 ms 22176 KB Ok
61 Correct 167 ms 22236 KB Ok
62 Correct 165 ms 22236 KB Ok
63 Correct 154 ms 22264 KB Ok
64 Correct 155 ms 22284 KB Ok
65 Correct 427 ms 24392 KB Ok
66 Correct 511 ms 24780 KB Ok
67 Correct 520 ms 24696 KB Ok
68 Correct 400 ms 24056 KB Ok
69 Correct 418 ms 24176 KB Ok
70 Correct 390 ms 24056 KB Ok
71 Correct 353 ms 23800 KB Ok
72 Correct 383 ms 24088 KB Ok
73 Correct 475 ms 24700 KB Ok
74 Correct 411 ms 24184 KB Ok
75 Correct 578 ms 24760 KB Ok
76 Correct 439 ms 24440 KB Ok
77 Correct 418 ms 24184 KB Ok
78 Correct 384 ms 24012 KB Ok
79 Correct 422 ms 24224 KB Ok
80 Correct 1628 ms 32340 KB Ok
81 Correct 1876 ms 33000 KB Ok
82 Correct 1338 ms 32528 KB Ok
83 Correct 1686 ms 32284 KB Ok
84 Correct 1656 ms 32520 KB Ok
85 Correct 1500 ms 32308 KB Ok
86 Correct 1511 ms 31900 KB Ok
87 Execution timed out 2016 ms 31992 KB Time limit exceeded
88 Halted 0 ms 0 KB -