oj.uz

Submission #334956

# Submission time Handle Problem Language Result Execution time Memory
334956 2020-12-10T12:56:55 Z amunduzbaev Nice sequence (IZhO18_sequence) C++14
76 / 100
 2000 ms 44208 KB 
#include<bits/stdc++.h>
using namespace std;
int n,m,len,pref[1000005];
bool vis[1000005];
vector<int>top;
void dfs(int v){
    vis[v]=1;
    if(v-m>=0&&!vis[v-m])dfs(v-m);
    if(v+n<=len&&!vis[v+n])dfs(v+n);
    top.push_back(v);
}
bool check(int x){
    len=x;
    top.clear();
    for(int i=0;i<=len;i++)vis[i]=0;
    for(int i=0;i<=len;i++)if(!vis[i])dfs(i);
    for(int i=0;i<=len;i++)pref[top[i]]=i;
    for(int i=0;i<=len;i++){
        if(i-m>=0&&pref[i]<=pref[i-m])return false;
        if(i+n<=len&&pref[i]<=pref[i+n])return false;
    }
    return true;
}
int main(){
    int test;
    scanf("%d",&test);
    while(test--){
        scanf("%d%d",&n,&m);
        int l=0,r=400000;
        while(l<r){
            int mid=(l+r+1)>>1;
            if(check(mid))l=mid;
            else r=mid-1;
        }
        check(l);
        printf("%d\n",l);
        if(l){
            for(int i=1;i<=l;i++)printf("%d ",pref[i]-pref[i-1]);
            puts("");
        }
    }
}

Compilation message

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

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 8416 KB Ok
2 Correct 66 ms 8416 KB Ok
3 Correct 53 ms 2676 KB Ok
4 Correct 54 ms 3040 KB Ok
5 Correct 53 ms 2656 KB Ok
6 Correct 56 ms 3828 KB Ok
7 Correct 54 ms 2548 KB Ok
8 Correct 53 ms 3808 KB Ok
9 Correct 52 ms 2656 KB Ok
10 Correct 53 ms 5344 KB Ok
11 Correct 54 ms 2528 KB Ok
12 Correct 51 ms 2400 KB Ok

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 8416 KB Ok
2 Correct 73 ms 8416 KB Ok
3 Correct 64 ms 8544 KB Ok
4 Correct 67 ms 8416 KB Ok
5 Correct 66 ms 8416 KB Ok
6 Correct 71 ms 8544 KB Ok
7 Correct 82 ms 8948 KB Ok
8 Correct 70 ms 8832 KB Ok
9 Correct 93 ms 9056 KB Ok
10 Correct 76 ms 8820 KB Ok

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 8416 KB Ok
2 Correct 72 ms 8416 KB Ok
3 Correct 71 ms 8416 KB Ok
4 Correct 76 ms 8416 KB Ok
5 Correct 70 ms 8416 KB Ok
6 Correct 82 ms 8432 KB Ok
7 Correct 69 ms 8416 KB Ok
8 Correct 80 ms 8416 KB Ok
9 Correct 75 ms 8416 KB Ok
10 Correct 83 ms 8416 KB Ok
11 Correct 73 ms 8544 KB Ok

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 8416 KB Ok
2 Correct 85 ms 8416 KB Ok
3 Correct 80 ms 8416 KB Ok
4 Correct 86 ms 8416 KB Ok
5 Correct 82 ms 8416 KB Ok
6 Correct 376 ms 12276 KB Ok
7 Correct 365 ms 10720 KB Ok
8 Correct 643 ms 13920 KB Ok
9 Correct 471 ms 13024 KB Ok
10 Correct 289 ms 9824 KB Ok
11 Correct 424 ms 12256 KB Ok

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 8416 KB Ok
2 Correct 66 ms 8416 KB Ok
3 Correct 53 ms 2676 KB Ok
4 Correct 54 ms 3040 KB Ok
5 Correct 53 ms 2656 KB Ok
6 Correct 56 ms 3828 KB Ok
7 Correct 54 ms 2548 KB Ok
8 Correct 53 ms 3808 KB Ok
9 Correct 52 ms 2656 KB Ok
10 Correct 53 ms 5344 KB Ok
11 Correct 54 ms 2528 KB Ok
12 Correct 51 ms 2400 KB Ok
13 Correct 28 ms 8416 KB Ok
14 Correct 72 ms 8416 KB Ok
15 Correct 71 ms 8416 KB Ok
16 Correct 76 ms 8416 KB Ok
17 Correct 70 ms 8416 KB Ok
18 Correct 82 ms 8432 KB Ok
19 Correct 69 ms 8416 KB Ok
20 Correct 80 ms 8416 KB Ok
21 Correct 75 ms 8416 KB Ok
22 Correct 83 ms 8416 KB Ok
23 Correct 73 ms 8544 KB Ok
24 Correct 64 ms 2272 KB Ok
25 Correct 62 ms 2400 KB Ok
26 Correct 64 ms 2784 KB Ok
27 Correct 61 ms 2784 KB Ok
28 Correct 69 ms 2528 KB Ok
29 Correct 60 ms 4320 KB Ok
30 Correct 63 ms 2656 KB Ok
31 Correct 68 ms 2400 KB Ok
32 Correct 63 ms 2272 KB Ok
33 Correct 65 ms 2656 KB Ok
34 Correct 90 ms 8544 KB Ok
35 Correct 92 ms 8672 KB Ok
36 Correct 90 ms 8672 KB Ok
37 Correct 98 ms 8544 KB Ok
38 Correct 95 ms 8672 KB Ok
39 Correct 86 ms 8672 KB Ok
40 Correct 95 ms 8672 KB Ok
41 Correct 99 ms 8544 KB Ok
42 Correct 92 ms 8544 KB Ok
43 Correct 90 ms 8672 KB Ok

Subtask #6
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 8416 KB Ok
2 Correct 66 ms 8416 KB Ok
3 Correct 53 ms 2676 KB Ok
4 Correct 54 ms 3040 KB Ok
5 Correct 53 ms 2656 KB Ok
6 Correct 56 ms 3828 KB Ok
7 Correct 54 ms 2548 KB Ok
8 Correct 53 ms 3808 KB Ok
9 Correct 52 ms 2656 KB Ok
10 Correct 53 ms 5344 KB Ok
11 Correct 54 ms 2528 KB Ok
12 Correct 51 ms 2400 KB Ok
13 Correct 76 ms 8416 KB Ok
14 Correct 73 ms 8416 KB Ok
15 Correct 64 ms 8544 KB Ok
16 Correct 67 ms 8416 KB Ok
17 Correct 66 ms 8416 KB Ok
18 Correct 71 ms 8544 KB Ok
19 Correct 82 ms 8948 KB Ok
20 Correct 70 ms 8832 KB Ok
21 Correct 93 ms 9056 KB Ok
22 Correct 76 ms 8820 KB Ok
23 Correct 28 ms 8416 KB Ok
24 Correct 72 ms 8416 KB Ok
25 Correct 71 ms 8416 KB Ok
26 Correct 76 ms 8416 KB Ok
27 Correct 70 ms 8416 KB Ok
28 Correct 82 ms 8432 KB Ok
29 Correct 69 ms 8416 KB Ok
30 Correct 80 ms 8416 KB Ok
31 Correct 75 ms 8416 KB Ok
32 Correct 83 ms 8416 KB Ok
33 Correct 73 ms 8544 KB Ok
34 Correct 64 ms 2272 KB Ok
35 Correct 62 ms 2400 KB Ok
36 Correct 64 ms 2784 KB Ok
37 Correct 61 ms 2784 KB Ok
38 Correct 69 ms 2528 KB Ok
39 Correct 60 ms 4320 KB Ok
40 Correct 63 ms 2656 KB Ok
41 Correct 68 ms 2400 KB Ok
42 Correct 63 ms 2272 KB Ok
43 Correct 65 ms 2656 KB Ok
44 Correct 90 ms 8544 KB Ok
45 Correct 92 ms 8672 KB Ok
46 Correct 90 ms 8672 KB Ok
47 Correct 98 ms 8544 KB Ok
48 Correct 95 ms 8672 KB Ok
49 Correct 86 ms 8672 KB Ok
50 Correct 95 ms 8672 KB Ok
51 Correct 99 ms 8544 KB Ok
52 Correct 92 ms 8544 KB Ok
53 Correct 90 ms 8672 KB Ok
54 Correct 264 ms 3928 KB Ok
55 Correct 300 ms 4192 KB Ok
56 Correct 294 ms 4192 KB Ok
57 Correct 227 ms 3552 KB Ok
58 Correct 261 ms 3936 KB Ok
59 Correct 249 ms 3560 KB Ok
60 Correct 222 ms 3552 KB Ok
61 Correct 232 ms 3680 KB Ok
62 Correct 290 ms 4192 KB Ok
63 Correct 247 ms 3680 KB Ok
64 Correct 288 ms 4192 KB Ok
65 Correct 270 ms 3808 KB Ok
66 Correct 253 ms 3680 KB Ok
67 Correct 221 ms 3680 KB Ok
68 Correct 254 ms 3936 KB Ok
69 Correct 462 ms 14560 KB Ok
70 Correct 479 ms 15072 KB Ok
71 Correct 461 ms 14560 KB Ok
72 Correct 466 ms 14592 KB Ok
73 Correct 461 ms 14560 KB Ok
74 Correct 452 ms 14432 KB Ok
75 Correct 473 ms 14048 KB Ok
76 Correct 480 ms 14688 KB Ok
77 Correct 454 ms 14048 KB Ok
78 Correct 465 ms 14432 KB Ok
79 Correct 462 ms 14816 KB Ok
80 Correct 466 ms 14932 KB Ok
81 Correct 481 ms 14688 KB Ok
82 Correct 450 ms 14560 KB Ok
83 Correct 450 ms 14048 KB Ok

Subtask #7
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 8416 KB Ok
2 Correct 66 ms 8416 KB Ok
3 Correct 53 ms 2676 KB Ok
4 Correct 54 ms 3040 KB Ok
5 Correct 53 ms 2656 KB Ok
6 Correct 56 ms 3828 KB Ok
7 Correct 54 ms 2548 KB Ok
8 Correct 53 ms 3808 KB Ok
9 Correct 52 ms 2656 KB Ok
10 Correct 53 ms 5344 KB Ok
11 Correct 54 ms 2528 KB Ok
12 Correct 51 ms 2400 KB Ok
13 Correct 76 ms 8416 KB Ok
14 Correct 73 ms 8416 KB Ok
15 Correct 64 ms 8544 KB Ok
16 Correct 67 ms 8416 KB Ok
17 Correct 66 ms 8416 KB Ok
18 Correct 71 ms 8544 KB Ok
19 Correct 82 ms 8948 KB Ok
20 Correct 70 ms 8832 KB Ok
21 Correct 93 ms 9056 KB Ok
22 Correct 76 ms 8820 KB Ok
23 Correct 28 ms 8416 KB Ok
24 Correct 72 ms 8416 KB Ok
25 Correct 71 ms 8416 KB Ok
26 Correct 76 ms 8416 KB Ok
27 Correct 70 ms 8416 KB Ok
28 Correct 82 ms 8432 KB Ok
29 Correct 69 ms 8416 KB Ok
30 Correct 80 ms 8416 KB Ok
31 Correct 75 ms 8416 KB Ok
32 Correct 83 ms 8416 KB Ok
33 Correct 73 ms 8544 KB Ok
34 Correct 81 ms 8416 KB Ok
35 Correct 85 ms 8416 KB Ok
36 Correct 80 ms 8416 KB Ok
37 Correct 86 ms 8416 KB Ok
38 Correct 82 ms 8416 KB Ok
39 Correct 376 ms 12276 KB Ok
40 Correct 365 ms 10720 KB Ok
41 Correct 643 ms 13920 KB Ok
42 Correct 471 ms 13024 KB Ok
43 Correct 289 ms 9824 KB Ok
44 Correct 424 ms 12256 KB Ok
45 Correct 64 ms 2272 KB Ok
46 Correct 62 ms 2400 KB Ok
47 Correct 64 ms 2784 KB Ok
48 Correct 61 ms 2784 KB Ok
49 Correct 69 ms 2528 KB Ok
50 Correct 60 ms 4320 KB Ok
51 Correct 63 ms 2656 KB Ok
52 Correct 68 ms 2400 KB Ok
53 Correct 63 ms 2272 KB Ok
54 Correct 65 ms 2656 KB Ok
55 Correct 90 ms 8544 KB Ok
56 Correct 92 ms 8672 KB Ok
57 Correct 90 ms 8672 KB Ok
58 Correct 98 ms 8544 KB Ok
59 Correct 95 ms 8672 KB Ok
60 Correct 86 ms 8672 KB Ok
61 Correct 95 ms 8672 KB Ok
62 Correct 99 ms 8544 KB Ok
63 Correct 92 ms 8544 KB Ok
64 Correct 90 ms 8672 KB Ok
65 Correct 264 ms 3928 KB Ok
66 Correct 300 ms 4192 KB Ok
67 Correct 294 ms 4192 KB Ok
68 Correct 227 ms 3552 KB Ok
69 Correct 261 ms 3936 KB Ok
70 Correct 249 ms 3560 KB Ok
71 Correct 222 ms 3552 KB Ok
72 Correct 232 ms 3680 KB Ok
73 Correct 290 ms 4192 KB Ok
74 Correct 247 ms 3680 KB Ok
75 Correct 288 ms 4192 KB Ok
76 Correct 270 ms 3808 KB Ok
77 Correct 253 ms 3680 KB Ok
78 Correct 221 ms 3680 KB Ok
79 Correct 254 ms 3936 KB Ok
80 Correct 462 ms 14560 KB Ok
81 Correct 479 ms 15072 KB Ok
82 Correct 461 ms 14560 KB Ok
83 Correct 466 ms 14592 KB Ok
84 Correct 461 ms 14560 KB Ok
85 Correct 452 ms 14432 KB Ok
86 Correct 473 ms 14048 KB Ok
87 Correct 480 ms 14688 KB Ok
88 Correct 454 ms 14048 KB Ok
89 Correct 465 ms 14432 KB Ok
90 Correct 462 ms 14816 KB Ok
91 Correct 466 ms 14932 KB Ok
92 Correct 481 ms 14688 KB Ok
93 Correct 450 ms 14560 KB Ok
94 Correct 450 ms 14048 KB Ok
95 Correct 583 ms 7576 KB Ok
96 Correct 865 ms 9436 KB Ok
97 Correct 833 ms 8488 KB Ok
98 Correct 607 ms 7516 KB Ok
99 Correct 738 ms 8028 KB Ok
100 Correct 813 ms 8028 KB Ok
101 Correct 767 ms 8524 KB Ok
102 Correct 744 ms 8156 KB Ok
103 Correct 727 ms 8540 KB Ok
104 Correct 888 ms 9660 KB Ok
105 Correct 833 ms 9436 KB Ok
106 Correct 731 ms 9024 KB Ok
107 Correct 795 ms 8924 KB Ok
108 Correct 876 ms 9564 KB Ok
109 Correct 827 ms 9436 KB Ok
110 Correct 1936 ms 41720 KB Ok
111 Execution timed out 2016 ms 44208 KB Time limit exceeded
112 Halted 0 ms 0 KB -