oj.uz

Submission #957127

# Submission time Handle Problem Language Result Execution time Memory
957127 2024-04-03T04:32:58 Z pragmatist Nice sequence (IZhO18_sequence) C++17
76 / 100
 776 ms 35528 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 = 3e5, 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 32 ms 17500 KB Ok
2 Correct 35 ms 17636 KB Ok
3 Correct 34 ms 17500 KB Ok
4 Correct 34 ms 17496 KB Ok
5 Correct 37 ms 17624 KB Ok
6 Correct 33 ms 17640 KB Ok
7 Correct 33 ms 17500 KB Ok
8 Correct 35 ms 17500 KB Ok
9 Correct 36 ms 17500 KB Ok
10 Correct 33 ms 17496 KB Ok
11 Correct 32 ms 17496 KB Ok
12 Correct 33 ms 17500 KB Ok

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 17496 KB Ok
2 Correct 32 ms 17500 KB Ok
3 Correct 33 ms 17496 KB Ok
4 Correct 42 ms 17500 KB Ok
5 Correct 33 ms 17500 KB Ok
6 Correct 36 ms 17756 KB Ok
7 Correct 49 ms 18512 KB Ok
8 Correct 39 ms 18004 KB Ok
9 Correct 53 ms 18524 KB Ok
10 Correct 42 ms 18008 KB Ok

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 17500 KB Ok
2 Correct 32 ms 17500 KB Ok
3 Correct 37 ms 17500 KB Ok
4 Correct 32 ms 17500 KB Ok
5 Correct 34 ms 17500 KB Ok
6 Correct 34 ms 17500 KB Ok
7 Correct 32 ms 17496 KB Ok
8 Correct 37 ms 17512 KB Ok
9 Correct 34 ms 17644 KB Ok
10 Correct 32 ms 17656 KB Ok
11 Correct 32 ms 17752 KB Ok

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 17500 KB Ok
2 Correct 32 ms 17500 KB Ok
3 Correct 34 ms 17500 KB Ok
4 Correct 35 ms 17648 KB Ok
5 Correct 32 ms 17496 KB Ok
6 Correct 250 ms 31928 KB Ok
7 Correct 225 ms 32712 KB Ok
8 Correct 462 ms 34996 KB Ok
9 Correct 321 ms 34992 KB Ok
10 Correct 233 ms 25612 KB Ok
11 Correct 335 ms 35528 KB Ok

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 17500 KB Ok
2 Correct 35 ms 17636 KB Ok
3 Correct 34 ms 17500 KB Ok
4 Correct 34 ms 17496 KB Ok
5 Correct 37 ms 17624 KB Ok
6 Correct 33 ms 17640 KB Ok
7 Correct 33 ms 17500 KB Ok
8 Correct 35 ms 17500 KB Ok
9 Correct 36 ms 17500 KB Ok
10 Correct 33 ms 17496 KB Ok
11 Correct 32 ms 17496 KB Ok
12 Correct 33 ms 17500 KB Ok
13 Correct 17 ms 17500 KB Ok
14 Correct 32 ms 17500 KB Ok
15 Correct 37 ms 17500 KB Ok
16 Correct 32 ms 17500 KB Ok
17 Correct 34 ms 17500 KB Ok
18 Correct 34 ms 17500 KB Ok
19 Correct 32 ms 17496 KB Ok
20 Correct 37 ms 17512 KB Ok
21 Correct 34 ms 17644 KB Ok
22 Correct 32 ms 17656 KB Ok
23 Correct 32 ms 17752 KB Ok
24 Correct 35 ms 17500 KB Ok
25 Correct 36 ms 17708 KB Ok
26 Correct 34 ms 17496 KB Ok
27 Correct 34 ms 17500 KB Ok
28 Correct 35 ms 17500 KB Ok
29 Correct 33 ms 17496 KB Ok
30 Correct 34 ms 17500 KB Ok
31 Correct 34 ms 17500 KB Ok
32 Correct 36 ms 17500 KB Ok
33 Correct 33 ms 17500 KB Ok
34 Correct 41 ms 17924 KB Ok
35 Correct 45 ms 17932 KB Ok
36 Correct 42 ms 17996 KB Ok
37 Correct 43 ms 17972 KB Ok
38 Correct 42 ms 18000 KB Ok
39 Correct 40 ms 17752 KB Ok
40 Correct 42 ms 18000 KB Ok
41 Correct 42 ms 18000 KB Ok
42 Correct 43 ms 18004 KB Ok
43 Correct 42 ms 17960 KB Ok

Subtask #6
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 17500 KB Ok
2 Correct 35 ms 17636 KB Ok
3 Correct 34 ms 17500 KB Ok
4 Correct 34 ms 17496 KB Ok
5 Correct 37 ms 17624 KB Ok
6 Correct 33 ms 17640 KB Ok
7 Correct 33 ms 17500 KB Ok
8 Correct 35 ms 17500 KB Ok
9 Correct 36 ms 17500 KB Ok
10 Correct 33 ms 17496 KB Ok
11 Correct 32 ms 17496 KB Ok
12 Correct 33 ms 17500 KB Ok
13 Correct 33 ms 17496 KB Ok
14 Correct 32 ms 17500 KB Ok
15 Correct 33 ms 17496 KB Ok
16 Correct 42 ms 17500 KB Ok
17 Correct 33 ms 17500 KB Ok
18 Correct 36 ms 17756 KB Ok
19 Correct 49 ms 18512 KB Ok
20 Correct 39 ms 18004 KB Ok
21 Correct 53 ms 18524 KB Ok
22 Correct 42 ms 18008 KB Ok
23 Correct 17 ms 17500 KB Ok
24 Correct 32 ms 17500 KB Ok
25 Correct 37 ms 17500 KB Ok
26 Correct 32 ms 17500 KB Ok
27 Correct 34 ms 17500 KB Ok
28 Correct 34 ms 17500 KB Ok
29 Correct 32 ms 17496 KB Ok
30 Correct 37 ms 17512 KB Ok
31 Correct 34 ms 17644 KB Ok
32 Correct 32 ms 17656 KB Ok
33 Correct 32 ms 17752 KB Ok
34 Correct 35 ms 17500 KB Ok
35 Correct 36 ms 17708 KB Ok
36 Correct 34 ms 17496 KB Ok
37 Correct 34 ms 17500 KB Ok
38 Correct 35 ms 17500 KB Ok
39 Correct 33 ms 17496 KB Ok
40 Correct 34 ms 17500 KB Ok
41 Correct 34 ms 17500 KB Ok
42 Correct 36 ms 17500 KB Ok
43 Correct 33 ms 17500 KB Ok
44 Correct 41 ms 17924 KB Ok
45 Correct 45 ms 17932 KB Ok
46 Correct 42 ms 17996 KB Ok
47 Correct 43 ms 17972 KB Ok
48 Correct 42 ms 18000 KB Ok
49 Correct 40 ms 17752 KB Ok
50 Correct 42 ms 18000 KB Ok
51 Correct 42 ms 18000 KB Ok
52 Correct 43 ms 18004 KB Ok
53 Correct 42 ms 17960 KB Ok
54 Correct 140 ms 20508 KB Ok
55 Correct 160 ms 20968 KB Ok
56 Correct 153 ms 20936 KB Ok
57 Correct 117 ms 20172 KB Ok
58 Correct 157 ms 20800 KB Ok
59 Correct 148 ms 20576 KB Ok
60 Correct 132 ms 20632 KB Ok
61 Correct 142 ms 20232 KB Ok
62 Correct 179 ms 21148 KB Ok
63 Correct 142 ms 20424 KB Ok
64 Correct 159 ms 20940 KB Ok
65 Correct 159 ms 20824 KB Ok
66 Correct 134 ms 20384 KB Ok
67 Correct 118 ms 20208 KB Ok
68 Correct 146 ms 20680 KB Ok
69 Correct 635 ms 29312 KB Ok
70 Correct 776 ms 29612 KB Ok
71 Correct 561 ms 29408 KB Ok
72 Correct 694 ms 29100 KB Ok
73 Correct 616 ms 29388 KB Ok
74 Correct 598 ms 29232 KB Ok
75 Correct 554 ms 29128 KB Ok
76 Correct 735 ms 29320 KB Ok
77 Correct 486 ms 29192 KB Ok
78 Correct 721 ms 29128 KB Ok
79 Correct 623 ms 29844 KB Ok
80 Correct 621 ms 29560 KB Ok
81 Correct 579 ms 29812 KB Ok
82 Correct 599 ms 29380 KB Ok
83 Correct 478 ms 29420 KB Ok

Subtask #7
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 17500 KB Ok
2 Correct 35 ms 17636 KB Ok
3 Correct 34 ms 17500 KB Ok
4 Correct 34 ms 17496 KB Ok
5 Correct 37 ms 17624 KB Ok
6 Correct 33 ms 17640 KB Ok
7 Correct 33 ms 17500 KB Ok
8 Correct 35 ms 17500 KB Ok
9 Correct 36 ms 17500 KB Ok
10 Correct 33 ms 17496 KB Ok
11 Correct 32 ms 17496 KB Ok
12 Correct 33 ms 17500 KB Ok
13 Correct 33 ms 17496 KB Ok
14 Correct 32 ms 17500 KB Ok
15 Correct 33 ms 17496 KB Ok
16 Correct 42 ms 17500 KB Ok
17 Correct 33 ms 17500 KB Ok
18 Correct 36 ms 17756 KB Ok
19 Correct 49 ms 18512 KB Ok
20 Correct 39 ms 18004 KB Ok
21 Correct 53 ms 18524 KB Ok
22 Correct 42 ms 18008 KB Ok
23 Correct 17 ms 17500 KB Ok
24 Correct 32 ms 17500 KB Ok
25 Correct 37 ms 17500 KB Ok
26 Correct 32 ms 17500 KB Ok
27 Correct 34 ms 17500 KB Ok
28 Correct 34 ms 17500 KB Ok
29 Correct 32 ms 17496 KB Ok
30 Correct 37 ms 17512 KB Ok
31 Correct 34 ms 17644 KB Ok
32 Correct 32 ms 17656 KB Ok
33 Correct 32 ms 17752 KB Ok
34 Correct 32 ms 17500 KB Ok
35 Correct 32 ms 17500 KB Ok
36 Correct 34 ms 17500 KB Ok
37 Correct 35 ms 17648 KB Ok
38 Correct 32 ms 17496 KB Ok
39 Correct 250 ms 31928 KB Ok
40 Correct 225 ms 32712 KB Ok
41 Correct 462 ms 34996 KB Ok
42 Correct 321 ms 34992 KB Ok
43 Correct 233 ms 25612 KB Ok
44 Correct 335 ms 35528 KB Ok
45 Correct 35 ms 17500 KB Ok
46 Correct 36 ms 17708 KB Ok
47 Correct 34 ms 17496 KB Ok
48 Correct 34 ms 17500 KB Ok
49 Correct 35 ms 17500 KB Ok
50 Correct 33 ms 17496 KB Ok
51 Correct 34 ms 17500 KB Ok
52 Correct 34 ms 17500 KB Ok
53 Correct 36 ms 17500 KB Ok
54 Correct 33 ms 17500 KB Ok
55 Correct 41 ms 17924 KB Ok
56 Correct 45 ms 17932 KB Ok
57 Correct 42 ms 17996 KB Ok
58 Correct 43 ms 17972 KB Ok
59 Correct 42 ms 18000 KB Ok
60 Correct 40 ms 17752 KB Ok
61 Correct 42 ms 18000 KB Ok
62 Correct 42 ms 18000 KB Ok
63 Correct 43 ms 18004 KB Ok
64 Correct 42 ms 17960 KB Ok
65 Correct 140 ms 20508 KB Ok
66 Correct 160 ms 20968 KB Ok
67 Correct 153 ms 20936 KB Ok
68 Correct 117 ms 20172 KB Ok
69 Correct 157 ms 20800 KB Ok
70 Correct 148 ms 20576 KB Ok
71 Correct 132 ms 20632 KB Ok
72 Correct 142 ms 20232 KB Ok
73 Correct 179 ms 21148 KB Ok
74 Correct 142 ms 20424 KB Ok
75 Correct 159 ms 20940 KB Ok
76 Correct 159 ms 20824 KB Ok
77 Correct 134 ms 20384 KB Ok
78 Correct 118 ms 20208 KB Ok
79 Correct 146 ms 20680 KB Ok
80 Correct 635 ms 29312 KB Ok
81 Correct 776 ms 29612 KB Ok
82 Correct 561 ms 29408 KB Ok
83 Correct 694 ms 29100 KB Ok
84 Correct 616 ms 29388 KB Ok
85 Correct 598 ms 29232 KB Ok
86 Correct 554 ms 29128 KB Ok
87 Correct 735 ms 29320 KB Ok
88 Correct 486 ms 29192 KB Ok
89 Correct 721 ms 29128 KB Ok
90 Correct 623 ms 29844 KB Ok
91 Correct 621 ms 29560 KB Ok
92 Correct 579 ms 29812 KB Ok
93 Correct 599 ms 29380 KB Ok
94 Correct 478 ms 29420 KB Ok
95 Correct 328 ms 28768 KB Ok
96 Incorrect 524 ms 32072 KB Jury has the better answer : jans = 311847, pans = 300000
97 Halted 0 ms 0 KB -