oj.uz

Submission #634055

# Submission time Handle Problem Language Result Execution time Memory
634055 2022-08-23T18:13:39 Z Tob Nice sequence (IZhO18_sequence) C++14
76 / 100
 1308 ms 34072 KB 
#include <bits/stdc++.h>

#define ll long long
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define pb push_back
#define FIO ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)

using namespace std;

ll nxt() {ll num; cin >> num; return num;}

const int maxn = 2e5 + 7;

int n, m;
bool ndag;
vector <int> v;
vector <int> adj[maxn];
ll val[maxn], bio[maxn], ps[maxn];

void dfs(int x) {
	bio[x] = 1;
	for (auto it : adj[x]) {
		if (bio[it] == 2) continue;
		if (bio[it] == 1) {
			ndag = 1;
			continue;
		}
		dfs(it);
	}
	bio[x] = 2;
	v.pb(x);
}

bool stask(int ma) {
	for (int i = 0; i <= ma; i++) {
		adj[i].clear();
	}
	v.clear();
	for (int i = 0; i <= ma; i++) bio[i] = 0;
	ndag = 0;
	
	for (int i = 0; i <= ma; i++) {
		if (i + m <= ma) adj[i].pb(i+m);
		if (i + n <= ma) adj[i+n].pb(i);
	}
	
	for (int i = 0; i <= ma; i++) {
		if (!bio[i]) dfs(i);
	}
	
	if (ndag) return 1;
	
	int cc = ma;
	
	for (auto it : v) {
		val[it] = cc--;
	}
	
	for (int i = 1; i <= ma; i++) {
		ps[i] = ps[i-1] + val[i] - val[i-1];
		if (i - m >= 0) {
			if (ps[i] - ps[i-m] <= 0) return 1;
		}
		if (i - n >= 0) {
			if (ps[i] - ps[i-n] >= 0) return 1;
		}
	}
	return 0;
}

void task() {
	cin >> n >> m;
	for (int i = 0; i < maxn; i++)  adj[i].reserve(2);

	ll lo = max(n, m) - 1, hi = max(n, m) * 2;
	
	if (n == m) {
		cout << lo << "\n"; 
		for (int i = 1; i <= lo; i++) cout << "1 ";
		cout << "\n";
		return;
	}
	
	while (lo < hi) {
		int mid = (lo + hi + 1) / 2;
		if (stask(mid)) hi = mid - 1;
		else lo = mid;
	}
	
	stask(hi);
	
	cout << hi << "\n";
	
	for (int i = 1; i <= hi; i++) {
		cout << val[i] - val[i-1] << " ";
	}
	cout << "\n";
}

int main () {
	FIO;
	int t;
	
	cin >> t;
	
	while (t--) task();

	return 0;
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 11220 KB Ok
2 Correct 11 ms 11296 KB Ok
3 Correct 15 ms 11196 KB Ok
4 Correct 11 ms 11220 KB Ok
5 Correct 11 ms 11220 KB Ok
6 Correct 15 ms 11296 KB Ok
7 Correct 12 ms 11296 KB Ok
8 Correct 11 ms 11220 KB Ok
9 Correct 15 ms 11288 KB Ok
10 Correct 13 ms 11220 KB Ok
11 Correct 15 ms 11300 KB Ok
12 Correct 12 ms 11164 KB Ok

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 11296 KB Ok
2 Correct 11 ms 11288 KB Ok
3 Correct 11 ms 11296 KB Ok
4 Correct 11 ms 11220 KB Ok
5 Correct 11 ms 11220 KB Ok
6 Correct 16 ms 11476 KB Ok
7 Correct 42 ms 12488 KB Ok
8 Correct 31 ms 11812 KB Ok
9 Correct 53 ms 12720 KB Ok
10 Correct 32 ms 12092 KB Ok

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 11220 KB Ok
2 Correct 11 ms 11228 KB Ok
3 Correct 11 ms 11296 KB Ok
4 Correct 11 ms 11220 KB Ok
5 Correct 11 ms 11296 KB Ok
6 Correct 12 ms 11220 KB Ok
7 Correct 12 ms 11228 KB Ok
8 Correct 12 ms 11300 KB Ok
9 Correct 11 ms 11296 KB Ok
10 Correct 11 ms 11220 KB Ok
11 Correct 12 ms 11300 KB Ok

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 11292 KB Ok
2 Correct 12 ms 11304 KB Ok
3 Correct 11 ms 11220 KB Ok
4 Correct 12 ms 11304 KB Ok
5 Correct 12 ms 11296 KB Ok
6 Correct 435 ms 26572 KB Ok
7 Correct 380 ms 28092 KB Ok
8 Correct 722 ms 30140 KB Ok
9 Correct 541 ms 29548 KB Ok
10 Correct 332 ms 21696 KB Ok
11 Correct 581 ms 30912 KB Ok

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 11220 KB Ok
2 Correct 11 ms 11296 KB Ok
3 Correct 15 ms 11196 KB Ok
4 Correct 11 ms 11220 KB Ok
5 Correct 11 ms 11220 KB Ok
6 Correct 15 ms 11296 KB Ok
7 Correct 12 ms 11296 KB Ok
8 Correct 11 ms 11220 KB Ok
9 Correct 15 ms 11288 KB Ok
10 Correct 13 ms 11220 KB Ok
11 Correct 15 ms 11300 KB Ok
12 Correct 12 ms 11164 KB Ok
13 Correct 10 ms 11220 KB Ok
14 Correct 11 ms 11228 KB Ok
15 Correct 11 ms 11296 KB Ok
16 Correct 11 ms 11220 KB Ok
17 Correct 11 ms 11296 KB Ok
18 Correct 12 ms 11220 KB Ok
19 Correct 12 ms 11228 KB Ok
20 Correct 12 ms 11300 KB Ok
21 Correct 11 ms 11296 KB Ok
22 Correct 11 ms 11220 KB Ok
23 Correct 12 ms 11300 KB Ok
24 Correct 16 ms 11348 KB Ok
25 Correct 19 ms 11376 KB Ok
26 Correct 16 ms 11344 KB Ok
27 Correct 16 ms 11424 KB Ok
28 Correct 16 ms 11348 KB Ok
29 Correct 16 ms 11456 KB Ok
30 Correct 15 ms 11404 KB Ok
31 Correct 21 ms 11348 KB Ok
32 Correct 17 ms 11348 KB Ok
33 Correct 15 ms 11440 KB Ok
34 Correct 25 ms 11736 KB Ok
35 Correct 24 ms 11704 KB Ok
36 Correct 23 ms 11732 KB Ok
37 Correct 24 ms 11732 KB Ok
38 Correct 23 ms 11732 KB Ok
39 Correct 23 ms 11732 KB Ok
40 Correct 25 ms 11716 KB Ok
41 Correct 23 ms 11732 KB Ok
42 Correct 27 ms 11724 KB Ok
43 Correct 28 ms 11732 KB Ok

Subtask #6
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 11220 KB Ok
2 Correct 11 ms 11296 KB Ok
3 Correct 15 ms 11196 KB Ok
4 Correct 11 ms 11220 KB Ok
5 Correct 11 ms 11220 KB Ok
6 Correct 15 ms 11296 KB Ok
7 Correct 12 ms 11296 KB Ok
8 Correct 11 ms 11220 KB Ok
9 Correct 15 ms 11288 KB Ok
10 Correct 13 ms 11220 KB Ok
11 Correct 15 ms 11300 KB Ok
12 Correct 12 ms 11164 KB Ok
13 Correct 12 ms 11296 KB Ok
14 Correct 11 ms 11288 KB Ok
15 Correct 11 ms 11296 KB Ok
16 Correct 11 ms 11220 KB Ok
17 Correct 11 ms 11220 KB Ok
18 Correct 16 ms 11476 KB Ok
19 Correct 42 ms 12488 KB Ok
20 Correct 31 ms 11812 KB Ok
21 Correct 53 ms 12720 KB Ok
22 Correct 32 ms 12092 KB Ok
23 Correct 10 ms 11220 KB Ok
24 Correct 11 ms 11228 KB Ok
25 Correct 11 ms 11296 KB Ok
26 Correct 11 ms 11220 KB Ok
27 Correct 11 ms 11296 KB Ok
28 Correct 12 ms 11220 KB Ok
29 Correct 12 ms 11228 KB Ok
30 Correct 12 ms 11300 KB Ok
31 Correct 11 ms 11296 KB Ok
32 Correct 11 ms 11220 KB Ok
33 Correct 12 ms 11300 KB Ok
34 Correct 16 ms 11348 KB Ok
35 Correct 19 ms 11376 KB Ok
36 Correct 16 ms 11344 KB Ok
37 Correct 16 ms 11424 KB Ok
38 Correct 16 ms 11348 KB Ok
39 Correct 16 ms 11456 KB Ok
40 Correct 15 ms 11404 KB Ok
41 Correct 21 ms 11348 KB Ok
42 Correct 17 ms 11348 KB Ok
43 Correct 15 ms 11440 KB Ok
44 Correct 25 ms 11736 KB Ok
45 Correct 24 ms 11704 KB Ok
46 Correct 23 ms 11732 KB Ok
47 Correct 24 ms 11732 KB Ok
48 Correct 23 ms 11732 KB Ok
49 Correct 23 ms 11732 KB Ok
50 Correct 25 ms 11716 KB Ok
51 Correct 23 ms 11732 KB Ok
52 Correct 27 ms 11724 KB Ok
53 Correct 28 ms 11732 KB Ok
54 Correct 243 ms 15904 KB Ok
55 Correct 327 ms 16452 KB Ok
56 Correct 288 ms 16284 KB Ok
57 Correct 202 ms 15372 KB Ok
58 Correct 286 ms 16280 KB Ok
59 Correct 253 ms 15924 KB Ok
60 Correct 197 ms 15480 KB Ok
61 Correct 200 ms 15624 KB Ok
62 Correct 377 ms 16720 KB Ok
63 Correct 222 ms 15668 KB Ok
64 Correct 345 ms 16360 KB Ok
65 Correct 280 ms 16284 KB Ok
66 Correct 226 ms 15812 KB Ok
67 Correct 190 ms 15440 KB Ok
68 Correct 285 ms 16068 KB Ok
69 Correct 1178 ms 25100 KB Ok
70 Correct 1302 ms 25376 KB Ok
71 Correct 1105 ms 24948 KB Ok
72 Correct 1016 ms 24936 KB Ok
73 Correct 1308 ms 25256 KB Ok
74 Correct 1149 ms 24960 KB Ok
75 Correct 1072 ms 24964 KB Ok
76 Correct 1221 ms 25120 KB Ok
77 Correct 1127 ms 24880 KB Ok
78 Correct 1224 ms 24820 KB Ok
79 Correct 1186 ms 25352 KB Ok
80 Correct 1082 ms 24832 KB Ok
81 Correct 1036 ms 25184 KB Ok
82 Correct 1118 ms 25044 KB Ok
83 Correct 1033 ms 25048 KB Ok

Subtask #7
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 11220 KB Ok
2 Correct 11 ms 11296 KB Ok
3 Correct 15 ms 11196 KB Ok
4 Correct 11 ms 11220 KB Ok
5 Correct 11 ms 11220 KB Ok
6 Correct 15 ms 11296 KB Ok
7 Correct 12 ms 11296 KB Ok
8 Correct 11 ms 11220 KB Ok
9 Correct 15 ms 11288 KB Ok
10 Correct 13 ms 11220 KB Ok
11 Correct 15 ms 11300 KB Ok
12 Correct 12 ms 11164 KB Ok
13 Correct 12 ms 11296 KB Ok
14 Correct 11 ms 11288 KB Ok
15 Correct 11 ms 11296 KB Ok
16 Correct 11 ms 11220 KB Ok
17 Correct 11 ms 11220 KB Ok
18 Correct 16 ms 11476 KB Ok
19 Correct 42 ms 12488 KB Ok
20 Correct 31 ms 11812 KB Ok
21 Correct 53 ms 12720 KB Ok
22 Correct 32 ms 12092 KB Ok
23 Correct 10 ms 11220 KB Ok
24 Correct 11 ms 11228 KB Ok
25 Correct 11 ms 11296 KB Ok
26 Correct 11 ms 11220 KB Ok
27 Correct 11 ms 11296 KB Ok
28 Correct 12 ms 11220 KB Ok
29 Correct 12 ms 11228 KB Ok
30 Correct 12 ms 11300 KB Ok
31 Correct 11 ms 11296 KB Ok
32 Correct 11 ms 11220 KB Ok
33 Correct 12 ms 11300 KB Ok
34 Correct 12 ms 11292 KB Ok
35 Correct 12 ms 11304 KB Ok
36 Correct 11 ms 11220 KB Ok
37 Correct 12 ms 11304 KB Ok
38 Correct 12 ms 11296 KB Ok
39 Correct 435 ms 26572 KB Ok
40 Correct 380 ms 28092 KB Ok
41 Correct 722 ms 30140 KB Ok
42 Correct 541 ms 29548 KB Ok
43 Correct 332 ms 21696 KB Ok
44 Correct 581 ms 30912 KB Ok
45 Correct 16 ms 11348 KB Ok
46 Correct 19 ms 11376 KB Ok
47 Correct 16 ms 11344 KB Ok
48 Correct 16 ms 11424 KB Ok
49 Correct 16 ms 11348 KB Ok
50 Correct 16 ms 11456 KB Ok
51 Correct 15 ms 11404 KB Ok
52 Correct 21 ms 11348 KB Ok
53 Correct 17 ms 11348 KB Ok
54 Correct 15 ms 11440 KB Ok
55 Correct 25 ms 11736 KB Ok
56 Correct 24 ms 11704 KB Ok
57 Correct 23 ms 11732 KB Ok
58 Correct 24 ms 11732 KB Ok
59 Correct 23 ms 11732 KB Ok
60 Correct 23 ms 11732 KB Ok
61 Correct 25 ms 11716 KB Ok
62 Correct 23 ms 11732 KB Ok
63 Correct 27 ms 11724 KB Ok
64 Correct 28 ms 11732 KB Ok
65 Correct 243 ms 15904 KB Ok
66 Correct 327 ms 16452 KB Ok
67 Correct 288 ms 16284 KB Ok
68 Correct 202 ms 15372 KB Ok
69 Correct 286 ms 16280 KB Ok
70 Correct 253 ms 15924 KB Ok
71 Correct 197 ms 15480 KB Ok
72 Correct 200 ms 15624 KB Ok
73 Correct 377 ms 16720 KB Ok
74 Correct 222 ms 15668 KB Ok
75 Correct 345 ms 16360 KB Ok
76 Correct 280 ms 16284 KB Ok
77 Correct 226 ms 15812 KB Ok
78 Correct 190 ms 15440 KB Ok
79 Correct 285 ms 16068 KB Ok
80 Correct 1178 ms 25100 KB Ok
81 Correct 1302 ms 25376 KB Ok
82 Correct 1105 ms 24948 KB Ok
83 Correct 1016 ms 24936 KB Ok
84 Correct 1308 ms 25256 KB Ok
85 Correct 1149 ms 24960 KB Ok
86 Correct 1072 ms 24964 KB Ok
87 Correct 1221 ms 25120 KB Ok
88 Correct 1127 ms 24880 KB Ok
89 Correct 1224 ms 24820 KB Ok
90 Correct 1186 ms 25352 KB Ok
91 Correct 1082 ms 24832 KB Ok
92 Correct 1036 ms 25184 KB Ok
93 Correct 1118 ms 25044 KB Ok
94 Correct 1033 ms 25048 KB Ok
95 Runtime error 113 ms 34072 KB Execution killed with signal 11
96 Halted 0 ms 0 KB -