oj.uz

Submission #634056

# Submission time Handle Problem Language Result Execution time Memory
634056 2022-08-23T18:14:50 Z Tob Nice sequence (IZhO18_sequence) C++14
76 / 100
 2000 ms 47736 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 = 4e5 + 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 25 ms 22248 KB Ok
2 Correct 24 ms 22228 KB Ok
3 Correct 25 ms 22228 KB Ok
4 Correct 27 ms 22268 KB Ok
5 Correct 25 ms 22264 KB Ok
6 Correct 28 ms 22252 KB Ok
7 Correct 25 ms 22228 KB Ok
8 Correct 24 ms 22184 KB Ok
9 Correct 27 ms 22212 KB Ok
10 Correct 25 ms 22244 KB Ok
11 Correct 29 ms 22244 KB Ok
12 Correct 29 ms 22244 KB Ok

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 22264 KB Ok
2 Correct 24 ms 22260 KB Ok
3 Correct 25 ms 22152 KB Ok
4 Correct 31 ms 22236 KB Ok
5 Correct 25 ms 22228 KB Ok
6 Correct 40 ms 22476 KB Ok
7 Correct 57 ms 23372 KB Ok
8 Correct 43 ms 22860 KB Ok
9 Correct 66 ms 23608 KB Ok
10 Correct 47 ms 23044 KB Ok

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 22140 KB Ok
2 Correct 30 ms 22228 KB Ok
3 Correct 26 ms 22228 KB Ok
4 Correct 24 ms 22184 KB Ok
5 Correct 25 ms 22260 KB Ok
6 Correct 26 ms 22248 KB Ok
7 Correct 24 ms 22180 KB Ok
8 Correct 24 ms 22228 KB Ok
9 Correct 24 ms 22260 KB Ok
10 Correct 28 ms 22144 KB Ok
11 Correct 24 ms 22256 KB Ok

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 22228 KB Ok
2 Correct 24 ms 22160 KB Ok
3 Correct 25 ms 22260 KB Ok
4 Correct 26 ms 22228 KB Ok
5 Correct 25 ms 22208 KB Ok
6 Correct 463 ms 37532 KB Ok
7 Correct 375 ms 39172 KB Ok
8 Correct 753 ms 41128 KB Ok
9 Correct 535 ms 40636 KB Ok
10 Correct 338 ms 32680 KB Ok
11 Correct 579 ms 41808 KB Ok

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 22248 KB Ok
2 Correct 24 ms 22228 KB Ok
3 Correct 25 ms 22228 KB Ok
4 Correct 27 ms 22268 KB Ok
5 Correct 25 ms 22264 KB Ok
6 Correct 28 ms 22252 KB Ok
7 Correct 25 ms 22228 KB Ok
8 Correct 24 ms 22184 KB Ok
9 Correct 27 ms 22212 KB Ok
10 Correct 25 ms 22244 KB Ok
11 Correct 29 ms 22244 KB Ok
12 Correct 29 ms 22244 KB Ok
13 Correct 21 ms 22140 KB Ok
14 Correct 30 ms 22228 KB Ok
15 Correct 26 ms 22228 KB Ok
16 Correct 24 ms 22184 KB Ok
17 Correct 25 ms 22260 KB Ok
18 Correct 26 ms 22248 KB Ok
19 Correct 24 ms 22180 KB Ok
20 Correct 24 ms 22228 KB Ok
21 Correct 24 ms 22260 KB Ok
22 Correct 28 ms 22144 KB Ok
23 Correct 24 ms 22256 KB Ok
24 Correct 34 ms 22288 KB Ok
25 Correct 34 ms 22328 KB Ok
26 Correct 34 ms 22464 KB Ok
27 Correct 36 ms 22368 KB Ok
28 Correct 33 ms 22400 KB Ok
29 Correct 31 ms 22368 KB Ok
30 Correct 35 ms 22356 KB Ok
31 Correct 35 ms 22424 KB Ok
32 Correct 38 ms 22388 KB Ok
33 Correct 33 ms 22352 KB Ok
34 Correct 43 ms 22656 KB Ok
35 Correct 49 ms 22788 KB Ok
36 Correct 51 ms 22624 KB Ok
37 Correct 43 ms 22656 KB Ok
38 Correct 41 ms 22660 KB Ok
39 Correct 40 ms 22676 KB Ok
40 Correct 52 ms 22672 KB Ok
41 Correct 41 ms 22676 KB Ok
42 Correct 46 ms 22604 KB Ok
43 Correct 43 ms 22692 KB Ok

Subtask #6
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 22248 KB Ok
2 Correct 24 ms 22228 KB Ok
3 Correct 25 ms 22228 KB Ok
4 Correct 27 ms 22268 KB Ok
5 Correct 25 ms 22264 KB Ok
6 Correct 28 ms 22252 KB Ok
7 Correct 25 ms 22228 KB Ok
8 Correct 24 ms 22184 KB Ok
9 Correct 27 ms 22212 KB Ok
10 Correct 25 ms 22244 KB Ok
11 Correct 29 ms 22244 KB Ok
12 Correct 29 ms 22244 KB Ok
13 Correct 25 ms 22264 KB Ok
14 Correct 24 ms 22260 KB Ok
15 Correct 25 ms 22152 KB Ok
16 Correct 31 ms 22236 KB Ok
17 Correct 25 ms 22228 KB Ok
18 Correct 40 ms 22476 KB Ok
19 Correct 57 ms 23372 KB Ok
20 Correct 43 ms 22860 KB Ok
21 Correct 66 ms 23608 KB Ok
22 Correct 47 ms 23044 KB Ok
23 Correct 21 ms 22140 KB Ok
24 Correct 30 ms 22228 KB Ok
25 Correct 26 ms 22228 KB Ok
26 Correct 24 ms 22184 KB Ok
27 Correct 25 ms 22260 KB Ok
28 Correct 26 ms 22248 KB Ok
29 Correct 24 ms 22180 KB Ok
30 Correct 24 ms 22228 KB Ok
31 Correct 24 ms 22260 KB Ok
32 Correct 28 ms 22144 KB Ok
33 Correct 24 ms 22256 KB Ok
34 Correct 34 ms 22288 KB Ok
35 Correct 34 ms 22328 KB Ok
36 Correct 34 ms 22464 KB Ok
37 Correct 36 ms 22368 KB Ok
38 Correct 33 ms 22400 KB Ok
39 Correct 31 ms 22368 KB Ok
40 Correct 35 ms 22356 KB Ok
41 Correct 35 ms 22424 KB Ok
42 Correct 38 ms 22388 KB Ok
43 Correct 33 ms 22352 KB Ok
44 Correct 43 ms 22656 KB Ok
45 Correct 49 ms 22788 KB Ok
46 Correct 51 ms 22624 KB Ok
47 Correct 43 ms 22656 KB Ok
48 Correct 41 ms 22660 KB Ok
49 Correct 40 ms 22676 KB Ok
50 Correct 52 ms 22672 KB Ok
51 Correct 41 ms 22676 KB Ok
52 Correct 46 ms 22604 KB Ok
53 Correct 43 ms 22692 KB Ok
54 Correct 272 ms 27020 KB Ok
55 Correct 370 ms 27368 KB Ok
56 Correct 336 ms 27344 KB Ok
57 Correct 207 ms 26308 KB Ok
58 Correct 311 ms 27208 KB Ok
59 Correct 296 ms 26900 KB Ok
60 Correct 239 ms 26472 KB Ok
61 Correct 227 ms 26584 KB Ok
62 Correct 384 ms 27696 KB Ok
63 Correct 256 ms 26684 KB Ok
64 Correct 387 ms 27412 KB Ok
65 Correct 308 ms 27200 KB Ok
66 Correct 239 ms 26772 KB Ok
67 Correct 200 ms 26396 KB Ok
68 Correct 292 ms 27068 KB Ok
69 Correct 1227 ms 35912 KB Ok
70 Correct 1195 ms 36424 KB Ok
71 Correct 1067 ms 35968 KB Ok
72 Correct 1054 ms 35748 KB Ok
73 Correct 1168 ms 36184 KB Ok
74 Correct 1114 ms 35772 KB Ok
75 Correct 1059 ms 36008 KB Ok
76 Correct 1064 ms 35968 KB Ok
77 Correct 992 ms 35880 KB Ok
78 Correct 1104 ms 35912 KB Ok
79 Correct 1103 ms 36260 KB Ok
80 Correct 950 ms 36036 KB Ok
81 Correct 926 ms 36152 KB Ok
82 Correct 1031 ms 35908 KB Ok
83 Correct 1068 ms 36136 KB Ok

Subtask #7
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 22248 KB Ok
2 Correct 24 ms 22228 KB Ok
3 Correct 25 ms 22228 KB Ok
4 Correct 27 ms 22268 KB Ok
5 Correct 25 ms 22264 KB Ok
6 Correct 28 ms 22252 KB Ok
7 Correct 25 ms 22228 KB Ok
8 Correct 24 ms 22184 KB Ok
9 Correct 27 ms 22212 KB Ok
10 Correct 25 ms 22244 KB Ok
11 Correct 29 ms 22244 KB Ok
12 Correct 29 ms 22244 KB Ok
13 Correct 25 ms 22264 KB Ok
14 Correct 24 ms 22260 KB Ok
15 Correct 25 ms 22152 KB Ok
16 Correct 31 ms 22236 KB Ok
17 Correct 25 ms 22228 KB Ok
18 Correct 40 ms 22476 KB Ok
19 Correct 57 ms 23372 KB Ok
20 Correct 43 ms 22860 KB Ok
21 Correct 66 ms 23608 KB Ok
22 Correct 47 ms 23044 KB Ok
23 Correct 21 ms 22140 KB Ok
24 Correct 30 ms 22228 KB Ok
25 Correct 26 ms 22228 KB Ok
26 Correct 24 ms 22184 KB Ok
27 Correct 25 ms 22260 KB Ok
28 Correct 26 ms 22248 KB Ok
29 Correct 24 ms 22180 KB Ok
30 Correct 24 ms 22228 KB Ok
31 Correct 24 ms 22260 KB Ok
32 Correct 28 ms 22144 KB Ok
33 Correct 24 ms 22256 KB Ok
34 Correct 24 ms 22228 KB Ok
35 Correct 24 ms 22160 KB Ok
36 Correct 25 ms 22260 KB Ok
37 Correct 26 ms 22228 KB Ok
38 Correct 25 ms 22208 KB Ok
39 Correct 463 ms 37532 KB Ok
40 Correct 375 ms 39172 KB Ok
41 Correct 753 ms 41128 KB Ok
42 Correct 535 ms 40636 KB Ok
43 Correct 338 ms 32680 KB Ok
44 Correct 579 ms 41808 KB Ok
45 Correct 34 ms 22288 KB Ok
46 Correct 34 ms 22328 KB Ok
47 Correct 34 ms 22464 KB Ok
48 Correct 36 ms 22368 KB Ok
49 Correct 33 ms 22400 KB Ok
50 Correct 31 ms 22368 KB Ok
51 Correct 35 ms 22356 KB Ok
52 Correct 35 ms 22424 KB Ok
53 Correct 38 ms 22388 KB Ok
54 Correct 33 ms 22352 KB Ok
55 Correct 43 ms 22656 KB Ok
56 Correct 49 ms 22788 KB Ok
57 Correct 51 ms 22624 KB Ok
58 Correct 43 ms 22656 KB Ok
59 Correct 41 ms 22660 KB Ok
60 Correct 40 ms 22676 KB Ok
61 Correct 52 ms 22672 KB Ok
62 Correct 41 ms 22676 KB Ok
63 Correct 46 ms 22604 KB Ok
64 Correct 43 ms 22692 KB Ok
65 Correct 272 ms 27020 KB Ok
66 Correct 370 ms 27368 KB Ok
67 Correct 336 ms 27344 KB Ok
68 Correct 207 ms 26308 KB Ok
69 Correct 311 ms 27208 KB Ok
70 Correct 296 ms 26900 KB Ok
71 Correct 239 ms 26472 KB Ok
72 Correct 227 ms 26584 KB Ok
73 Correct 384 ms 27696 KB Ok
74 Correct 256 ms 26684 KB Ok
75 Correct 387 ms 27412 KB Ok
76 Correct 308 ms 27200 KB Ok
77 Correct 239 ms 26772 KB Ok
78 Correct 200 ms 26396 KB Ok
79 Correct 292 ms 27068 KB Ok
80 Correct 1227 ms 35912 KB Ok
81 Correct 1195 ms 36424 KB Ok
82 Correct 1067 ms 35968 KB Ok
83 Correct 1054 ms 35748 KB Ok
84 Correct 1168 ms 36184 KB Ok
85 Correct 1114 ms 35772 KB Ok
86 Correct 1059 ms 36008 KB Ok
87 Correct 1064 ms 35968 KB Ok
88 Correct 992 ms 35880 KB Ok
89 Correct 1104 ms 35912 KB Ok
90 Correct 1103 ms 36260 KB Ok
91 Correct 950 ms 36036 KB Ok
92 Correct 926 ms 36152 KB Ok
93 Correct 1031 ms 35908 KB Ok
94 Correct 1068 ms 36136 KB Ok
95 Correct 741 ms 35000 KB Ok
96 Correct 1208 ms 40512 KB Ok
97 Correct 1169 ms 38152 KB Ok
98 Correct 674 ms 36700 KB Ok
99 Correct 968 ms 36896 KB Ok
100 Correct 1050 ms 37844 KB Ok
101 Correct 972 ms 38296 KB Ok
102 Correct 872 ms 37300 KB Ok
103 Correct 970 ms 38452 KB Ok
104 Correct 1143 ms 39732 KB Ok
105 Correct 1219 ms 40340 KB Ok
106 Correct 790 ms 38568 KB Ok
107 Correct 1004 ms 38956 KB Ok
108 Correct 1364 ms 40720 KB Ok
109 Correct 1031 ms 39924 KB Ok
110 Execution timed out 2083 ms 47736 KB Time limit exceeded
111 Halted 0 ms 0 KB -