oj.uz

Submission #488589

# Submission time Handle Problem Language Result Execution time Memory
488589 2021-11-19T17:54:53 Z keta_tsimakuridze Nice sequence (IZhO18_sequence) C++14
76 / 100
 2000 ms 59700 KB 
#include<bits/stdc++.h>
#define f first
#define s second
#define pii pair<int,int>
#define int long long
using namespace std;
const int N = 1e6 + 5, mod = 1e9 + 7; // !
int t, in[N],n,m, p[N];
vector<int> V[N], v;
queue<int> q;
void construct(int x) {
	for(int i = 0; i <= x; i++) in[i] = 0, V[i].clear();
	for(int i = 0; i <= x; i++) {
		if(i + n <= x) {
			in[i + n]++; //cout << i <<"-->"<<i + n << endl;
			V[i].push_back(i + n);
		}
		if(i + m <= x) {
			in[i]++;
	//		cout << i + m <<"-->" << i << endl;
			V[i + m].push_back(i);
		}
	}
	for(int i = 0; i <= x; i++) {
		if(!in[i]) q.push(i);
	}	
}
int check(int x) {
	int c = 0;
	construct(x);
	v.clear();
	while(q.size()) {
		int u = q.front(); //cout <<"+" << u << endl;
		q.pop();
		v.push_back(u);
		c++;
		for(int i = 0; i < V[u].size(); i++) {
			in[V[u][i]]--;
			if(!in[V[u][i]]) q.push(V[u][i]);
		}
	}
	reverse(v.begin(),v.end());
	return c;
}
main() {
	cin >> t;
	while(t--) {
		cin >> n >> m;
		int l = 1, r = 1e6, ans = 0;
		while(l <= r) {
			int mid = (l + r)/2;
			if(check(mid) == mid + 1) {
				ans = mid, l = mid + 1;
			} else r = mid - 1;
		}
		cout << ans << endl;
		check(ans);
		for(int i = 0; i < v.size(); i++) {
			p[v[i]] = i + 1;
		}
		for(int i = 1; i <= ans; i++) {
			cout << p[i] - p[i - 1] <<" ";
	
		}
		cout << endl;
	}
}

Compilation message

sequence.cpp: In function 'long long int check(long long int)':
sequence.cpp:37:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |   for(int i = 0; i < V[u].size(); i++) {
      |                  ~~^~~~~~~~~~~~~
sequence.cpp: At global scope:
sequence.cpp:45:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   45 | main() {
      | ^~~~
sequence.cpp: In function 'int main()':
sequence.cpp:58:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |   for(int i = 0; i < v.size(); i++) {
      |                  ~~^~~~~~~~~~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 210 ms 43348 KB Ok
2 Correct 216 ms 43264 KB Ok
3 Correct 211 ms 43336 KB Ok
4 Correct 205 ms 43364 KB Ok
5 Correct 218 ms 43324 KB Ok
6 Correct 206 ms 43348 KB Ok
7 Correct 206 ms 43336 KB Ok
8 Correct 221 ms 43348 KB Ok
9 Correct 204 ms 43332 KB Ok
10 Correct 205 ms 43280 KB Ok
11 Correct 199 ms 43232 KB Ok
12 Correct 224 ms 43356 KB Ok

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 207 ms 43488 KB Ok
2 Correct 206 ms 43248 KB Ok
3 Correct 205 ms 43276 KB Ok
4 Correct 219 ms 43352 KB Ok
5 Correct 210 ms 43328 KB Ok
6 Correct 215 ms 43448 KB Ok
7 Correct 249 ms 43984 KB Ok
8 Correct 233 ms 43500 KB Ok
9 Correct 237 ms 44052 KB Ok
10 Correct 227 ms 43784 KB Ok

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 43328 KB Ok
2 Correct 210 ms 43352 KB Ok
3 Correct 214 ms 43352 KB Ok
4 Correct 209 ms 43236 KB Ok
5 Correct 224 ms 43344 KB Ok
6 Correct 210 ms 43356 KB Ok
7 Correct 208 ms 43260 KB Ok
8 Correct 236 ms 43336 KB Ok
9 Correct 208 ms 43228 KB Ok
10 Correct 220 ms 43336 KB Ok
11 Correct 204 ms 43348 KB Ok

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 215 ms 43296 KB Ok
2 Correct 205 ms 43340 KB Ok
3 Correct 207 ms 43324 KB Ok
4 Correct 209 ms 43348 KB Ok
5 Correct 215 ms 43360 KB Ok
6 Correct 569 ms 49372 KB Ok
7 Correct 479 ms 49080 KB Ok
8 Correct 788 ms 51428 KB Ok
9 Correct 631 ms 51248 KB Ok
10 Correct 437 ms 47280 KB Ok
11 Correct 607 ms 50700 KB Ok

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 210 ms 43348 KB Ok
2 Correct 216 ms 43264 KB Ok
3 Correct 211 ms 43336 KB Ok
4 Correct 205 ms 43364 KB Ok
5 Correct 218 ms 43324 KB Ok
6 Correct 206 ms 43348 KB Ok
7 Correct 206 ms 43336 KB Ok
8 Correct 221 ms 43348 KB Ok
9 Correct 204 ms 43332 KB Ok
10 Correct 205 ms 43280 KB Ok
11 Correct 199 ms 43232 KB Ok
12 Correct 224 ms 43356 KB Ok
13 Correct 89 ms 43328 KB Ok
14 Correct 210 ms 43352 KB Ok
15 Correct 214 ms 43352 KB Ok
16 Correct 209 ms 43236 KB Ok
17 Correct 224 ms 43344 KB Ok
18 Correct 210 ms 43356 KB Ok
19 Correct 208 ms 43260 KB Ok
20 Correct 236 ms 43336 KB Ok
21 Correct 208 ms 43228 KB Ok
22 Correct 220 ms 43336 KB Ok
23 Correct 204 ms 43348 KB Ok
24 Correct 219 ms 43448 KB Ok
25 Correct 241 ms 43420 KB Ok
26 Correct 217 ms 43476 KB Ok
27 Correct 212 ms 43476 KB Ok
28 Correct 238 ms 43460 KB Ok
29 Correct 214 ms 43424 KB Ok
30 Correct 208 ms 43344 KB Ok
31 Correct 227 ms 43584 KB Ok
32 Correct 223 ms 43464 KB Ok
33 Correct 215 ms 43404 KB Ok
34 Correct 221 ms 43520 KB Ok
35 Correct 237 ms 43564 KB Ok
36 Correct 213 ms 43564 KB Ok
37 Correct 223 ms 43600 KB Ok
38 Correct 236 ms 43536 KB Ok
39 Correct 230 ms 43496 KB Ok
40 Correct 235 ms 43584 KB Ok
41 Correct 225 ms 43640 KB Ok
42 Correct 236 ms 43552 KB Ok
43 Correct 233 ms 43584 KB Ok

Subtask #6
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 210 ms 43348 KB Ok
2 Correct 216 ms 43264 KB Ok
3 Correct 211 ms 43336 KB Ok
4 Correct 205 ms 43364 KB Ok
5 Correct 218 ms 43324 KB Ok
6 Correct 206 ms 43348 KB Ok
7 Correct 206 ms 43336 KB Ok
8 Correct 221 ms 43348 KB Ok
9 Correct 204 ms 43332 KB Ok
10 Correct 205 ms 43280 KB Ok
11 Correct 199 ms 43232 KB Ok
12 Correct 224 ms 43356 KB Ok
13 Correct 207 ms 43488 KB Ok
14 Correct 206 ms 43248 KB Ok
15 Correct 205 ms 43276 KB Ok
16 Correct 219 ms 43352 KB Ok
17 Correct 210 ms 43328 KB Ok
18 Correct 215 ms 43448 KB Ok
19 Correct 249 ms 43984 KB Ok
20 Correct 233 ms 43500 KB Ok
21 Correct 237 ms 44052 KB Ok
22 Correct 227 ms 43784 KB Ok
23 Correct 89 ms 43328 KB Ok
24 Correct 210 ms 43352 KB Ok
25 Correct 214 ms 43352 KB Ok
26 Correct 209 ms 43236 KB Ok
27 Correct 224 ms 43344 KB Ok
28 Correct 210 ms 43356 KB Ok
29 Correct 208 ms 43260 KB Ok
30 Correct 236 ms 43336 KB Ok
31 Correct 208 ms 43228 KB Ok
32 Correct 220 ms 43336 KB Ok
33 Correct 204 ms 43348 KB Ok
34 Correct 219 ms 43448 KB Ok
35 Correct 241 ms 43420 KB Ok
36 Correct 217 ms 43476 KB Ok
37 Correct 212 ms 43476 KB Ok
38 Correct 238 ms 43460 KB Ok
39 Correct 214 ms 43424 KB Ok
40 Correct 208 ms 43344 KB Ok
41 Correct 227 ms 43584 KB Ok
42 Correct 223 ms 43464 KB Ok
43 Correct 215 ms 43404 KB Ok
44 Correct 221 ms 43520 KB Ok
45 Correct 237 ms 43564 KB Ok
46 Correct 213 ms 43564 KB Ok
47 Correct 223 ms 43600 KB Ok
48 Correct 236 ms 43536 KB Ok
49 Correct 230 ms 43496 KB Ok
50 Correct 235 ms 43584 KB Ok
51 Correct 225 ms 43640 KB Ok
52 Correct 236 ms 43552 KB Ok
53 Correct 233 ms 43584 KB Ok
54 Correct 554 ms 47228 KB Ok
55 Correct 569 ms 47448 KB Ok
56 Correct 531 ms 47560 KB Ok
57 Correct 451 ms 46708 KB Ok
58 Correct 508 ms 47148 KB Ok
59 Correct 523 ms 47164 KB Ok
60 Correct 453 ms 46796 KB Ok
61 Correct 438 ms 46940 KB Ok
62 Correct 576 ms 47432 KB Ok
63 Correct 469 ms 46860 KB Ok
64 Correct 537 ms 47404 KB Ok
65 Correct 521 ms 47280 KB Ok
66 Correct 465 ms 47072 KB Ok
67 Correct 494 ms 46784 KB Ok
68 Correct 501 ms 47252 KB Ok
69 Correct 901 ms 50780 KB Ok
70 Correct 909 ms 51896 KB Ok
71 Correct 846 ms 50228 KB Ok
72 Correct 813 ms 51132 KB Ok
73 Correct 859 ms 50752 KB Ok
74 Correct 810 ms 49968 KB Ok
75 Correct 817 ms 49876 KB Ok
76 Correct 828 ms 51588 KB Ok
77 Correct 769 ms 49684 KB Ok
78 Correct 871 ms 51256 KB Ok
79 Correct 865 ms 51012 KB Ok
80 Correct 825 ms 50768 KB Ok
81 Correct 884 ms 51232 KB Ok
82 Correct 792 ms 50884 KB Ok
83 Correct 795 ms 50000 KB Ok

Subtask #7
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 210 ms 43348 KB Ok
2 Correct 216 ms 43264 KB Ok
3 Correct 211 ms 43336 KB Ok
4 Correct 205 ms 43364 KB Ok
5 Correct 218 ms 43324 KB Ok
6 Correct 206 ms 43348 KB Ok
7 Correct 206 ms 43336 KB Ok
8 Correct 221 ms 43348 KB Ok
9 Correct 204 ms 43332 KB Ok
10 Correct 205 ms 43280 KB Ok
11 Correct 199 ms 43232 KB Ok
12 Correct 224 ms 43356 KB Ok
13 Correct 207 ms 43488 KB Ok
14 Correct 206 ms 43248 KB Ok
15 Correct 205 ms 43276 KB Ok
16 Correct 219 ms 43352 KB Ok
17 Correct 210 ms 43328 KB Ok
18 Correct 215 ms 43448 KB Ok
19 Correct 249 ms 43984 KB Ok
20 Correct 233 ms 43500 KB Ok
21 Correct 237 ms 44052 KB Ok
22 Correct 227 ms 43784 KB Ok
23 Correct 89 ms 43328 KB Ok
24 Correct 210 ms 43352 KB Ok
25 Correct 214 ms 43352 KB Ok
26 Correct 209 ms 43236 KB Ok
27 Correct 224 ms 43344 KB Ok
28 Correct 210 ms 43356 KB Ok
29 Correct 208 ms 43260 KB Ok
30 Correct 236 ms 43336 KB Ok
31 Correct 208 ms 43228 KB Ok
32 Correct 220 ms 43336 KB Ok
33 Correct 204 ms 43348 KB Ok
34 Correct 215 ms 43296 KB Ok
35 Correct 205 ms 43340 KB Ok
36 Correct 207 ms 43324 KB Ok
37 Correct 209 ms 43348 KB Ok
38 Correct 215 ms 43360 KB Ok
39 Correct 569 ms 49372 KB Ok
40 Correct 479 ms 49080 KB Ok
41 Correct 788 ms 51428 KB Ok
42 Correct 631 ms 51248 KB Ok
43 Correct 437 ms 47280 KB Ok
44 Correct 607 ms 50700 KB Ok
45 Correct 219 ms 43448 KB Ok
46 Correct 241 ms 43420 KB Ok
47 Correct 217 ms 43476 KB Ok
48 Correct 212 ms 43476 KB Ok
49 Correct 238 ms 43460 KB Ok
50 Correct 214 ms 43424 KB Ok
51 Correct 208 ms 43344 KB Ok
52 Correct 227 ms 43584 KB Ok
53 Correct 223 ms 43464 KB Ok
54 Correct 215 ms 43404 KB Ok
55 Correct 221 ms 43520 KB Ok
56 Correct 237 ms 43564 KB Ok
57 Correct 213 ms 43564 KB Ok
58 Correct 223 ms 43600 KB Ok
59 Correct 236 ms 43536 KB Ok
60 Correct 230 ms 43496 KB Ok
61 Correct 235 ms 43584 KB Ok
62 Correct 225 ms 43640 KB Ok
63 Correct 236 ms 43552 KB Ok
64 Correct 233 ms 43584 KB Ok
65 Correct 554 ms 47228 KB Ok
66 Correct 569 ms 47448 KB Ok
67 Correct 531 ms 47560 KB Ok
68 Correct 451 ms 46708 KB Ok
69 Correct 508 ms 47148 KB Ok
70 Correct 523 ms 47164 KB Ok
71 Correct 453 ms 46796 KB Ok
72 Correct 438 ms 46940 KB Ok
73 Correct 576 ms 47432 KB Ok
74 Correct 469 ms 46860 KB Ok
75 Correct 537 ms 47404 KB Ok
76 Correct 521 ms 47280 KB Ok
77 Correct 465 ms 47072 KB Ok
78 Correct 494 ms 46784 KB Ok
79 Correct 501 ms 47252 KB Ok
80 Correct 901 ms 50780 KB Ok
81 Correct 909 ms 51896 KB Ok
82 Correct 846 ms 50228 KB Ok
83 Correct 813 ms 51132 KB Ok
84 Correct 859 ms 50752 KB Ok
85 Correct 810 ms 49968 KB Ok
86 Correct 817 ms 49876 KB Ok
87 Correct 828 ms 51588 KB Ok
88 Correct 769 ms 49684 KB Ok
89 Correct 871 ms 51256 KB Ok
90 Correct 865 ms 51012 KB Ok
91 Correct 825 ms 50768 KB Ok
92 Correct 884 ms 51232 KB Ok
93 Correct 792 ms 50884 KB Ok
94 Correct 795 ms 50000 KB Ok
95 Correct 934 ms 53372 KB Ok
96 Correct 1412 ms 57716 KB Ok
97 Correct 1396 ms 55960 KB Ok
98 Correct 988 ms 55220 KB Ok
99 Correct 1279 ms 55324 KB Ok
100 Correct 1297 ms 55124 KB Ok
101 Correct 1300 ms 56948 KB Ok
102 Correct 1212 ms 55924 KB Ok
103 Correct 1197 ms 55900 KB Ok
104 Correct 1457 ms 57800 KB Ok
105 Correct 1359 ms 57016 KB Ok
106 Correct 1089 ms 56728 KB Ok
107 Correct 1271 ms 57084 KB Ok
108 Correct 1458 ms 57296 KB Ok
109 Correct 1229 ms 57584 KB Ok
110 Execution timed out 2091 ms 59700 KB Time limit exceeded
111 Halted 0 ms 0 KB -