oj.uz

Submission #382797

# Submission time Handle Problem Language Result Execution time Memory
382797 2021-03-28T08:27:11 Z maximath_1 Nice sequence (IZhO18_sequence) C++11
100 / 100
 545 ms 34500 KB 
// binary search the length
// construct a graph of len + 1 vertices
// draw a directed edge from u to v if we require pref[u] - pref[v] < 0
// start indexing pref[x] from source to sink
// as you can see if we traverse the graph in that manner
// the pref[x]s will be numbered in a way s.t. all requirements are fulfilled
// get final array from pref
// complexity O(T * (N + M)log(N + M)), very tight to TL

// now we will prove that the final length is N + M - gcd(N, M) - 1
// first of all, we can show that if len = N + M - gcd(N, M),
// there is a cycle in the set of vertices divisible by gcd(N, M)
// if we remove vertex N + M - gcd(N, M), the cycle will break as (N + M - gcd(N, M)) is divisible by gcd(N, M)
// thus N + M - gcd(N, M) - 1 is max
// complexity O(T * (N + M))
#include <stdio.h>
#include <string>
#include <math.h>
#include <algorithm>
#include <vector>
#include <string.h>
#include <numeric>
#include <queue>
#include <assert.h>
#include <map>
#include <set>
#include <limits.h>
using namespace std;

#define ll long long
#define ld long double
const int MX = 200005;
const int LG = (int)log2(MX) + 2;
const ll mod = 1e9 + 7;
const ll inv2 = (mod + 1) / 2;

#define gc getchar//_unlocked //can't for window server
void cin(int &x){
	char c = gc(); bool neg = false;
	for(; c < '0'||'9' < c; c = gc())
		if(c == '-') neg=true;
	x = c - '0'; c = gc();
	for(; '0' <= c && c <= '9'; c = gc())
		x = (x << 1) + (x << 3) + (c - '0');
	if(neg) x = -x;
}

int tc, n, m;

pair<bool, vector<int> > check(int len){
	vector<int> deg(len + 1, 0);

	for(int i = 0; i <= len; i ++){
		if(i - n >= 0) deg[i - n] ++;
		if(i + m <= len) deg[i + m] ++;
	}

	vector<int> pref(len + 1, 0);
	queue<int> q;
	for(int i = 0; i <= len; i ++){
		if(deg[i] == 0)
			q.push(i);
	}

	int cnt = 0;
	for(; q.size();){
		int nw = q.front(); q.pop();
		pref[nw] = ++ cnt;

		if(nw - n >= 0){
			deg[nw - n] --;
			if(deg[nw - n] == 0)
				q.push(nw - n);
		}

		if(nw + m <= len){
			deg[nw + m] --;
			if(deg[nw + m] == 0)
				q.push(nw + m);
		}
	}

	bool valid = 1;
	for(int i = 0; i <= len; i ++)
		if(deg[i] > 0) valid = 0;

	vector<int> res(len, 0);
	for(int i = 0; i < len; i ++)
		res[i] = pref[i + 1] - pref[i];

	return make_pair(valid, res);
}

int main(){
	cin(tc);

	for(; tc --;){
		cin(n); cin(m);

		int rs = n + m - __gcd(n, m) - 1;
		vector<int> ans = check(rs).second;

		printf("%d\n", rs);
		for(int i = 0; i < rs; i ++)
			printf("%d ", ans[i]);
		printf("\n");
	}
	
	return 0;
}

Subtask #1
6.0 / 6.0

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

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Ok
2 Correct 1 ms 364 KB Ok
3 Correct 1 ms 364 KB Ok
4 Correct 1 ms 364 KB Ok
5 Correct 1 ms 384 KB Ok
6 Correct 3 ms 364 KB Ok
7 Correct 11 ms 876 KB Ok
8 Correct 6 ms 492 KB Ok
9 Correct 14 ms 876 KB Ok
10 Correct 8 ms 620 KB Ok

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Ok
2 Correct 1 ms 364 KB Ok
3 Correct 1 ms 384 KB Ok
4 Correct 1 ms 364 KB Ok
5 Correct 1 ms 364 KB Ok
6 Correct 1 ms 364 KB Ok
7 Correct 1 ms 364 KB Ok
8 Correct 1 ms 364 KB Ok
9 Correct 1 ms 364 KB Ok
10 Correct 2 ms 364 KB Ok
11 Correct 1 ms 512 KB Ok

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Ok
2 Correct 1 ms 364 KB Ok
3 Correct 1 ms 364 KB Ok
4 Correct 1 ms 364 KB Ok
5 Correct 1 ms 364 KB Ok
6 Correct 99 ms 4740 KB Ok
7 Correct 88 ms 4272 KB Ok
8 Correct 158 ms 7128 KB Ok
9 Correct 126 ms 7204 KB Ok
10 Correct 68 ms 3204 KB Ok
11 Correct 118 ms 7272 KB Ok

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Ok
2 Correct 1 ms 364 KB Ok
3 Correct 1 ms 364 KB Ok
4 Correct 1 ms 364 KB Ok
5 Correct 1 ms 364 KB Ok
6 Correct 1 ms 364 KB Ok
7 Correct 1 ms 364 KB Ok
8 Correct 1 ms 364 KB Ok
9 Correct 1 ms 364 KB Ok
10 Correct 1 ms 364 KB Ok
11 Correct 1 ms 364 KB Ok
12 Correct 1 ms 364 KB Ok
13 Correct 1 ms 364 KB Ok
14 Correct 1 ms 364 KB Ok
15 Correct 1 ms 384 KB Ok
16 Correct 1 ms 364 KB Ok
17 Correct 1 ms 364 KB Ok
18 Correct 1 ms 364 KB Ok
19 Correct 1 ms 364 KB Ok
20 Correct 1 ms 364 KB Ok
21 Correct 1 ms 364 KB Ok
22 Correct 2 ms 364 KB Ok
23 Correct 1 ms 512 KB Ok
24 Correct 3 ms 364 KB Ok
25 Correct 3 ms 440 KB Ok
26 Correct 3 ms 364 KB Ok
27 Correct 4 ms 364 KB Ok
28 Correct 3 ms 364 KB Ok
29 Correct 3 ms 364 KB Ok
30 Correct 2 ms 364 KB Ok
31 Correct 3 ms 364 KB Ok
32 Correct 3 ms 364 KB Ok
33 Correct 3 ms 364 KB Ok
34 Correct 5 ms 492 KB Ok
35 Correct 5 ms 492 KB Ok
36 Correct 5 ms 492 KB Ok
37 Correct 5 ms 492 KB Ok
38 Correct 5 ms 512 KB Ok
39 Correct 5 ms 492 KB Ok
40 Correct 5 ms 492 KB Ok
41 Correct 5 ms 492 KB Ok
42 Correct 5 ms 492 KB Ok
43 Correct 5 ms 492 KB Ok

Subtask #6
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Ok
2 Correct 1 ms 364 KB Ok
3 Correct 1 ms 364 KB Ok
4 Correct 1 ms 364 KB Ok
5 Correct 1 ms 364 KB Ok
6 Correct 1 ms 364 KB Ok
7 Correct 1 ms 364 KB Ok
8 Correct 1 ms 364 KB Ok
9 Correct 1 ms 364 KB Ok
10 Correct 1 ms 364 KB Ok
11 Correct 1 ms 364 KB Ok
12 Correct 1 ms 364 KB Ok
13 Correct 1 ms 364 KB Ok
14 Correct 1 ms 364 KB Ok
15 Correct 1 ms 364 KB Ok
16 Correct 1 ms 364 KB Ok
17 Correct 1 ms 384 KB Ok
18 Correct 3 ms 364 KB Ok
19 Correct 11 ms 876 KB Ok
20 Correct 6 ms 492 KB Ok
21 Correct 14 ms 876 KB Ok
22 Correct 8 ms 620 KB Ok
23 Correct 1 ms 364 KB Ok
24 Correct 1 ms 364 KB Ok
25 Correct 1 ms 384 KB Ok
26 Correct 1 ms 364 KB Ok
27 Correct 1 ms 364 KB Ok
28 Correct 1 ms 364 KB Ok
29 Correct 1 ms 364 KB Ok
30 Correct 1 ms 364 KB Ok
31 Correct 1 ms 364 KB Ok
32 Correct 2 ms 364 KB Ok
33 Correct 1 ms 512 KB Ok
34 Correct 3 ms 364 KB Ok
35 Correct 3 ms 440 KB Ok
36 Correct 3 ms 364 KB Ok
37 Correct 4 ms 364 KB Ok
38 Correct 3 ms 364 KB Ok
39 Correct 3 ms 364 KB Ok
40 Correct 2 ms 364 KB Ok
41 Correct 3 ms 364 KB Ok
42 Correct 3 ms 364 KB Ok
43 Correct 3 ms 364 KB Ok
44 Correct 5 ms 492 KB Ok
45 Correct 5 ms 492 KB Ok
46 Correct 5 ms 492 KB Ok
47 Correct 5 ms 492 KB Ok
48 Correct 5 ms 512 KB Ok
49 Correct 5 ms 492 KB Ok
50 Correct 5 ms 492 KB Ok
51 Correct 5 ms 492 KB Ok
52 Correct 5 ms 492 KB Ok
53 Correct 5 ms 492 KB Ok
54 Correct 75 ms 3200 KB Ok
55 Correct 88 ms 3240 KB Ok
56 Correct 85 ms 3028 KB Ok
57 Correct 75 ms 2764 KB Ok
58 Correct 93 ms 2852 KB Ok
59 Correct 76 ms 2900 KB Ok
60 Correct 71 ms 2868 KB Ok
61 Correct 68 ms 2884 KB Ok
62 Correct 86 ms 3040 KB Ok
63 Correct 72 ms 3236 KB Ok
64 Correct 88 ms 3352 KB Ok
65 Correct 88 ms 3368 KB Ok
66 Correct 76 ms 3328 KB Ok
67 Correct 75 ms 2980 KB Ok
68 Correct 75 ms 3012 KB Ok
69 Correct 130 ms 7252 KB Ok
70 Correct 130 ms 8468 KB Ok
71 Correct 125 ms 6400 KB Ok
72 Correct 164 ms 7564 KB Ok
73 Correct 126 ms 6964 KB Ok
74 Correct 127 ms 5944 KB Ok
75 Correct 125 ms 6044 KB Ok
76 Correct 128 ms 8092 KB Ok
77 Correct 121 ms 5536 KB Ok
78 Correct 126 ms 7824 KB Ok
79 Correct 157 ms 7424 KB Ok
80 Correct 131 ms 6916 KB Ok
81 Correct 136 ms 7680 KB Ok
82 Correct 125 ms 7064 KB Ok
83 Correct 126 ms 6056 KB Ok

Subtask #7
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Ok
2 Correct 1 ms 364 KB Ok
3 Correct 1 ms 364 KB Ok
4 Correct 1 ms 364 KB Ok
5 Correct 1 ms 364 KB Ok
6 Correct 1 ms 364 KB Ok
7 Correct 1 ms 364 KB Ok
8 Correct 1 ms 364 KB Ok
9 Correct 1 ms 364 KB Ok
10 Correct 1 ms 364 KB Ok
11 Correct 1 ms 364 KB Ok
12 Correct 1 ms 364 KB Ok
13 Correct 1 ms 364 KB Ok
14 Correct 1 ms 364 KB Ok
15 Correct 1 ms 364 KB Ok
16 Correct 1 ms 364 KB Ok
17 Correct 1 ms 384 KB Ok
18 Correct 3 ms 364 KB Ok
19 Correct 11 ms 876 KB Ok
20 Correct 6 ms 492 KB Ok
21 Correct 14 ms 876 KB Ok
22 Correct 8 ms 620 KB Ok
23 Correct 1 ms 364 KB Ok
24 Correct 1 ms 364 KB Ok
25 Correct 1 ms 384 KB Ok
26 Correct 1 ms 364 KB Ok
27 Correct 1 ms 364 KB Ok
28 Correct 1 ms 364 KB Ok
29 Correct 1 ms 364 KB Ok
30 Correct 1 ms 364 KB Ok
31 Correct 1 ms 364 KB Ok
32 Correct 2 ms 364 KB Ok
33 Correct 1 ms 512 KB Ok
34 Correct 1 ms 364 KB Ok
35 Correct 1 ms 364 KB Ok
36 Correct 1 ms 364 KB Ok
37 Correct 1 ms 364 KB Ok
38 Correct 1 ms 364 KB Ok
39 Correct 99 ms 4740 KB Ok
40 Correct 88 ms 4272 KB Ok
41 Correct 158 ms 7128 KB Ok
42 Correct 126 ms 7204 KB Ok
43 Correct 68 ms 3204 KB Ok
44 Correct 118 ms 7272 KB Ok
45 Correct 3 ms 364 KB Ok
46 Correct 3 ms 440 KB Ok
47 Correct 3 ms 364 KB Ok
48 Correct 4 ms 364 KB Ok
49 Correct 3 ms 364 KB Ok
50 Correct 3 ms 364 KB Ok
51 Correct 2 ms 364 KB Ok
52 Correct 3 ms 364 KB Ok
53 Correct 3 ms 364 KB Ok
54 Correct 3 ms 364 KB Ok
55 Correct 5 ms 492 KB Ok
56 Correct 5 ms 492 KB Ok
57 Correct 5 ms 492 KB Ok
58 Correct 5 ms 492 KB Ok
59 Correct 5 ms 512 KB Ok
60 Correct 5 ms 492 KB Ok
61 Correct 5 ms 492 KB Ok
62 Correct 5 ms 492 KB Ok
63 Correct 5 ms 492 KB Ok
64 Correct 5 ms 492 KB Ok
65 Correct 75 ms 3200 KB Ok
66 Correct 88 ms 3240 KB Ok
67 Correct 85 ms 3028 KB Ok
68 Correct 75 ms 2764 KB Ok
69 Correct 93 ms 2852 KB Ok
70 Correct 76 ms 2900 KB Ok
71 Correct 71 ms 2868 KB Ok
72 Correct 68 ms 2884 KB Ok
73 Correct 86 ms 3040 KB Ok
74 Correct 72 ms 3236 KB Ok
75 Correct 88 ms 3352 KB Ok
76 Correct 88 ms 3368 KB Ok
77 Correct 76 ms 3328 KB Ok
78 Correct 75 ms 2980 KB Ok
79 Correct 75 ms 3012 KB Ok
80 Correct 130 ms 7252 KB Ok
81 Correct 130 ms 8468 KB Ok
82 Correct 125 ms 6400 KB Ok
83 Correct 164 ms 7564 KB Ok
84 Correct 126 ms 6964 KB Ok
85 Correct 127 ms 5944 KB Ok
86 Correct 125 ms 6044 KB Ok
87 Correct 128 ms 8092 KB Ok
88 Correct 121 ms 5536 KB Ok
89 Correct 126 ms 7824 KB Ok
90 Correct 157 ms 7424 KB Ok
91 Correct 131 ms 6916 KB Ok
92 Correct 136 ms 7680 KB Ok
93 Correct 125 ms 7064 KB Ok
94 Correct 126 ms 6056 KB Ok
95 Correct 187 ms 7288 KB Ok
96 Correct 272 ms 10832 KB Ok
97 Correct 274 ms 9572 KB Ok
98 Correct 201 ms 7372 KB Ok
99 Correct 246 ms 8584 KB Ok
100 Correct 253 ms 8600 KB Ok
101 Correct 245 ms 10236 KB Ok
102 Correct 237 ms 9952 KB Ok
103 Correct 233 ms 8520 KB Ok
104 Correct 282 ms 9264 KB Ok
105 Correct 272 ms 11348 KB Ok
106 Correct 226 ms 8756 KB Ok
107 Correct 259 ms 9612 KB Ok
108 Correct 275 ms 10572 KB Ok
109 Correct 248 ms 9032 KB Ok
110 Correct 506 ms 24788 KB Ok
111 Correct 545 ms 34500 KB Ok
112 Correct 517 ms 26548 KB Ok
113 Correct 517 ms 30692 KB Ok
114 Correct 531 ms 32064 KB Ok
115 Correct 524 ms 31328 KB Ok
116 Correct 536 ms 31184 KB Ok
117 Correct 523 ms 31872 KB Ok
118 Correct 515 ms 27532 KB Ok
119 Correct 523 ms 30940 KB Ok
120 Correct 530 ms 27844 KB Ok
121 Correct 503 ms 26668 KB Ok
122 Correct 520 ms 29716 KB Ok
123 Correct 536 ms 34308 KB Ok
124 Correct 506 ms 23560 KB Ok
125 Correct 449 ms 16836 KB Ok