oj.uz

Submission #334957

# Submission time Handle Problem Language Result Execution time Memory
334957 2020-12-10T12:57:53 Z amunduzbaev Nice sequence (IZhO18_sequence) C++14
76 / 100
 2000 ms 44268 KB 
#include <bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define ub upper_bound
#define lb lower_bound
#define ll long long 
#define ld long double 
#define pii pair<int, int>
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(),x.rend()
#define prc(n) fixed << setprecision(n)
#define fastios ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define pi acos(-1);
const int inf = 1e9 + 7;
const int N = 1e6 + 5;

int len, n, m, pref[N];
bool vis[N];
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;
}

void solve(){
	cin>>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);
	cout<<l<<"\n";
	if(l){
		for(int i=1;i<=l;i++) cout<<pref[i] - pref[i-1]<<" ";
		cout<<"\n";
	}
	return;
}

int main(){
	int t;
	cin>>t;
	while(t--) solve();
	return 0;
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 8416 KB Ok
2 Correct 62 ms 8416 KB Ok
3 Correct 52 ms 2656 KB Ok
4 Correct 54 ms 3040 KB Ok
5 Correct 53 ms 2656 KB Ok
6 Correct 57 ms 3808 KB Ok
7 Correct 54 ms 2528 KB Ok
8 Correct 50 ms 3808 KB Ok
9 Correct 53 ms 2656 KB Ok
10 Correct 55 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 74 ms 8416 KB Ok
2 Correct 69 ms 8568 KB Ok
3 Correct 68 ms 8416 KB Ok
4 Correct 67 ms 8416 KB Ok
5 Correct 65 ms 8416 KB Ok
6 Correct 69 ms 8544 KB Ok
7 Correct 84 ms 8812 KB Ok
8 Correct 81 ms 8672 KB Ok
9 Correct 95 ms 9064 KB Ok
10 Correct 78 ms 8800 KB Ok

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 8416 KB Ok
2 Correct 86 ms 8416 KB Ok
3 Correct 69 ms 8416 KB Ok
4 Correct 85 ms 8416 KB Ok
5 Correct 76 ms 8416 KB Ok
6 Correct 81 ms 8416 KB Ok
7 Correct 68 ms 8416 KB Ok
8 Correct 75 ms 8416 KB Ok
9 Correct 73 ms 8476 KB Ok
10 Correct 83 ms 8416 KB Ok
11 Correct 82 ms 8344 KB Ok

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 94 ms 8416 KB Ok
2 Correct 85 ms 8416 KB Ok
3 Correct 85 ms 8416 KB Ok
4 Correct 89 ms 8416 KB Ok
5 Correct 85 ms 8416 KB Ok
6 Correct 389 ms 12128 KB Ok
7 Correct 371 ms 10720 KB Ok
8 Correct 670 ms 13920 KB Ok
9 Correct 490 ms 13024 KB Ok
10 Correct 295 ms 9824 KB Ok
11 Correct 436 ms 12128 KB Ok

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 8416 KB Ok
2 Correct 62 ms 8416 KB Ok
3 Correct 52 ms 2656 KB Ok
4 Correct 54 ms 3040 KB Ok
5 Correct 53 ms 2656 KB Ok
6 Correct 57 ms 3808 KB Ok
7 Correct 54 ms 2528 KB Ok
8 Correct 50 ms 3808 KB Ok
9 Correct 53 ms 2656 KB Ok
10 Correct 55 ms 5344 KB Ok
11 Correct 54 ms 2528 KB Ok
12 Correct 51 ms 2400 KB Ok
13 Correct 29 ms 8416 KB Ok
14 Correct 86 ms 8416 KB Ok
15 Correct 69 ms 8416 KB Ok
16 Correct 85 ms 8416 KB Ok
17 Correct 76 ms 8416 KB Ok
18 Correct 81 ms 8416 KB Ok
19 Correct 68 ms 8416 KB Ok
20 Correct 75 ms 8416 KB Ok
21 Correct 73 ms 8476 KB Ok
22 Correct 83 ms 8416 KB Ok
23 Correct 82 ms 8344 KB Ok
24 Correct 64 ms 2272 KB Ok
25 Correct 61 ms 2400 KB Ok
26 Correct 63 ms 2656 KB Ok
27 Correct 64 ms 2784 KB Ok
28 Correct 62 ms 2400 KB Ok
29 Correct 59 ms 4320 KB Ok
30 Correct 66 ms 2528 KB Ok
31 Correct 66 ms 2400 KB Ok
32 Correct 65 ms 2272 KB Ok
33 Correct 65 ms 2528 KB Ok
34 Correct 88 ms 8544 KB Ok
35 Correct 93 ms 8672 KB Ok
36 Correct 87 ms 8672 KB Ok
37 Correct 94 ms 8672 KB Ok
38 Correct 91 ms 8672 KB Ok
39 Correct 95 ms 8544 KB Ok
40 Correct 93 ms 8672 KB Ok
41 Correct 90 ms 8672 KB Ok
42 Correct 91 ms 8544 KB Ok
43 Correct 96 ms 8672 KB Ok

Subtask #6
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 8416 KB Ok
2 Correct 62 ms 8416 KB Ok
3 Correct 52 ms 2656 KB Ok
4 Correct 54 ms 3040 KB Ok
5 Correct 53 ms 2656 KB Ok
6 Correct 57 ms 3808 KB Ok
7 Correct 54 ms 2528 KB Ok
8 Correct 50 ms 3808 KB Ok
9 Correct 53 ms 2656 KB Ok
10 Correct 55 ms 5344 KB Ok
11 Correct 54 ms 2528 KB Ok
12 Correct 51 ms 2400 KB Ok
13 Correct 74 ms 8416 KB Ok
14 Correct 69 ms 8568 KB Ok
15 Correct 68 ms 8416 KB Ok
16 Correct 67 ms 8416 KB Ok
17 Correct 65 ms 8416 KB Ok
18 Correct 69 ms 8544 KB Ok
19 Correct 84 ms 8812 KB Ok
20 Correct 81 ms 8672 KB Ok
21 Correct 95 ms 9064 KB Ok
22 Correct 78 ms 8800 KB Ok
23 Correct 29 ms 8416 KB Ok
24 Correct 86 ms 8416 KB Ok
25 Correct 69 ms 8416 KB Ok
26 Correct 85 ms 8416 KB Ok
27 Correct 76 ms 8416 KB Ok
28 Correct 81 ms 8416 KB Ok
29 Correct 68 ms 8416 KB Ok
30 Correct 75 ms 8416 KB Ok
31 Correct 73 ms 8476 KB Ok
32 Correct 83 ms 8416 KB Ok
33 Correct 82 ms 8344 KB Ok
34 Correct 64 ms 2272 KB Ok
35 Correct 61 ms 2400 KB Ok
36 Correct 63 ms 2656 KB Ok
37 Correct 64 ms 2784 KB Ok
38 Correct 62 ms 2400 KB Ok
39 Correct 59 ms 4320 KB Ok
40 Correct 66 ms 2528 KB Ok
41 Correct 66 ms 2400 KB Ok
42 Correct 65 ms 2272 KB Ok
43 Correct 65 ms 2528 KB Ok
44 Correct 88 ms 8544 KB Ok
45 Correct 93 ms 8672 KB Ok
46 Correct 87 ms 8672 KB Ok
47 Correct 94 ms 8672 KB Ok
48 Correct 91 ms 8672 KB Ok
49 Correct 95 ms 8544 KB Ok
50 Correct 93 ms 8672 KB Ok
51 Correct 90 ms 8672 KB Ok
52 Correct 91 ms 8544 KB Ok
53 Correct 96 ms 8672 KB Ok
54 Correct 275 ms 3936 KB Ok
55 Correct 311 ms 4192 KB Ok
56 Correct 305 ms 4320 KB Ok
57 Correct 226 ms 3680 KB Ok
58 Correct 262 ms 3808 KB Ok
59 Correct 247 ms 3552 KB Ok
60 Correct 221 ms 3424 KB Ok
61 Correct 231 ms 3552 KB Ok
62 Correct 292 ms 3996 KB Ok
63 Correct 247 ms 3680 KB Ok
64 Correct 299 ms 4192 KB Ok
65 Correct 274 ms 3808 KB Ok
66 Correct 253 ms 3892 KB Ok
67 Correct 226 ms 3808 KB Ok
68 Correct 256 ms 3936 KB Ok
69 Correct 490 ms 14412 KB Ok
70 Correct 508 ms 15072 KB Ok
71 Correct 479 ms 14560 KB Ok
72 Correct 489 ms 14432 KB Ok
73 Correct 465 ms 14608 KB Ok
74 Correct 476 ms 14304 KB Ok
75 Correct 484 ms 14220 KB Ok
76 Correct 489 ms 14816 KB Ok
77 Correct 472 ms 14076 KB Ok
78 Correct 487 ms 14432 KB Ok
79 Correct 487 ms 14816 KB Ok
80 Correct 481 ms 14816 KB Ok
81 Correct 489 ms 14688 KB Ok
82 Correct 477 ms 14560 KB Ok
83 Correct 473 ms 14176 KB Ok

Subtask #7
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 8416 KB Ok
2 Correct 62 ms 8416 KB Ok
3 Correct 52 ms 2656 KB Ok
4 Correct 54 ms 3040 KB Ok
5 Correct 53 ms 2656 KB Ok
6 Correct 57 ms 3808 KB Ok
7 Correct 54 ms 2528 KB Ok
8 Correct 50 ms 3808 KB Ok
9 Correct 53 ms 2656 KB Ok
10 Correct 55 ms 5344 KB Ok
11 Correct 54 ms 2528 KB Ok
12 Correct 51 ms 2400 KB Ok
13 Correct 74 ms 8416 KB Ok
14 Correct 69 ms 8568 KB Ok
15 Correct 68 ms 8416 KB Ok
16 Correct 67 ms 8416 KB Ok
17 Correct 65 ms 8416 KB Ok
18 Correct 69 ms 8544 KB Ok
19 Correct 84 ms 8812 KB Ok
20 Correct 81 ms 8672 KB Ok
21 Correct 95 ms 9064 KB Ok
22 Correct 78 ms 8800 KB Ok
23 Correct 29 ms 8416 KB Ok
24 Correct 86 ms 8416 KB Ok
25 Correct 69 ms 8416 KB Ok
26 Correct 85 ms 8416 KB Ok
27 Correct 76 ms 8416 KB Ok
28 Correct 81 ms 8416 KB Ok
29 Correct 68 ms 8416 KB Ok
30 Correct 75 ms 8416 KB Ok
31 Correct 73 ms 8476 KB Ok
32 Correct 83 ms 8416 KB Ok
33 Correct 82 ms 8344 KB Ok
34 Correct 94 ms 8416 KB Ok
35 Correct 85 ms 8416 KB Ok
36 Correct 85 ms 8416 KB Ok
37 Correct 89 ms 8416 KB Ok
38 Correct 85 ms 8416 KB Ok
39 Correct 389 ms 12128 KB Ok
40 Correct 371 ms 10720 KB Ok
41 Correct 670 ms 13920 KB Ok
42 Correct 490 ms 13024 KB Ok
43 Correct 295 ms 9824 KB Ok
44 Correct 436 ms 12128 KB Ok
45 Correct 64 ms 2272 KB Ok
46 Correct 61 ms 2400 KB Ok
47 Correct 63 ms 2656 KB Ok
48 Correct 64 ms 2784 KB Ok
49 Correct 62 ms 2400 KB Ok
50 Correct 59 ms 4320 KB Ok
51 Correct 66 ms 2528 KB Ok
52 Correct 66 ms 2400 KB Ok
53 Correct 65 ms 2272 KB Ok
54 Correct 65 ms 2528 KB Ok
55 Correct 88 ms 8544 KB Ok
56 Correct 93 ms 8672 KB Ok
57 Correct 87 ms 8672 KB Ok
58 Correct 94 ms 8672 KB Ok
59 Correct 91 ms 8672 KB Ok
60 Correct 95 ms 8544 KB Ok
61 Correct 93 ms 8672 KB Ok
62 Correct 90 ms 8672 KB Ok
63 Correct 91 ms 8544 KB Ok
64 Correct 96 ms 8672 KB Ok
65 Correct 275 ms 3936 KB Ok
66 Correct 311 ms 4192 KB Ok
67 Correct 305 ms 4320 KB Ok
68 Correct 226 ms 3680 KB Ok
69 Correct 262 ms 3808 KB Ok
70 Correct 247 ms 3552 KB Ok
71 Correct 221 ms 3424 KB Ok
72 Correct 231 ms 3552 KB Ok
73 Correct 292 ms 3996 KB Ok
74 Correct 247 ms 3680 KB Ok
75 Correct 299 ms 4192 KB Ok
76 Correct 274 ms 3808 KB Ok
77 Correct 253 ms 3892 KB Ok
78 Correct 226 ms 3808 KB Ok
79 Correct 256 ms 3936 KB Ok
80 Correct 490 ms 14412 KB Ok
81 Correct 508 ms 15072 KB Ok
82 Correct 479 ms 14560 KB Ok
83 Correct 489 ms 14432 KB Ok
84 Correct 465 ms 14608 KB Ok
85 Correct 476 ms 14304 KB Ok
86 Correct 484 ms 14220 KB Ok
87 Correct 489 ms 14816 KB Ok
88 Correct 472 ms 14076 KB Ok
89 Correct 487 ms 14432 KB Ok
90 Correct 487 ms 14816 KB Ok
91 Correct 481 ms 14816 KB Ok
92 Correct 489 ms 14688 KB Ok
93 Correct 477 ms 14560 KB Ok
94 Correct 473 ms 14176 KB Ok
95 Correct 584 ms 7644 KB Ok
96 Correct 871 ms 9564 KB Ok
97 Correct 833 ms 8540 KB Ok
98 Correct 612 ms 7796 KB Ok
99 Correct 746 ms 8028 KB Ok
100 Correct 768 ms 8156 KB Ok
101 Correct 787 ms 8540 KB Ok
102 Correct 754 ms 8028 KB Ok
103 Correct 729 ms 8424 KB Ok
104 Correct 896 ms 9692 KB Ok
105 Correct 840 ms 9436 KB Ok
106 Correct 746 ms 9052 KB Ok
107 Correct 809 ms 8764 KB Ok
108 Correct 875 ms 9820 KB Ok
109 Correct 808 ms 9692 KB Ok
110 Correct 1997 ms 41664 KB Ok
111 Execution timed out 2049 ms 44268 KB Time limit exceeded
112 Halted 0 ms 0 KB -