oj.uz

Submission #957128

# Submission time Handle Problem Language Result Execution time Memory
957128 2024-04-03T04:34:04 Z pragmatist Nice sequence (IZhO18_sequence) C++17
76 / 100
 2000 ms 48208 KB 
#include <bits/stdc++.h>

using namespace std;

const int N = (int)4e5+20;
const int inf = (int)1e9+7;
const long long INF = (long long)1e18+7;
const int MOD = 42043;

int sum(int x, int y) {
	x += y;
	if(x >= MOD) {
		x -= MOD;
	}
	return x;
}

int mult(int x, int y) {
	return 1ll*x*y%MOD;
}

int n, m, b[N], dp[N];
bool ok;
vector<int> g[N], ord;
int used[N];

void dfs(int v) {
	if(!ok) {
		return;
	}
	used[v] = 1;
	for(auto to : g[v]) {
		if(used[to] == 1) {
			ok = 0;
			return;
		}
		if(!used[to]) {
			dfs(to);
		}
	}
	used[v] = 2;
	ord.push_back(v);
}

bool may(int len) {
	for(int i = 0; i <= len; ++i) {
		g[i].clear();
		used[i] = 0;
		dp[i] = 0;
	}	
	ord.clear();
	for(int i = n; i <= len; ++i) {
		g[i].push_back(i-n);
	}
	for(int i = m; i <= len; ++i) {
		g[i-m].push_back(i);
	}
	ok = 1;
	for(int i = 0; i <= len; ++i) {
		if(!used[i]) {
			dfs(i);
		}
	}
	if(!ok) {
		return 0;
	}
	reverse(ord.begin(), ord.end());
	int timer = 0;
	for(auto i : ord) {
		dp[i] = ++timer;
	}
	for(int i = 0; i <= len; ++i) {
		b[i] = dp[i];
	}
	return 1;
}

void test_case() {
	cin >> n >> m;        
	int l = 0, r = 4e5, len = -1;
	while(l <= r) {
		int mid = (l+r)/2;
		if(may(mid)) {
			len = mid;
			l = mid+1;
		} else {
			r = mid-1;
		}
	}	   
	assert(len != -1);
	cout << len << "\n";
	for(int i = 1; i <= len; ++i) {
		cout << b[i]-b[i-1] << ' ';
	}
	cout << "\n";
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int t;
    cin >> t;
    while(t--) {
    	test_case();
    }
	return 0;
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 19036 KB Ok
2 Correct 45 ms 19220 KB Ok
3 Correct 44 ms 19036 KB Ok
4 Correct 47 ms 19196 KB Ok
5 Correct 51 ms 19196 KB Ok
6 Correct 46 ms 19036 KB Ok
7 Correct 43 ms 19036 KB Ok
8 Correct 44 ms 19288 KB Ok
9 Correct 49 ms 19188 KB Ok
10 Correct 44 ms 19032 KB Ok
11 Correct 47 ms 19032 KB Ok
12 Correct 44 ms 19036 KB Ok

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 19216 KB Ok
2 Correct 55 ms 19200 KB Ok
3 Correct 44 ms 19036 KB Ok
4 Correct 44 ms 19192 KB Ok
5 Correct 44 ms 19036 KB Ok
6 Correct 47 ms 19308 KB Ok
7 Correct 60 ms 20124 KB Ok
8 Correct 51 ms 19540 KB Ok
9 Correct 66 ms 20304 KB Ok
10 Correct 65 ms 19700 KB Ok

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 19544 KB Ok
2 Correct 47 ms 19036 KB Ok
3 Correct 42 ms 19032 KB Ok
4 Correct 55 ms 19036 KB Ok
5 Correct 49 ms 18968 KB Ok
6 Correct 51 ms 19032 KB Ok
7 Correct 45 ms 19196 KB Ok
8 Correct 42 ms 19032 KB Ok
9 Correct 44 ms 19036 KB Ok
10 Correct 44 ms 19036 KB Ok
11 Correct 47 ms 19032 KB Ok

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 19032 KB Ok
2 Correct 43 ms 19036 KB Ok
3 Correct 42 ms 19036 KB Ok
4 Correct 47 ms 19036 KB Ok
5 Correct 50 ms 19036 KB Ok
6 Correct 265 ms 31104 KB Ok
7 Correct 295 ms 32132 KB Ok
8 Correct 478 ms 34176 KB Ok
9 Correct 388 ms 34260 KB Ok
10 Correct 200 ms 27080 KB Ok
11 Correct 364 ms 35068 KB Ok

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 19036 KB Ok
2 Correct 45 ms 19220 KB Ok
3 Correct 44 ms 19036 KB Ok
4 Correct 47 ms 19196 KB Ok
5 Correct 51 ms 19196 KB Ok
6 Correct 46 ms 19036 KB Ok
7 Correct 43 ms 19036 KB Ok
8 Correct 44 ms 19288 KB Ok
9 Correct 49 ms 19188 KB Ok
10 Correct 44 ms 19032 KB Ok
11 Correct 47 ms 19032 KB Ok
12 Correct 44 ms 19036 KB Ok
13 Correct 25 ms 19544 KB Ok
14 Correct 47 ms 19036 KB Ok
15 Correct 42 ms 19032 KB Ok
16 Correct 55 ms 19036 KB Ok
17 Correct 49 ms 18968 KB Ok
18 Correct 51 ms 19032 KB Ok
19 Correct 45 ms 19196 KB Ok
20 Correct 42 ms 19032 KB Ok
21 Correct 44 ms 19036 KB Ok
22 Correct 44 ms 19036 KB Ok
23 Correct 47 ms 19032 KB Ok
24 Correct 45 ms 19264 KB Ok
25 Correct 45 ms 19292 KB Ok
26 Correct 51 ms 19288 KB Ok
27 Correct 45 ms 19280 KB Ok
28 Correct 45 ms 19280 KB Ok
29 Correct 49 ms 19284 KB Ok
30 Correct 46 ms 19292 KB Ok
31 Correct 46 ms 19280 KB Ok
32 Correct 48 ms 19292 KB Ok
33 Correct 47 ms 19284 KB Ok
34 Correct 52 ms 19536 KB Ok
35 Correct 57 ms 19464 KB Ok
36 Correct 53 ms 19416 KB Ok
37 Correct 57 ms 19540 KB Ok
38 Correct 53 ms 19540 KB Ok
39 Correct 59 ms 19348 KB Ok
40 Correct 56 ms 19540 KB Ok
41 Correct 54 ms 19564 KB Ok
42 Correct 62 ms 19576 KB Ok
43 Correct 58 ms 19560 KB Ok

Subtask #6
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 19036 KB Ok
2 Correct 45 ms 19220 KB Ok
3 Correct 44 ms 19036 KB Ok
4 Correct 47 ms 19196 KB Ok
5 Correct 51 ms 19196 KB Ok
6 Correct 46 ms 19036 KB Ok
7 Correct 43 ms 19036 KB Ok
8 Correct 44 ms 19288 KB Ok
9 Correct 49 ms 19188 KB Ok
10 Correct 44 ms 19032 KB Ok
11 Correct 47 ms 19032 KB Ok
12 Correct 44 ms 19036 KB Ok
13 Correct 46 ms 19216 KB Ok
14 Correct 55 ms 19200 KB Ok
15 Correct 44 ms 19036 KB Ok
16 Correct 44 ms 19192 KB Ok
17 Correct 44 ms 19036 KB Ok
18 Correct 47 ms 19308 KB Ok
19 Correct 60 ms 20124 KB Ok
20 Correct 51 ms 19540 KB Ok
21 Correct 66 ms 20304 KB Ok
22 Correct 65 ms 19700 KB Ok
23 Correct 25 ms 19544 KB Ok
24 Correct 47 ms 19036 KB Ok
25 Correct 42 ms 19032 KB Ok
26 Correct 55 ms 19036 KB Ok
27 Correct 49 ms 18968 KB Ok
28 Correct 51 ms 19032 KB Ok
29 Correct 45 ms 19196 KB Ok
30 Correct 42 ms 19032 KB Ok
31 Correct 44 ms 19036 KB Ok
32 Correct 44 ms 19036 KB Ok
33 Correct 47 ms 19032 KB Ok
34 Correct 45 ms 19264 KB Ok
35 Correct 45 ms 19292 KB Ok
36 Correct 51 ms 19288 KB Ok
37 Correct 45 ms 19280 KB Ok
38 Correct 45 ms 19280 KB Ok
39 Correct 49 ms 19284 KB Ok
40 Correct 46 ms 19292 KB Ok
41 Correct 46 ms 19280 KB Ok
42 Correct 48 ms 19292 KB Ok
43 Correct 47 ms 19284 KB Ok
44 Correct 52 ms 19536 KB Ok
45 Correct 57 ms 19464 KB Ok
46 Correct 53 ms 19416 KB Ok
47 Correct 57 ms 19540 KB Ok
48 Correct 53 ms 19540 KB Ok
49 Correct 59 ms 19348 KB Ok
50 Correct 56 ms 19540 KB Ok
51 Correct 54 ms 19564 KB Ok
52 Correct 62 ms 19576 KB Ok
53 Correct 58 ms 19560 KB Ok
54 Correct 162 ms 21964 KB Ok
55 Correct 163 ms 22480 KB Ok
56 Correct 164 ms 22424 KB Ok
57 Correct 127 ms 21712 KB Ok
58 Correct 182 ms 22348 KB Ok
59 Correct 162 ms 22392 KB Ok
60 Correct 161 ms 21928 KB Ok
61 Correct 127 ms 21964 KB Ok
62 Correct 183 ms 22728 KB Ok
63 Correct 141 ms 21960 KB Ok
64 Correct 181 ms 22404 KB Ok
65 Correct 184 ms 22256 KB Ok
66 Correct 141 ms 21968 KB Ok
67 Correct 155 ms 21708 KB Ok
68 Correct 180 ms 22320 KB Ok
69 Correct 643 ms 30876 KB Ok
70 Correct 804 ms 31248 KB Ok
71 Correct 547 ms 30844 KB Ok
72 Correct 631 ms 30668 KB Ok
73 Correct 751 ms 31108 KB Ok
74 Correct 557 ms 30796 KB Ok
75 Correct 586 ms 30796 KB Ok
76 Correct 734 ms 30884 KB Ok
77 Correct 579 ms 30872 KB Ok
78 Correct 845 ms 30824 KB Ok
79 Correct 843 ms 31152 KB Ok
80 Correct 540 ms 30996 KB Ok
81 Correct 543 ms 31024 KB Ok
82 Correct 639 ms 30860 KB Ok
83 Correct 528 ms 30952 KB Ok

Subtask #7
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 19036 KB Ok
2 Correct 45 ms 19220 KB Ok
3 Correct 44 ms 19036 KB Ok
4 Correct 47 ms 19196 KB Ok
5 Correct 51 ms 19196 KB Ok
6 Correct 46 ms 19036 KB Ok
7 Correct 43 ms 19036 KB Ok
8 Correct 44 ms 19288 KB Ok
9 Correct 49 ms 19188 KB Ok
10 Correct 44 ms 19032 KB Ok
11 Correct 47 ms 19032 KB Ok
12 Correct 44 ms 19036 KB Ok
13 Correct 46 ms 19216 KB Ok
14 Correct 55 ms 19200 KB Ok
15 Correct 44 ms 19036 KB Ok
16 Correct 44 ms 19192 KB Ok
17 Correct 44 ms 19036 KB Ok
18 Correct 47 ms 19308 KB Ok
19 Correct 60 ms 20124 KB Ok
20 Correct 51 ms 19540 KB Ok
21 Correct 66 ms 20304 KB Ok
22 Correct 65 ms 19700 KB Ok
23 Correct 25 ms 19544 KB Ok
24 Correct 47 ms 19036 KB Ok
25 Correct 42 ms 19032 KB Ok
26 Correct 55 ms 19036 KB Ok
27 Correct 49 ms 18968 KB Ok
28 Correct 51 ms 19032 KB Ok
29 Correct 45 ms 19196 KB Ok
30 Correct 42 ms 19032 KB Ok
31 Correct 44 ms 19036 KB Ok
32 Correct 44 ms 19036 KB Ok
33 Correct 47 ms 19032 KB Ok
34 Correct 47 ms 19032 KB Ok
35 Correct 43 ms 19036 KB Ok
36 Correct 42 ms 19036 KB Ok
37 Correct 47 ms 19036 KB Ok
38 Correct 50 ms 19036 KB Ok
39 Correct 265 ms 31104 KB Ok
40 Correct 295 ms 32132 KB Ok
41 Correct 478 ms 34176 KB Ok
42 Correct 388 ms 34260 KB Ok
43 Correct 200 ms 27080 KB Ok
44 Correct 364 ms 35068 KB Ok
45 Correct 45 ms 19264 KB Ok
46 Correct 45 ms 19292 KB Ok
47 Correct 51 ms 19288 KB Ok
48 Correct 45 ms 19280 KB Ok
49 Correct 45 ms 19280 KB Ok
50 Correct 49 ms 19284 KB Ok
51 Correct 46 ms 19292 KB Ok
52 Correct 46 ms 19280 KB Ok
53 Correct 48 ms 19292 KB Ok
54 Correct 47 ms 19284 KB Ok
55 Correct 52 ms 19536 KB Ok
56 Correct 57 ms 19464 KB Ok
57 Correct 53 ms 19416 KB Ok
58 Correct 57 ms 19540 KB Ok
59 Correct 53 ms 19540 KB Ok
60 Correct 59 ms 19348 KB Ok
61 Correct 56 ms 19540 KB Ok
62 Correct 54 ms 19564 KB Ok
63 Correct 62 ms 19576 KB Ok
64 Correct 58 ms 19560 KB Ok
65 Correct 162 ms 21964 KB Ok
66 Correct 163 ms 22480 KB Ok
67 Correct 164 ms 22424 KB Ok
68 Correct 127 ms 21712 KB Ok
69 Correct 182 ms 22348 KB Ok
70 Correct 162 ms 22392 KB Ok
71 Correct 161 ms 21928 KB Ok
72 Correct 127 ms 21964 KB Ok
73 Correct 183 ms 22728 KB Ok
74 Correct 141 ms 21960 KB Ok
75 Correct 181 ms 22404 KB Ok
76 Correct 184 ms 22256 KB Ok
77 Correct 141 ms 21968 KB Ok
78 Correct 155 ms 21708 KB Ok
79 Correct 180 ms 22320 KB Ok
80 Correct 643 ms 30876 KB Ok
81 Correct 804 ms 31248 KB Ok
82 Correct 547 ms 30844 KB Ok
83 Correct 631 ms 30668 KB Ok
84 Correct 751 ms 31108 KB Ok
85 Correct 557 ms 30796 KB Ok
86 Correct 586 ms 30796 KB Ok
87 Correct 734 ms 30884 KB Ok
88 Correct 579 ms 30872 KB Ok
89 Correct 845 ms 30824 KB Ok
90 Correct 843 ms 31152 KB Ok
91 Correct 540 ms 30996 KB Ok
92 Correct 543 ms 31024 KB Ok
93 Correct 639 ms 30860 KB Ok
94 Correct 528 ms 30952 KB Ok
95 Correct 387 ms 29888 KB Ok
96 Correct 606 ms 35908 KB Ok
97 Correct 587 ms 32096 KB Ok
98 Correct 412 ms 32164 KB Ok
99 Correct 488 ms 31088 KB Ok
100 Correct 516 ms 32092 KB Ok
101 Correct 493 ms 33536 KB Ok
102 Correct 501 ms 31944 KB Ok
103 Correct 540 ms 33716 KB Ok
104 Correct 613 ms 34768 KB Ok
105 Correct 567 ms 35520 KB Ok
106 Correct 484 ms 34108 KB Ok
107 Correct 594 ms 34076 KB Ok
108 Correct 572 ms 35412 KB Ok
109 Correct 522 ms 35368 KB Ok
110 Execution timed out 2043 ms 48208 KB Time limit exceeded
111 Halted 0 ms 0 KB -