oj.uz

Submission #488601

# Submission time Handle Problem Language Result Execution time Memory
488601 2021-11-19T18:08:33 Z keta_tsimakuridze Nice sequence (IZhO18_sequence) C++14
76 / 100
 2000 ms 35936 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 = 4e5 + 5, mod = 1e9 + 7; // !
int t, in[N],n,m, p[N];
vector<int> V[N], v;
queue<int> q;
int check(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]++;
			V[i].push_back(i + n);
		}
		if(i + m <= x) {
			in[i]++;
			V[i + m].push_back(i);
		}
	}
	for(int i = 0; i <= x; i++) {
		if(!in[i]) q.push(i);
	}	
	v.clear();
	while(q.size()) {
		int u = q.front();
		q.pop();
		v.push_back(u);
		for(int i = 0; i < V[u].size(); i++) {
			in[V[u][i]]--;
			if(!in[V[u][i]]) q.push(V[u][i]);
		}
	}
	return v.size();
}
main() {
	ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	#define endl " "
	cin >> t;
	while(t--) {
		cin >> n >> m;
		int l = max(n, m), r = 400000, ans = max(n, m) - 1;
		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);
		reverse(v.begin(), v.end());
		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 'int check(int)':
sequence.cpp:31:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |   for(int i = 0; i < V[u].size(); i++) {
      |                  ~~^~~~~~~~~~~~~
sequence.cpp: At global scope:
sequence.cpp:38:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   38 | main() {
      | ^~~~
sequence.cpp: In function 'int main()':
sequence.cpp:55:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |   for(int i = 0; i < v.size(); i++) {
      |                  ~~^~~~~~~~~~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 16748 KB Ok
2 Correct 79 ms 16744 KB Ok
3 Correct 80 ms 16704 KB Ok
4 Correct 89 ms 16676 KB Ok
5 Correct 79 ms 16716 KB Ok
6 Correct 80 ms 16668 KB Ok
7 Correct 80 ms 16688 KB Ok
8 Correct 80 ms 16652 KB Ok
9 Correct 79 ms 16760 KB Ok
10 Correct 81 ms 16716 KB Ok
11 Correct 79 ms 16756 KB Ok
12 Correct 79 ms 16700 KB Ok

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 16752 KB Ok
2 Correct 80 ms 16744 KB Ok
3 Correct 80 ms 16740 KB Ok
4 Correct 80 ms 16724 KB Ok
5 Correct 80 ms 16744 KB Ok
6 Correct 84 ms 16820 KB Ok
7 Correct 108 ms 17492 KB Ok
8 Correct 92 ms 17028 KB Ok
9 Correct 111 ms 17456 KB Ok
10 Correct 99 ms 17144 KB Ok

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 16728 KB Ok
2 Correct 80 ms 16744 KB Ok
3 Correct 86 ms 16736 KB Ok
4 Correct 80 ms 16752 KB Ok
5 Correct 79 ms 16700 KB Ok
6 Correct 78 ms 16748 KB Ok
7 Correct 80 ms 16744 KB Ok
8 Correct 81 ms 16716 KB Ok
9 Correct 81 ms 16856 KB Ok
10 Correct 79 ms 16716 KB Ok
11 Correct 79 ms 16672 KB Ok

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 16752 KB Ok
2 Correct 80 ms 16716 KB Ok
3 Correct 81 ms 16732 KB Ok
4 Correct 85 ms 16752 KB Ok
5 Correct 79 ms 16696 KB Ok
6 Correct 394 ms 22604 KB Ok
7 Correct 358 ms 22332 KB Ok
8 Correct 656 ms 24440 KB Ok
9 Correct 478 ms 24452 KB Ok
10 Correct 303 ms 20432 KB Ok
11 Correct 481 ms 23944 KB Ok

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 16748 KB Ok
2 Correct 79 ms 16744 KB Ok
3 Correct 80 ms 16704 KB Ok
4 Correct 89 ms 16676 KB Ok
5 Correct 79 ms 16716 KB Ok
6 Correct 80 ms 16668 KB Ok
7 Correct 80 ms 16688 KB Ok
8 Correct 80 ms 16652 KB Ok
9 Correct 79 ms 16760 KB Ok
10 Correct 81 ms 16716 KB Ok
11 Correct 79 ms 16756 KB Ok
12 Correct 79 ms 16700 KB Ok
13 Correct 36 ms 16728 KB Ok
14 Correct 80 ms 16744 KB Ok
15 Correct 86 ms 16736 KB Ok
16 Correct 80 ms 16752 KB Ok
17 Correct 79 ms 16700 KB Ok
18 Correct 78 ms 16748 KB Ok
19 Correct 80 ms 16744 KB Ok
20 Correct 81 ms 16716 KB Ok
21 Correct 81 ms 16856 KB Ok
22 Correct 79 ms 16716 KB Ok
23 Correct 79 ms 16672 KB Ok
24 Correct 87 ms 16848 KB Ok
25 Correct 90 ms 17024 KB Ok
26 Correct 87 ms 16836 KB Ok
27 Correct 82 ms 16864 KB Ok
28 Correct 85 ms 16868 KB Ok
29 Correct 85 ms 16776 KB Ok
30 Correct 86 ms 16908 KB Ok
31 Correct 83 ms 16836 KB Ok
32 Correct 90 ms 16816 KB Ok
33 Correct 92 ms 16776 KB Ok
34 Correct 93 ms 16900 KB Ok
35 Correct 93 ms 16888 KB Ok
36 Correct 96 ms 16960 KB Ok
37 Correct 92 ms 16996 KB Ok
38 Correct 100 ms 16976 KB Ok
39 Correct 93 ms 16964 KB Ok
40 Correct 95 ms 16980 KB Ok
41 Correct 95 ms 16872 KB Ok
42 Correct 92 ms 16924 KB Ok
43 Correct 93 ms 16964 KB Ok

Subtask #6
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 16748 KB Ok
2 Correct 79 ms 16744 KB Ok
3 Correct 80 ms 16704 KB Ok
4 Correct 89 ms 16676 KB Ok
5 Correct 79 ms 16716 KB Ok
6 Correct 80 ms 16668 KB Ok
7 Correct 80 ms 16688 KB Ok
8 Correct 80 ms 16652 KB Ok
9 Correct 79 ms 16760 KB Ok
10 Correct 81 ms 16716 KB Ok
11 Correct 79 ms 16756 KB Ok
12 Correct 79 ms 16700 KB Ok
13 Correct 82 ms 16752 KB Ok
14 Correct 80 ms 16744 KB Ok
15 Correct 80 ms 16740 KB Ok
16 Correct 80 ms 16724 KB Ok
17 Correct 80 ms 16744 KB Ok
18 Correct 84 ms 16820 KB Ok
19 Correct 108 ms 17492 KB Ok
20 Correct 92 ms 17028 KB Ok
21 Correct 111 ms 17456 KB Ok
22 Correct 99 ms 17144 KB Ok
23 Correct 36 ms 16728 KB Ok
24 Correct 80 ms 16744 KB Ok
25 Correct 86 ms 16736 KB Ok
26 Correct 80 ms 16752 KB Ok
27 Correct 79 ms 16700 KB Ok
28 Correct 78 ms 16748 KB Ok
29 Correct 80 ms 16744 KB Ok
30 Correct 81 ms 16716 KB Ok
31 Correct 81 ms 16856 KB Ok
32 Correct 79 ms 16716 KB Ok
33 Correct 79 ms 16672 KB Ok
34 Correct 87 ms 16848 KB Ok
35 Correct 90 ms 17024 KB Ok
36 Correct 87 ms 16836 KB Ok
37 Correct 82 ms 16864 KB Ok
38 Correct 85 ms 16868 KB Ok
39 Correct 85 ms 16776 KB Ok
40 Correct 86 ms 16908 KB Ok
41 Correct 83 ms 16836 KB Ok
42 Correct 90 ms 16816 KB Ok
43 Correct 92 ms 16776 KB Ok
44 Correct 93 ms 16900 KB Ok
45 Correct 93 ms 16888 KB Ok
46 Correct 96 ms 16960 KB Ok
47 Correct 92 ms 16996 KB Ok
48 Correct 100 ms 16976 KB Ok
49 Correct 93 ms 16964 KB Ok
50 Correct 95 ms 16980 KB Ok
51 Correct 95 ms 16872 KB Ok
52 Correct 92 ms 16924 KB Ok
53 Correct 93 ms 16964 KB Ok
54 Correct 352 ms 20496 KB Ok
55 Correct 413 ms 20864 KB Ok
56 Correct 399 ms 20876 KB Ok
57 Correct 319 ms 20156 KB Ok
58 Correct 381 ms 20548 KB Ok
59 Correct 351 ms 20516 KB Ok
60 Correct 308 ms 20216 KB Ok
61 Correct 315 ms 20292 KB Ok
62 Correct 425 ms 20876 KB Ok
63 Correct 386 ms 20516 KB Ok
64 Correct 402 ms 20772 KB Ok
65 Correct 384 ms 20692 KB Ok
66 Correct 349 ms 20636 KB Ok
67 Correct 297 ms 20156 KB Ok
68 Correct 373 ms 20860 KB Ok
69 Correct 666 ms 23984 KB Ok
70 Correct 745 ms 25228 KB Ok
71 Correct 655 ms 23476 KB Ok
72 Correct 650 ms 24316 KB Ok
73 Correct 618 ms 23908 KB Ok
74 Correct 598 ms 23216 KB Ok
75 Correct 686 ms 23192 KB Ok
76 Correct 698 ms 24720 KB Ok
77 Correct 638 ms 22780 KB Ok
78 Correct 765 ms 24540 KB Ok
79 Correct 712 ms 24120 KB Ok
80 Correct 639 ms 24100 KB Ok
81 Correct 724 ms 24428 KB Ok
82 Correct 681 ms 23988 KB Ok
83 Correct 672 ms 23228 KB Ok

Subtask #7
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 16748 KB Ok
2 Correct 79 ms 16744 KB Ok
3 Correct 80 ms 16704 KB Ok
4 Correct 89 ms 16676 KB Ok
5 Correct 79 ms 16716 KB Ok
6 Correct 80 ms 16668 KB Ok
7 Correct 80 ms 16688 KB Ok
8 Correct 80 ms 16652 KB Ok
9 Correct 79 ms 16760 KB Ok
10 Correct 81 ms 16716 KB Ok
11 Correct 79 ms 16756 KB Ok
12 Correct 79 ms 16700 KB Ok
13 Correct 82 ms 16752 KB Ok
14 Correct 80 ms 16744 KB Ok
15 Correct 80 ms 16740 KB Ok
16 Correct 80 ms 16724 KB Ok
17 Correct 80 ms 16744 KB Ok
18 Correct 84 ms 16820 KB Ok
19 Correct 108 ms 17492 KB Ok
20 Correct 92 ms 17028 KB Ok
21 Correct 111 ms 17456 KB Ok
22 Correct 99 ms 17144 KB Ok
23 Correct 36 ms 16728 KB Ok
24 Correct 80 ms 16744 KB Ok
25 Correct 86 ms 16736 KB Ok
26 Correct 80 ms 16752 KB Ok
27 Correct 79 ms 16700 KB Ok
28 Correct 78 ms 16748 KB Ok
29 Correct 80 ms 16744 KB Ok
30 Correct 81 ms 16716 KB Ok
31 Correct 81 ms 16856 KB Ok
32 Correct 79 ms 16716 KB Ok
33 Correct 79 ms 16672 KB Ok
34 Correct 79 ms 16752 KB Ok
35 Correct 80 ms 16716 KB Ok
36 Correct 81 ms 16732 KB Ok
37 Correct 85 ms 16752 KB Ok
38 Correct 79 ms 16696 KB Ok
39 Correct 394 ms 22604 KB Ok
40 Correct 358 ms 22332 KB Ok
41 Correct 656 ms 24440 KB Ok
42 Correct 478 ms 24452 KB Ok
43 Correct 303 ms 20432 KB Ok
44 Correct 481 ms 23944 KB Ok
45 Correct 87 ms 16848 KB Ok
46 Correct 90 ms 17024 KB Ok
47 Correct 87 ms 16836 KB Ok
48 Correct 82 ms 16864 KB Ok
49 Correct 85 ms 16868 KB Ok
50 Correct 85 ms 16776 KB Ok
51 Correct 86 ms 16908 KB Ok
52 Correct 83 ms 16836 KB Ok
53 Correct 90 ms 16816 KB Ok
54 Correct 92 ms 16776 KB Ok
55 Correct 93 ms 16900 KB Ok
56 Correct 93 ms 16888 KB Ok
57 Correct 96 ms 16960 KB Ok
58 Correct 92 ms 16996 KB Ok
59 Correct 100 ms 16976 KB Ok
60 Correct 93 ms 16964 KB Ok
61 Correct 95 ms 16980 KB Ok
62 Correct 95 ms 16872 KB Ok
63 Correct 92 ms 16924 KB Ok
64 Correct 93 ms 16964 KB Ok
65 Correct 352 ms 20496 KB Ok
66 Correct 413 ms 20864 KB Ok
67 Correct 399 ms 20876 KB Ok
68 Correct 319 ms 20156 KB Ok
69 Correct 381 ms 20548 KB Ok
70 Correct 351 ms 20516 KB Ok
71 Correct 308 ms 20216 KB Ok
72 Correct 315 ms 20292 KB Ok
73 Correct 425 ms 20876 KB Ok
74 Correct 386 ms 20516 KB Ok
75 Correct 402 ms 20772 KB Ok
76 Correct 384 ms 20692 KB Ok
77 Correct 349 ms 20636 KB Ok
78 Correct 297 ms 20156 KB Ok
79 Correct 373 ms 20860 KB Ok
80 Correct 666 ms 23984 KB Ok
81 Correct 745 ms 25228 KB Ok
82 Correct 655 ms 23476 KB Ok
83 Correct 650 ms 24316 KB Ok
84 Correct 618 ms 23908 KB Ok
85 Correct 598 ms 23216 KB Ok
86 Correct 686 ms 23192 KB Ok
87 Correct 698 ms 24720 KB Ok
88 Correct 638 ms 22780 KB Ok
89 Correct 765 ms 24540 KB Ok
90 Correct 712 ms 24120 KB Ok
91 Correct 639 ms 24100 KB Ok
92 Correct 724 ms 24428 KB Ok
93 Correct 681 ms 23988 KB Ok
94 Correct 672 ms 23228 KB Ok
95 Correct 777 ms 27612 KB Ok
96 Correct 1209 ms 33884 KB Ok
97 Correct 1210 ms 30076 KB Ok
98 Correct 826 ms 30756 KB Ok
99 Correct 1085 ms 29312 KB Ok
100 Correct 1107 ms 29336 KB Ok
101 Correct 1097 ms 32028 KB Ok
102 Correct 1035 ms 29864 KB Ok
103 Correct 1036 ms 31536 KB Ok
104 Correct 1247 ms 33088 KB Ok
105 Correct 1182 ms 32756 KB Ok
106 Correct 925 ms 32692 KB Ok
107 Correct 1080 ms 31972 KB Ok
108 Correct 1251 ms 32532 KB Ok
109 Correct 1078 ms 33916 KB Ok
110 Execution timed out 2065 ms 35936 KB Time limit exceeded
111 Halted 0 ms 0 KB -