oj.uz

Submission #93177

# Submission time Handle Problem Language Result Execution time Memory
93177 2019-01-06T19:26:33 Z Vardanyan Nice sequence (IZhO18_sequence) C++14
100 / 100
 1522 ms 49784 KB 
#include <bits/stdc++.h>
using namespace std;
const int N = 1000*1000+5;
int pref[N];
int col[N];
int now = N;
int n,m;
int len;
void dfs(int v){
    col[v] = 1;
    if(v == 0){
        now = -1;
    }
    else{
        pref[v] = now;
        now--;
    }
  if(v-m>=0)  dfs(v-m);
  if(v+n<=len)  dfs(v+n);
}
bool check(int v){
    col[v] = 1;
    for(int i = 0;i<2;i++){
        int to = -1;
        if(i == 0 && v-m>=0) to = v-m;
        else if(i == 1 && v+n<=len) to = v+n;
        if(to == -1) continue;
        if(!col[to]){
            if(check(to)) return true;
        }
        else if(col[to] == 1){
            return true;
        }
    }
    col[v] = 2;
    return false;
}
int main(){
    ios_base::sync_with_stdio(false);
    int t;
    cin>>t;
    while(t--){
        cin>>n>>m;
        int l = min(n,m)-1;
        int r = n+m;
        int as = -1;
        while(l<=r){
            memset(col,0,sizeof col);
            now = N;
            int mid = (l+r)/2;
            len = mid;
            bool f = true;
            for(int i = 1;i<=mid;i++){
                if(!col[i]){
                    if(check(i)){
                        f = false;
                        break;
                    }
                }
            }
            if(!f){
                r = mid-1;
                continue;
            }
            else{
                as = mid;
                l = mid+1;
            }
        }
        if(as == -1){
            cout<<0<<endl;
            continue;
        }
        memset(col,0,sizeof col);
        memset(pref,0,sizeof pref);
        len = as;
        for(int i = n;i>=0;i--){
            if(!col[i]) dfs(i);
        }
        cout<<as<<endl;
        for(int i = 1;i<=as;i++){
            int x = pref[i]-pref[i-1];
            cout<<x<<" ";
        }
        cout<<endl;
    }
	return 0;
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 8184 KB Ok
2 Correct 22 ms 8184 KB Ok
3 Correct 22 ms 8184 KB Ok
4 Correct 23 ms 8184 KB Ok
5 Correct 23 ms 8184 KB Ok
6 Correct 23 ms 8184 KB Ok
7 Correct 22 ms 8184 KB Ok
8 Correct 22 ms 8184 KB Ok
9 Correct 24 ms 8196 KB Ok
10 Correct 23 ms 8184 KB Ok
11 Correct 23 ms 8184 KB Ok
12 Correct 22 ms 8184 KB Ok

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 8184 KB Ok
2 Correct 20 ms 8184 KB Ok
3 Correct 21 ms 8184 KB Ok
4 Correct 21 ms 8184 KB Ok
5 Correct 22 ms 8184 KB Ok
6 Correct 35 ms 8312 KB Ok
7 Correct 49 ms 9080 KB Ok
8 Correct 38 ms 8696 KB Ok
9 Correct 51 ms 9200 KB Ok
10 Correct 40 ms 8696 KB Ok

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 8184 KB Ok
2 Correct 15 ms 8184 KB Ok
3 Correct 15 ms 8184 KB Ok
4 Correct 15 ms 8184 KB Ok
5 Correct 42 ms 8184 KB Ok
6 Correct 19 ms 8184 KB Ok
7 Correct 18 ms 8184 KB Ok
8 Correct 17 ms 8184 KB Ok
9 Correct 18 ms 8184 KB Ok
10 Correct 18 ms 8184 KB Ok
11 Correct 19 ms 8184 KB Ok

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 8184 KB Ok
2 Correct 19 ms 8184 KB Ok
3 Correct 19 ms 8184 KB Ok
4 Correct 20 ms 8184 KB Ok
5 Correct 21 ms 8188 KB Ok
6 Correct 178 ms 17476 KB Ok
7 Correct 171 ms 16504 KB Ok
8 Correct 292 ms 20472 KB Ok
9 Correct 214 ms 19696 KB Ok
10 Correct 134 ms 13904 KB Ok
11 Correct 194 ms 19448 KB Ok

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 8184 KB Ok
2 Correct 22 ms 8184 KB Ok
3 Correct 22 ms 8184 KB Ok
4 Correct 23 ms 8184 KB Ok
5 Correct 23 ms 8184 KB Ok
6 Correct 23 ms 8184 KB Ok
7 Correct 22 ms 8184 KB Ok
8 Correct 22 ms 8184 KB Ok
9 Correct 24 ms 8196 KB Ok
10 Correct 23 ms 8184 KB Ok
11 Correct 23 ms 8184 KB Ok
12 Correct 22 ms 8184 KB Ok
13 Correct 9 ms 8184 KB Ok
14 Correct 15 ms 8184 KB Ok
15 Correct 15 ms 8184 KB Ok
16 Correct 15 ms 8184 KB Ok
17 Correct 42 ms 8184 KB Ok
18 Correct 19 ms 8184 KB Ok
19 Correct 18 ms 8184 KB Ok
20 Correct 17 ms 8184 KB Ok
21 Correct 18 ms 8184 KB Ok
22 Correct 18 ms 8184 KB Ok
23 Correct 19 ms 8184 KB Ok
24 Correct 34 ms 8184 KB Ok
25 Correct 32 ms 8184 KB Ok
26 Correct 33 ms 8184 KB Ok
27 Correct 32 ms 8184 KB Ok
28 Correct 32 ms 8228 KB Ok
29 Correct 32 ms 8184 KB Ok
30 Correct 31 ms 8184 KB Ok
31 Correct 33 ms 8184 KB Ok
32 Correct 35 ms 8184 KB Ok
33 Correct 32 ms 8184 KB Ok
34 Correct 36 ms 8440 KB Ok
35 Correct 37 ms 8440 KB Ok
36 Correct 37 ms 8440 KB Ok
37 Correct 37 ms 8412 KB Ok
38 Correct 36 ms 8440 KB Ok
39 Correct 37 ms 8440 KB Ok
40 Correct 37 ms 8440 KB Ok
41 Correct 34 ms 8440 KB Ok
42 Correct 36 ms 8440 KB Ok
43 Correct 36 ms 8440 KB Ok

Subtask #6
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 8184 KB Ok
2 Correct 22 ms 8184 KB Ok
3 Correct 22 ms 8184 KB Ok
4 Correct 23 ms 8184 KB Ok
5 Correct 23 ms 8184 KB Ok
6 Correct 23 ms 8184 KB Ok
7 Correct 22 ms 8184 KB Ok
8 Correct 22 ms 8184 KB Ok
9 Correct 24 ms 8196 KB Ok
10 Correct 23 ms 8184 KB Ok
11 Correct 23 ms 8184 KB Ok
12 Correct 22 ms 8184 KB Ok
13 Correct 17 ms 8184 KB Ok
14 Correct 20 ms 8184 KB Ok
15 Correct 21 ms 8184 KB Ok
16 Correct 21 ms 8184 KB Ok
17 Correct 22 ms 8184 KB Ok
18 Correct 35 ms 8312 KB Ok
19 Correct 49 ms 9080 KB Ok
20 Correct 38 ms 8696 KB Ok
21 Correct 51 ms 9200 KB Ok
22 Correct 40 ms 8696 KB Ok
23 Correct 9 ms 8184 KB Ok
24 Correct 15 ms 8184 KB Ok
25 Correct 15 ms 8184 KB Ok
26 Correct 15 ms 8184 KB Ok
27 Correct 42 ms 8184 KB Ok
28 Correct 19 ms 8184 KB Ok
29 Correct 18 ms 8184 KB Ok
30 Correct 17 ms 8184 KB Ok
31 Correct 18 ms 8184 KB Ok
32 Correct 18 ms 8184 KB Ok
33 Correct 19 ms 8184 KB Ok
34 Correct 34 ms 8184 KB Ok
35 Correct 32 ms 8184 KB Ok
36 Correct 33 ms 8184 KB Ok
37 Correct 32 ms 8184 KB Ok
38 Correct 32 ms 8228 KB Ok
39 Correct 32 ms 8184 KB Ok
40 Correct 31 ms 8184 KB Ok
41 Correct 33 ms 8184 KB Ok
42 Correct 35 ms 8184 KB Ok
43 Correct 32 ms 8184 KB Ok
44 Correct 36 ms 8440 KB Ok
45 Correct 37 ms 8440 KB Ok
46 Correct 37 ms 8440 KB Ok
47 Correct 37 ms 8412 KB Ok
48 Correct 36 ms 8440 KB Ok
49 Correct 37 ms 8440 KB Ok
50 Correct 37 ms 8440 KB Ok
51 Correct 34 ms 8440 KB Ok
52 Correct 36 ms 8440 KB Ok
53 Correct 36 ms 8440 KB Ok
54 Correct 115 ms 9948 KB Ok
55 Correct 129 ms 10404 KB Ok
56 Correct 126 ms 10360 KB Ok
57 Correct 99 ms 9592 KB Ok
58 Correct 118 ms 9976 KB Ok
59 Correct 113 ms 9888 KB Ok
60 Correct 99 ms 9848 KB Ok
61 Correct 105 ms 9608 KB Ok
62 Correct 125 ms 10236 KB Ok
63 Correct 105 ms 9848 KB Ok
64 Correct 137 ms 10360 KB Ok
65 Correct 119 ms 10232 KB Ok
66 Correct 118 ms 9852 KB Ok
67 Correct 103 ms 9768 KB Ok
68 Correct 113 ms 9848 KB Ok
69 Correct 270 ms 17648 KB Ok
70 Correct 294 ms 18240 KB Ok
71 Correct 279 ms 17912 KB Ok
72 Correct 276 ms 17404 KB Ok
73 Correct 283 ms 18048 KB Ok
74 Correct 269 ms 17784 KB Ok
75 Correct 262 ms 17528 KB Ok
76 Correct 308 ms 17960 KB Ok
77 Correct 264 ms 17528 KB Ok
78 Correct 273 ms 17604 KB Ok
79 Correct 269 ms 18040 KB Ok
80 Correct 298 ms 18024 KB Ok
81 Correct 295 ms 18016 KB Ok
82 Correct 264 ms 17912 KB Ok
83 Correct 259 ms 17656 KB Ok

Subtask #7
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 8184 KB Ok
2 Correct 22 ms 8184 KB Ok
3 Correct 22 ms 8184 KB Ok
4 Correct 23 ms 8184 KB Ok
5 Correct 23 ms 8184 KB Ok
6 Correct 23 ms 8184 KB Ok
7 Correct 22 ms 8184 KB Ok
8 Correct 22 ms 8184 KB Ok
9 Correct 24 ms 8196 KB Ok
10 Correct 23 ms 8184 KB Ok
11 Correct 23 ms 8184 KB Ok
12 Correct 22 ms 8184 KB Ok
13 Correct 17 ms 8184 KB Ok
14 Correct 20 ms 8184 KB Ok
15 Correct 21 ms 8184 KB Ok
16 Correct 21 ms 8184 KB Ok
17 Correct 22 ms 8184 KB Ok
18 Correct 35 ms 8312 KB Ok
19 Correct 49 ms 9080 KB Ok
20 Correct 38 ms 8696 KB Ok
21 Correct 51 ms 9200 KB Ok
22 Correct 40 ms 8696 KB Ok
23 Correct 9 ms 8184 KB Ok
24 Correct 15 ms 8184 KB Ok
25 Correct 15 ms 8184 KB Ok
26 Correct 15 ms 8184 KB Ok
27 Correct 42 ms 8184 KB Ok
28 Correct 19 ms 8184 KB Ok
29 Correct 18 ms 8184 KB Ok
30 Correct 17 ms 8184 KB Ok
31 Correct 18 ms 8184 KB Ok
32 Correct 18 ms 8184 KB Ok
33 Correct 19 ms 8184 KB Ok
34 Correct 18 ms 8184 KB Ok
35 Correct 19 ms 8184 KB Ok
36 Correct 19 ms 8184 KB Ok
37 Correct 20 ms 8184 KB Ok
38 Correct 21 ms 8188 KB Ok
39 Correct 178 ms 17476 KB Ok
40 Correct 171 ms 16504 KB Ok
41 Correct 292 ms 20472 KB Ok
42 Correct 214 ms 19696 KB Ok
43 Correct 134 ms 13904 KB Ok
44 Correct 194 ms 19448 KB Ok
45 Correct 34 ms 8184 KB Ok
46 Correct 32 ms 8184 KB Ok
47 Correct 33 ms 8184 KB Ok
48 Correct 32 ms 8184 KB Ok
49 Correct 32 ms 8228 KB Ok
50 Correct 32 ms 8184 KB Ok
51 Correct 31 ms 8184 KB Ok
52 Correct 33 ms 8184 KB Ok
53 Correct 35 ms 8184 KB Ok
54 Correct 32 ms 8184 KB Ok
55 Correct 36 ms 8440 KB Ok
56 Correct 37 ms 8440 KB Ok
57 Correct 37 ms 8440 KB Ok
58 Correct 37 ms 8412 KB Ok
59 Correct 36 ms 8440 KB Ok
60 Correct 37 ms 8440 KB Ok
61 Correct 37 ms 8440 KB Ok
62 Correct 34 ms 8440 KB Ok
63 Correct 36 ms 8440 KB Ok
64 Correct 36 ms 8440 KB Ok
65 Correct 115 ms 9948 KB Ok
66 Correct 129 ms 10404 KB Ok
67 Correct 126 ms 10360 KB Ok
68 Correct 99 ms 9592 KB Ok
69 Correct 118 ms 9976 KB Ok
70 Correct 113 ms 9888 KB Ok
71 Correct 99 ms 9848 KB Ok
72 Correct 105 ms 9608 KB Ok
73 Correct 125 ms 10236 KB Ok
74 Correct 105 ms 9848 KB Ok
75 Correct 137 ms 10360 KB Ok
76 Correct 119 ms 10232 KB Ok
77 Correct 118 ms 9852 KB Ok
78 Correct 103 ms 9768 KB Ok
79 Correct 113 ms 9848 KB Ok
80 Correct 270 ms 17648 KB Ok
81 Correct 294 ms 18240 KB Ok
82 Correct 279 ms 17912 KB Ok
83 Correct 276 ms 17404 KB Ok
84 Correct 283 ms 18048 KB Ok
85 Correct 269 ms 17784 KB Ok
86 Correct 262 ms 17528 KB Ok
87 Correct 308 ms 17960 KB Ok
88 Correct 264 ms 17528 KB Ok
89 Correct 273 ms 17604 KB Ok
90 Correct 269 ms 18040 KB Ok
91 Correct 298 ms 18024 KB Ok
92 Correct 295 ms 18016 KB Ok
93 Correct 264 ms 17912 KB Ok
94 Correct 259 ms 17656 KB Ok
95 Correct 219 ms 12796 KB Ok
96 Correct 325 ms 14528 KB Ok
97 Correct 323 ms 13816 KB Ok
98 Correct 229 ms 12380 KB Ok
99 Correct 310 ms 13176 KB Ok
100 Correct 290 ms 14228 KB Ok
101 Correct 316 ms 13500 KB Ok
102 Correct 282 ms 14096 KB Ok
103 Correct 285 ms 14072 KB Ok
104 Correct 328 ms 14856 KB Ok
105 Correct 315 ms 14460 KB Ok
106 Correct 264 ms 13480 KB Ok
107 Correct 321 ms 13944 KB Ok
108 Correct 350 ms 14588 KB Ok
109 Correct 301 ms 13944 KB Ok
110 Correct 1171 ms 46392 KB Ok
111 Correct 1406 ms 48016 KB Ok
112 Correct 1212 ms 49016 KB Ok
113 Correct 1316 ms 47484 KB Ok
114 Correct 1301 ms 49784 KB Ok
115 Correct 1228 ms 48220 KB Ok
116 Correct 1164 ms 48988 KB Ok
117 Correct 1522 ms 47068 KB Ok
118 Correct 1318 ms 48744 KB Ok
119 Correct 1404 ms 47008 KB Ok
120 Correct 1358 ms 47480 KB Ok
121 Correct 1320 ms 47608 KB Ok
122 Correct 1241 ms 48120 KB Ok
123 Correct 1444 ms 48504 KB Ok
124 Correct 1096 ms 48168 KB Ok
125 Correct 799 ms 30456 KB Ok