oj.uz

Submission #341745

# Submission time Handle Problem Language Result Execution time Memory
341745 2020-12-30T20:29:47 Z Tosic Nice sequence (IZhO18_sequence) C++14
76 / 100
 2000 ms 18896 KB 
#include <bits/stdc++.h>
#define maxn 200010
using namespace std;

int n, m, t, prefS[maxn], res[maxn], ans;
vector<int> topV;
bool was[maxn];

void topSort(int x, int mx){
	// prefS[x+n] < prefS[x], prefS[x-m] < prefS[x]
	was[x] = 1;
	if(x+n <= mx and !was[x+n]){
		topSort(x+n, mx);
	}
	if(x-m >= 0 and !was[x-m]){
		topSort(x-m, mx);
	}
	topV.push_back(x);
}

bool ok(int mx){
	topV.clear();
	for(int i = 0; i <= mx; ++i){
		//cerr << was[i] << ' ';
		if(!was[i]){
			topSort(i, mx);
		}
	}
	for(int i = 0; i <= mx; ++i){
		prefS[topV[i]] = i;
		was[i] = 0;
	}
	for(int i = 0; i <= mx; ++i){
		if( (i+n<=mx and prefS[i] < prefS[i+n]) or (i-m >= 0 and prefS[i-m] > prefS[i]) ){
			return 0;
		}
	}
	for(int i = 1 ;i <mx+1;++i){
		res[i] = prefS[i]-prefS[i-1];
	}
	return 1;
}

int main(){
	ios_base::sync_with_stdio(0);
	cout.tie(0);
	cin.tie(0);
	cin >> t;
	while(t--){
		cin >> n >> m;
		ans = 0;
		int l = 0, r = maxn;
		while(l <= r){
			int mid = (l+r)/2;
			//cerr<<mid<<'\n';
			if(ok(mid)){
				l=mid+1;
				ans = max(ans, mid);
			} else {
				r = mid-1;
			}
		}
		cout << ans<<'\n';
		for(int i = 1; i <= ans; ++i){
			cout << res[i] << ' ';
		}
		cout << '\n';
	}
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 4460 KB Ok
2 Correct 26 ms 4460 KB Ok
3 Correct 23 ms 1644 KB Ok
4 Correct 24 ms 1516 KB Ok
5 Correct 24 ms 1516 KB Ok
6 Correct 24 ms 2156 KB Ok
7 Correct 24 ms 1516 KB Ok
8 Correct 26 ms 2156 KB Ok
9 Correct 24 ms 1388 KB Ok
10 Correct 24 ms 2924 KB Ok
11 Correct 23 ms 1516 KB Ok
12 Correct 23 ms 1388 KB Ok

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 2924 KB Ok
2 Correct 25 ms 2924 KB Ok
3 Correct 25 ms 2924 KB Ok
4 Correct 24 ms 2924 KB Ok
5 Correct 26 ms 2924 KB Ok
6 Correct 28 ms 3052 KB Ok
7 Correct 45 ms 3564 KB Ok
8 Correct 33 ms 3180 KB Ok
9 Correct 47 ms 3584 KB Ok
10 Correct 38 ms 3308 KB Ok

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 4460 KB Ok
2 Correct 25 ms 4460 KB Ok
3 Correct 24 ms 2924 KB Ok
4 Correct 23 ms 2412 KB Ok
5 Correct 26 ms 4460 KB Ok
6 Correct 26 ms 4460 KB Ok
7 Correct 25 ms 4460 KB Ok
8 Correct 25 ms 4460 KB Ok
9 Correct 29 ms 4460 KB Ok
10 Correct 25 ms 2924 KB Ok
11 Correct 23 ms 2412 KB Ok

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 2924 KB Ok
2 Correct 23 ms 1772 KB Ok
3 Correct 23 ms 1644 KB Ok
4 Correct 24 ms 1516 KB Ok
5 Correct 23 ms 1516 KB Ok
6 Correct 281 ms 10856 KB Ok
7 Correct 267 ms 11388 KB Ok
8 Correct 518 ms 14312 KB Ok
9 Correct 369 ms 12648 KB Ok
10 Correct 208 ms 6760 KB Ok
11 Correct 324 ms 12804 KB Ok

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 4460 KB Ok
2 Correct 26 ms 4460 KB Ok
3 Correct 23 ms 1644 KB Ok
4 Correct 24 ms 1516 KB Ok
5 Correct 24 ms 1516 KB Ok
6 Correct 24 ms 2156 KB Ok
7 Correct 24 ms 1516 KB Ok
8 Correct 26 ms 2156 KB Ok
9 Correct 24 ms 1388 KB Ok
10 Correct 24 ms 2924 KB Ok
11 Correct 23 ms 1516 KB Ok
12 Correct 23 ms 1388 KB Ok
13 Correct 11 ms 4460 KB Ok
14 Correct 25 ms 4460 KB Ok
15 Correct 24 ms 2924 KB Ok
16 Correct 23 ms 2412 KB Ok
17 Correct 26 ms 4460 KB Ok
18 Correct 26 ms 4460 KB Ok
19 Correct 25 ms 4460 KB Ok
20 Correct 25 ms 4460 KB Ok
21 Correct 29 ms 4460 KB Ok
22 Correct 25 ms 2924 KB Ok
23 Correct 23 ms 2412 KB Ok
24 Correct 26 ms 1388 KB Ok
25 Correct 27 ms 1388 KB Ok
26 Correct 27 ms 1388 KB Ok
27 Correct 26 ms 1388 KB Ok
28 Correct 26 ms 1480 KB Ok
29 Correct 25 ms 1388 KB Ok
30 Correct 25 ms 1388 KB Ok
31 Correct 26 ms 1388 KB Ok
32 Correct 27 ms 1388 KB Ok
33 Correct 26 ms 1456 KB Ok
34 Correct 34 ms 1644 KB Ok
35 Correct 33 ms 1644 KB Ok
36 Correct 34 ms 1644 KB Ok
37 Correct 33 ms 1644 KB Ok
38 Correct 32 ms 1644 KB Ok
39 Correct 33 ms 1644 KB Ok
40 Correct 34 ms 1644 KB Ok
41 Correct 33 ms 1644 KB Ok
42 Correct 33 ms 1644 KB Ok
43 Correct 33 ms 1644 KB Ok

Subtask #6
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 4460 KB Ok
2 Correct 26 ms 4460 KB Ok
3 Correct 23 ms 1644 KB Ok
4 Correct 24 ms 1516 KB Ok
5 Correct 24 ms 1516 KB Ok
6 Correct 24 ms 2156 KB Ok
7 Correct 24 ms 1516 KB Ok
8 Correct 26 ms 2156 KB Ok
9 Correct 24 ms 1388 KB Ok
10 Correct 24 ms 2924 KB Ok
11 Correct 23 ms 1516 KB Ok
12 Correct 23 ms 1388 KB Ok
13 Correct 24 ms 2924 KB Ok
14 Correct 25 ms 2924 KB Ok
15 Correct 25 ms 2924 KB Ok
16 Correct 24 ms 2924 KB Ok
17 Correct 26 ms 2924 KB Ok
18 Correct 28 ms 3052 KB Ok
19 Correct 45 ms 3564 KB Ok
20 Correct 33 ms 3180 KB Ok
21 Correct 47 ms 3584 KB Ok
22 Correct 38 ms 3308 KB Ok
23 Correct 11 ms 4460 KB Ok
24 Correct 25 ms 4460 KB Ok
25 Correct 24 ms 2924 KB Ok
26 Correct 23 ms 2412 KB Ok
27 Correct 26 ms 4460 KB Ok
28 Correct 26 ms 4460 KB Ok
29 Correct 25 ms 4460 KB Ok
30 Correct 25 ms 4460 KB Ok
31 Correct 29 ms 4460 KB Ok
32 Correct 25 ms 2924 KB Ok
33 Correct 23 ms 2412 KB Ok
34 Correct 26 ms 1388 KB Ok
35 Correct 27 ms 1388 KB Ok
36 Correct 27 ms 1388 KB Ok
37 Correct 26 ms 1388 KB Ok
38 Correct 26 ms 1480 KB Ok
39 Correct 25 ms 1388 KB Ok
40 Correct 25 ms 1388 KB Ok
41 Correct 26 ms 1388 KB Ok
42 Correct 27 ms 1388 KB Ok
43 Correct 26 ms 1456 KB Ok
44 Correct 34 ms 1644 KB Ok
45 Correct 33 ms 1644 KB Ok
46 Correct 34 ms 1644 KB Ok
47 Correct 33 ms 1644 KB Ok
48 Correct 32 ms 1644 KB Ok
49 Correct 33 ms 1644 KB Ok
50 Correct 34 ms 1644 KB Ok
51 Correct 33 ms 1644 KB Ok
52 Correct 33 ms 1644 KB Ok
53 Correct 33 ms 1644 KB Ok
54 Correct 205 ms 3436 KB Ok
55 Correct 231 ms 3752 KB Ok
56 Correct 227 ms 3692 KB Ok
57 Correct 167 ms 3052 KB Ok
58 Correct 202 ms 3180 KB Ok
59 Correct 188 ms 3052 KB Ok
60 Correct 167 ms 2924 KB Ok
61 Correct 173 ms 3052 KB Ok
62 Correct 221 ms 3468 KB Ok
63 Correct 197 ms 3180 KB Ok
64 Correct 224 ms 3692 KB Ok
65 Correct 203 ms 3308 KB Ok
66 Correct 190 ms 3180 KB Ok
67 Correct 171 ms 3180 KB Ok
68 Correct 193 ms 3308 KB Ok
69 Correct 376 ms 10864 KB Ok
70 Correct 401 ms 11440 KB Ok
71 Correct 364 ms 10860 KB Ok
72 Correct 388 ms 10732 KB Ok
73 Correct 367 ms 10924 KB Ok
74 Correct 367 ms 10836 KB Ok
75 Correct 378 ms 10348 KB Ok
76 Correct 385 ms 11116 KB Ok
77 Correct 358 ms 10456 KB Ok
78 Correct 391 ms 10964 KB Ok
79 Correct 374 ms 11076 KB Ok
80 Correct 372 ms 11116 KB Ok
81 Correct 365 ms 10988 KB Ok
82 Correct 397 ms 10988 KB Ok
83 Correct 353 ms 10512 KB Ok

Subtask #7
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 4460 KB Ok
2 Correct 26 ms 4460 KB Ok
3 Correct 23 ms 1644 KB Ok
4 Correct 24 ms 1516 KB Ok
5 Correct 24 ms 1516 KB Ok
6 Correct 24 ms 2156 KB Ok
7 Correct 24 ms 1516 KB Ok
8 Correct 26 ms 2156 KB Ok
9 Correct 24 ms 1388 KB Ok
10 Correct 24 ms 2924 KB Ok
11 Correct 23 ms 1516 KB Ok
12 Correct 23 ms 1388 KB Ok
13 Correct 24 ms 2924 KB Ok
14 Correct 25 ms 2924 KB Ok
15 Correct 25 ms 2924 KB Ok
16 Correct 24 ms 2924 KB Ok
17 Correct 26 ms 2924 KB Ok
18 Correct 28 ms 3052 KB Ok
19 Correct 45 ms 3564 KB Ok
20 Correct 33 ms 3180 KB Ok
21 Correct 47 ms 3584 KB Ok
22 Correct 38 ms 3308 KB Ok
23 Correct 11 ms 4460 KB Ok
24 Correct 25 ms 4460 KB Ok
25 Correct 24 ms 2924 KB Ok
26 Correct 23 ms 2412 KB Ok
27 Correct 26 ms 4460 KB Ok
28 Correct 26 ms 4460 KB Ok
29 Correct 25 ms 4460 KB Ok
30 Correct 25 ms 4460 KB Ok
31 Correct 29 ms 4460 KB Ok
32 Correct 25 ms 2924 KB Ok
33 Correct 23 ms 2412 KB Ok
34 Correct 24 ms 2924 KB Ok
35 Correct 23 ms 1772 KB Ok
36 Correct 23 ms 1644 KB Ok
37 Correct 24 ms 1516 KB Ok
38 Correct 23 ms 1516 KB Ok
39 Correct 281 ms 10856 KB Ok
40 Correct 267 ms 11388 KB Ok
41 Correct 518 ms 14312 KB Ok
42 Correct 369 ms 12648 KB Ok
43 Correct 208 ms 6760 KB Ok
44 Correct 324 ms 12804 KB Ok
45 Correct 26 ms 1388 KB Ok
46 Correct 27 ms 1388 KB Ok
47 Correct 27 ms 1388 KB Ok
48 Correct 26 ms 1388 KB Ok
49 Correct 26 ms 1480 KB Ok
50 Correct 25 ms 1388 KB Ok
51 Correct 25 ms 1388 KB Ok
52 Correct 26 ms 1388 KB Ok
53 Correct 27 ms 1388 KB Ok
54 Correct 26 ms 1456 KB Ok
55 Correct 34 ms 1644 KB Ok
56 Correct 33 ms 1644 KB Ok
57 Correct 34 ms 1644 KB Ok
58 Correct 33 ms 1644 KB Ok
59 Correct 32 ms 1644 KB Ok
60 Correct 33 ms 1644 KB Ok
61 Correct 34 ms 1644 KB Ok
62 Correct 33 ms 1644 KB Ok
63 Correct 33 ms 1644 KB Ok
64 Correct 33 ms 1644 KB Ok
65 Correct 205 ms 3436 KB Ok
66 Correct 231 ms 3752 KB Ok
67 Correct 227 ms 3692 KB Ok
68 Correct 167 ms 3052 KB Ok
69 Correct 202 ms 3180 KB Ok
70 Correct 188 ms 3052 KB Ok
71 Correct 167 ms 2924 KB Ok
72 Correct 173 ms 3052 KB Ok
73 Correct 221 ms 3468 KB Ok
74 Correct 197 ms 3180 KB Ok
75 Correct 224 ms 3692 KB Ok
76 Correct 203 ms 3308 KB Ok
77 Correct 190 ms 3180 KB Ok
78 Correct 171 ms 3180 KB Ok
79 Correct 193 ms 3308 KB Ok
80 Correct 376 ms 10864 KB Ok
81 Correct 401 ms 11440 KB Ok
82 Correct 364 ms 10860 KB Ok
83 Correct 388 ms 10732 KB Ok
84 Correct 367 ms 10924 KB Ok
85 Correct 367 ms 10836 KB Ok
86 Correct 378 ms 10348 KB Ok
87 Correct 385 ms 11116 KB Ok
88 Correct 358 ms 10456 KB Ok
89 Correct 391 ms 10964 KB Ok
90 Correct 374 ms 11076 KB Ok
91 Correct 372 ms 11116 KB Ok
92 Correct 365 ms 10988 KB Ok
93 Correct 397 ms 10988 KB Ok
94 Correct 353 ms 10512 KB Ok
95 Execution timed out 2065 ms 18896 KB Time limit exceeded
96 Halted 0 ms 0 KB -