oj.uz

Submission #341740

# Submission time Handle Problem Language Result Execution time Memory
341740 2020-12-30T20:22:28 Z Tosic Nice sequence (IZhO18_sequence) C++14
61 / 100
 2000 ms 17764 KB 
#include <bits/stdc++.h>
#define maxn 100010
using namespace std;

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

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();
	was.clear();
	res.clear();
	was.resize(maxn+2, 0);
	//cerr << mx << ' ' << n << ' ' << m << '\n';
	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;
	}
	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.push_back(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;
			}
		}
		ok(ans);
		cout << res.size()<<'\n';
		for(auto i:res){
			cout << i << ' ';
		}
		cout << '\n';
	}
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 4336 KB Ok
2 Correct 24 ms 4336 KB Ok
3 Correct 23 ms 1520 KB Ok
4 Correct 23 ms 1520 KB Ok
5 Correct 23 ms 1520 KB Ok
6 Correct 23 ms 2032 KB Ok
7 Correct 23 ms 1392 KB Ok
8 Correct 23 ms 2160 KB Ok
9 Correct 23 ms 1392 KB Ok
10 Correct 24 ms 2928 KB Ok
11 Correct 23 ms 1392 KB Ok
12 Correct 25 ms 1392 KB Ok

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 2800 KB Ok
2 Correct 23 ms 2800 KB Ok
3 Correct 24 ms 2800 KB Ok
4 Correct 23 ms 2800 KB Ok
5 Correct 26 ms 2928 KB Ok
6 Correct 28 ms 2928 KB Ok
7 Correct 49 ms 3440 KB Ok
8 Correct 35 ms 3184 KB Ok
9 Correct 53 ms 3696 KB Ok
10 Correct 40 ms 3312 KB Ok

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 4336 KB Ok
2 Correct 25 ms 4336 KB Ok
3 Correct 24 ms 2800 KB Ok
4 Correct 23 ms 2288 KB Ok
5 Correct 24 ms 4336 KB Ok
6 Correct 24 ms 4336 KB Ok
7 Correct 24 ms 4336 KB Ok
8 Correct 25 ms 4336 KB Ok
9 Correct 24 ms 4336 KB Ok
10 Correct 24 ms 2800 KB Ok
11 Correct 23 ms 2288 KB Ok

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 2800 KB Ok
2 Correct 22 ms 1648 KB Ok
3 Correct 24 ms 1648 KB Ok
4 Correct 22 ms 1392 KB Ok
5 Correct 22 ms 1392 KB Ok
6 Execution timed out 2083 ms 17764 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 4336 KB Ok
2 Correct 24 ms 4336 KB Ok
3 Correct 23 ms 1520 KB Ok
4 Correct 23 ms 1520 KB Ok
5 Correct 23 ms 1520 KB Ok
6 Correct 23 ms 2032 KB Ok
7 Correct 23 ms 1392 KB Ok
8 Correct 23 ms 2160 KB Ok
9 Correct 23 ms 1392 KB Ok
10 Correct 24 ms 2928 KB Ok
11 Correct 23 ms 1392 KB Ok
12 Correct 25 ms 1392 KB Ok
13 Correct 9 ms 4336 KB Ok
14 Correct 25 ms 4336 KB Ok
15 Correct 24 ms 2800 KB Ok
16 Correct 23 ms 2288 KB Ok
17 Correct 24 ms 4336 KB Ok
18 Correct 24 ms 4336 KB Ok
19 Correct 24 ms 4336 KB Ok
20 Correct 25 ms 4336 KB Ok
21 Correct 24 ms 4336 KB Ok
22 Correct 24 ms 2800 KB Ok
23 Correct 23 ms 2288 KB Ok
24 Correct 26 ms 1264 KB Ok
25 Correct 26 ms 1264 KB Ok
26 Correct 29 ms 1520 KB Ok
27 Correct 26 ms 1264 KB Ok
28 Correct 25 ms 1392 KB Ok
29 Correct 26 ms 1264 KB Ok
30 Correct 25 ms 1264 KB Ok
31 Correct 26 ms 1264 KB Ok
32 Correct 28 ms 1264 KB Ok
33 Correct 26 ms 1264 KB Ok
34 Correct 33 ms 1648 KB Ok
35 Correct 34 ms 1648 KB Ok
36 Correct 34 ms 1648 KB Ok
37 Correct 34 ms 1648 KB Ok
38 Correct 33 ms 1648 KB Ok
39 Correct 33 ms 1648 KB Ok
40 Correct 35 ms 1672 KB Ok
41 Correct 33 ms 1648 KB Ok
42 Correct 34 ms 1648 KB Ok
43 Correct 34 ms 1648 KB Ok

Subtask #6
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 4336 KB Ok
2 Correct 24 ms 4336 KB Ok
3 Correct 23 ms 1520 KB Ok
4 Correct 23 ms 1520 KB Ok
5 Correct 23 ms 1520 KB Ok
6 Correct 23 ms 2032 KB Ok
7 Correct 23 ms 1392 KB Ok
8 Correct 23 ms 2160 KB Ok
9 Correct 23 ms 1392 KB Ok
10 Correct 24 ms 2928 KB Ok
11 Correct 23 ms 1392 KB Ok
12 Correct 25 ms 1392 KB Ok
13 Correct 23 ms 2800 KB Ok
14 Correct 23 ms 2800 KB Ok
15 Correct 24 ms 2800 KB Ok
16 Correct 23 ms 2800 KB Ok
17 Correct 26 ms 2928 KB Ok
18 Correct 28 ms 2928 KB Ok
19 Correct 49 ms 3440 KB Ok
20 Correct 35 ms 3184 KB Ok
21 Correct 53 ms 3696 KB Ok
22 Correct 40 ms 3312 KB Ok
23 Correct 9 ms 4336 KB Ok
24 Correct 25 ms 4336 KB Ok
25 Correct 24 ms 2800 KB Ok
26 Correct 23 ms 2288 KB Ok
27 Correct 24 ms 4336 KB Ok
28 Correct 24 ms 4336 KB Ok
29 Correct 24 ms 4336 KB Ok
30 Correct 25 ms 4336 KB Ok
31 Correct 24 ms 4336 KB Ok
32 Correct 24 ms 2800 KB Ok
33 Correct 23 ms 2288 KB Ok
34 Correct 26 ms 1264 KB Ok
35 Correct 26 ms 1264 KB Ok
36 Correct 29 ms 1520 KB Ok
37 Correct 26 ms 1264 KB Ok
38 Correct 25 ms 1392 KB Ok
39 Correct 26 ms 1264 KB Ok
40 Correct 25 ms 1264 KB Ok
41 Correct 26 ms 1264 KB Ok
42 Correct 28 ms 1264 KB Ok
43 Correct 26 ms 1264 KB Ok
44 Correct 33 ms 1648 KB Ok
45 Correct 34 ms 1648 KB Ok
46 Correct 34 ms 1648 KB Ok
47 Correct 34 ms 1648 KB Ok
48 Correct 33 ms 1648 KB Ok
49 Correct 33 ms 1648 KB Ok
50 Correct 35 ms 1672 KB Ok
51 Correct 33 ms 1648 KB Ok
52 Correct 34 ms 1648 KB Ok
53 Correct 34 ms 1648 KB Ok
54 Correct 244 ms 3684 KB Ok
55 Correct 282 ms 3940 KB Ok
56 Correct 274 ms 3940 KB Ok
57 Correct 205 ms 3300 KB Ok
58 Correct 238 ms 3556 KB Ok
59 Correct 230 ms 3300 KB Ok
60 Correct 202 ms 3044 KB Ok
61 Correct 207 ms 3300 KB Ok
62 Correct 260 ms 3684 KB Ok
63 Correct 219 ms 3380 KB Ok
64 Correct 271 ms 3940 KB Ok
65 Correct 243 ms 3556 KB Ok
66 Correct 223 ms 3428 KB Ok
67 Correct 204 ms 3300 KB Ok
68 Correct 230 ms 3556 KB Ok
69 Correct 463 ms 14308 KB Ok
70 Correct 506 ms 14976 KB Ok
71 Correct 459 ms 14308 KB Ok
72 Correct 483 ms 14308 KB Ok
73 Correct 460 ms 14436 KB Ok
74 Correct 453 ms 14180 KB Ok
75 Correct 470 ms 13924 KB Ok
76 Correct 497 ms 14564 KB Ok
77 Correct 449 ms 14052 KB Ok
78 Correct 488 ms 14564 KB Ok
79 Correct 479 ms 14784 KB Ok
80 Correct 470 ms 14564 KB Ok
81 Correct 465 ms 14464 KB Ok
82 Correct 466 ms 14436 KB Ok
83 Correct 449 ms 13924 KB Ok

Subtask #7
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 4336 KB Ok
2 Correct 24 ms 4336 KB Ok
3 Correct 23 ms 1520 KB Ok
4 Correct 23 ms 1520 KB Ok
5 Correct 23 ms 1520 KB Ok
6 Correct 23 ms 2032 KB Ok
7 Correct 23 ms 1392 KB Ok
8 Correct 23 ms 2160 KB Ok
9 Correct 23 ms 1392 KB Ok
10 Correct 24 ms 2928 KB Ok
11 Correct 23 ms 1392 KB Ok
12 Correct 25 ms 1392 KB Ok
13 Correct 23 ms 2800 KB Ok
14 Correct 23 ms 2800 KB Ok
15 Correct 24 ms 2800 KB Ok
16 Correct 23 ms 2800 KB Ok
17 Correct 26 ms 2928 KB Ok
18 Correct 28 ms 2928 KB Ok
19 Correct 49 ms 3440 KB Ok
20 Correct 35 ms 3184 KB Ok
21 Correct 53 ms 3696 KB Ok
22 Correct 40 ms 3312 KB Ok
23 Correct 9 ms 4336 KB Ok
24 Correct 25 ms 4336 KB Ok
25 Correct 24 ms 2800 KB Ok
26 Correct 23 ms 2288 KB Ok
27 Correct 24 ms 4336 KB Ok
28 Correct 24 ms 4336 KB Ok
29 Correct 24 ms 4336 KB Ok
30 Correct 25 ms 4336 KB Ok
31 Correct 24 ms 4336 KB Ok
32 Correct 24 ms 2800 KB Ok
33 Correct 23 ms 2288 KB Ok
34 Correct 23 ms 2800 KB Ok
35 Correct 22 ms 1648 KB Ok
36 Correct 24 ms 1648 KB Ok
37 Correct 22 ms 1392 KB Ok
38 Correct 22 ms 1392 KB Ok
39 Execution timed out 2083 ms 17764 KB Time limit exceeded
40 Halted 0 ms 0 KB -