oj.uz

Submission #957129

# Submission time Handle Problem Language Result Execution time Memory
957129 2024-04-03T04:34:24 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) {
	used[v] = 1;
	if(!ok) {
		return;
	}
	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 44 ms 19036 KB Ok
2 Correct 47 ms 19036 KB Ok
3 Correct 47 ms 19036 KB Ok
4 Correct 57 ms 19204 KB Ok
5 Correct 48 ms 19196 KB Ok
6 Correct 51 ms 19032 KB Ok
7 Correct 60 ms 19200 KB Ok
8 Correct 56 ms 19036 KB Ok
9 Correct 48 ms 19032 KB Ok
10 Correct 61 ms 19204 KB Ok
11 Correct 51 ms 19032 KB Ok
12 Correct 48 ms 19032 KB Ok

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 19036 KB Ok
2 Correct 59 ms 19088 KB Ok
3 Correct 53 ms 19288 KB Ok
4 Correct 46 ms 19212 KB Ok
5 Correct 45 ms 19032 KB Ok
6 Correct 65 ms 19292 KB Ok
7 Correct 60 ms 20104 KB Ok
8 Correct 65 ms 19472 KB Ok
9 Correct 65 ms 20096 KB Ok
10 Correct 54 ms 19596 KB Ok

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 19416 KB Ok
2 Correct 48 ms 19036 KB Ok
3 Correct 51 ms 19192 KB Ok
4 Correct 52 ms 19036 KB Ok
5 Correct 50 ms 19192 KB Ok
6 Correct 48 ms 19032 KB Ok
7 Correct 47 ms 19196 KB Ok
8 Correct 58 ms 19032 KB Ok
9 Correct 45 ms 19032 KB Ok
10 Correct 45 ms 19036 KB Ok
11 Correct 64 ms 19288 KB Ok

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 19188 KB Ok
2 Correct 53 ms 19036 KB Ok
3 Correct 44 ms 19036 KB Ok
4 Correct 45 ms 19036 KB Ok
5 Correct 52 ms 19188 KB Ok
6 Correct 287 ms 31180 KB Ok
7 Correct 247 ms 32128 KB Ok
8 Correct 461 ms 34144 KB Ok
9 Correct 338 ms 34244 KB Ok
10 Correct 211 ms 27084 KB Ok
11 Correct 426 ms 34736 KB Ok

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 19036 KB Ok
2 Correct 47 ms 19036 KB Ok
3 Correct 47 ms 19036 KB Ok
4 Correct 57 ms 19204 KB Ok
5 Correct 48 ms 19196 KB Ok
6 Correct 51 ms 19032 KB Ok
7 Correct 60 ms 19200 KB Ok
8 Correct 56 ms 19036 KB Ok
9 Correct 48 ms 19032 KB Ok
10 Correct 61 ms 19204 KB Ok
11 Correct 51 ms 19032 KB Ok
12 Correct 48 ms 19032 KB Ok
13 Correct 30 ms 19416 KB Ok
14 Correct 48 ms 19036 KB Ok
15 Correct 51 ms 19192 KB Ok
16 Correct 52 ms 19036 KB Ok
17 Correct 50 ms 19192 KB Ok
18 Correct 48 ms 19032 KB Ok
19 Correct 47 ms 19196 KB Ok
20 Correct 58 ms 19032 KB Ok
21 Correct 45 ms 19032 KB Ok
22 Correct 45 ms 19036 KB Ok
23 Correct 64 ms 19288 KB Ok
24 Correct 53 ms 19296 KB Ok
25 Correct 47 ms 19284 KB Ok
26 Correct 46 ms 19280 KB Ok
27 Correct 51 ms 19088 KB Ok
28 Correct 50 ms 19280 KB Ok
29 Correct 49 ms 19232 KB Ok
30 Correct 50 ms 19268 KB Ok
31 Correct 51 ms 19284 KB Ok
32 Correct 46 ms 19280 KB Ok
33 Correct 50 ms 19284 KB Ok
34 Correct 68 ms 19544 KB Ok
35 Correct 59 ms 19536 KB Ok
36 Correct 55 ms 19468 KB Ok
37 Correct 61 ms 19540 KB Ok
38 Correct 62 ms 19552 KB Ok
39 Correct 78 ms 19536 KB Ok
40 Correct 70 ms 19540 KB Ok
41 Correct 67 ms 19544 KB Ok
42 Correct 54 ms 19464 KB Ok
43 Correct 55 ms 19540 KB Ok

Subtask #6
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 19036 KB Ok
2 Correct 47 ms 19036 KB Ok
3 Correct 47 ms 19036 KB Ok
4 Correct 57 ms 19204 KB Ok
5 Correct 48 ms 19196 KB Ok
6 Correct 51 ms 19032 KB Ok
7 Correct 60 ms 19200 KB Ok
8 Correct 56 ms 19036 KB Ok
9 Correct 48 ms 19032 KB Ok
10 Correct 61 ms 19204 KB Ok
11 Correct 51 ms 19032 KB Ok
12 Correct 48 ms 19032 KB Ok
13 Correct 44 ms 19036 KB Ok
14 Correct 59 ms 19088 KB Ok
15 Correct 53 ms 19288 KB Ok
16 Correct 46 ms 19212 KB Ok
17 Correct 45 ms 19032 KB Ok
18 Correct 65 ms 19292 KB Ok
19 Correct 60 ms 20104 KB Ok
20 Correct 65 ms 19472 KB Ok
21 Correct 65 ms 20096 KB Ok
22 Correct 54 ms 19596 KB Ok
23 Correct 30 ms 19416 KB Ok
24 Correct 48 ms 19036 KB Ok
25 Correct 51 ms 19192 KB Ok
26 Correct 52 ms 19036 KB Ok
27 Correct 50 ms 19192 KB Ok
28 Correct 48 ms 19032 KB Ok
29 Correct 47 ms 19196 KB Ok
30 Correct 58 ms 19032 KB Ok
31 Correct 45 ms 19032 KB Ok
32 Correct 45 ms 19036 KB Ok
33 Correct 64 ms 19288 KB Ok
34 Correct 53 ms 19296 KB Ok
35 Correct 47 ms 19284 KB Ok
36 Correct 46 ms 19280 KB Ok
37 Correct 51 ms 19088 KB Ok
38 Correct 50 ms 19280 KB Ok
39 Correct 49 ms 19232 KB Ok
40 Correct 50 ms 19268 KB Ok
41 Correct 51 ms 19284 KB Ok
42 Correct 46 ms 19280 KB Ok
43 Correct 50 ms 19284 KB Ok
44 Correct 68 ms 19544 KB Ok
45 Correct 59 ms 19536 KB Ok
46 Correct 55 ms 19468 KB Ok
47 Correct 61 ms 19540 KB Ok
48 Correct 62 ms 19552 KB Ok
49 Correct 78 ms 19536 KB Ok
50 Correct 70 ms 19540 KB Ok
51 Correct 67 ms 19544 KB Ok
52 Correct 54 ms 19464 KB Ok
53 Correct 55 ms 19540 KB Ok
54 Correct 150 ms 22092 KB Ok
55 Correct 189 ms 22452 KB Ok
56 Correct 172 ms 22476 KB Ok
57 Correct 124 ms 21544 KB Ok
58 Correct 156 ms 22468 KB Ok
59 Correct 155 ms 22220 KB Ok
60 Correct 143 ms 21876 KB Ok
61 Correct 130 ms 21940 KB Ok
62 Correct 179 ms 22732 KB Ok
63 Correct 161 ms 22036 KB Ok
64 Correct 172 ms 22432 KB Ok
65 Correct 165 ms 22308 KB Ok
66 Correct 137 ms 21960 KB Ok
67 Correct 145 ms 21680 KB Ok
68 Correct 162 ms 22276 KB Ok
69 Correct 702 ms 30896 KB Ok
70 Correct 895 ms 31328 KB Ok
71 Correct 515 ms 30916 KB Ok
72 Correct 798 ms 30680 KB Ok
73 Correct 685 ms 31168 KB Ok
74 Correct 501 ms 30720 KB Ok
75 Correct 531 ms 30652 KB Ok
76 Correct 865 ms 31060 KB Ok
77 Correct 540 ms 30804 KB Ok
78 Correct 670 ms 30576 KB Ok
79 Correct 652 ms 31172 KB Ok
80 Correct 596 ms 30664 KB Ok
81 Correct 525 ms 31176 KB Ok
82 Correct 596 ms 31004 KB Ok
83 Correct 517 ms 31048 KB Ok

Subtask #7
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 19036 KB Ok
2 Correct 47 ms 19036 KB Ok
3 Correct 47 ms 19036 KB Ok
4 Correct 57 ms 19204 KB Ok
5 Correct 48 ms 19196 KB Ok
6 Correct 51 ms 19032 KB Ok
7 Correct 60 ms 19200 KB Ok
8 Correct 56 ms 19036 KB Ok
9 Correct 48 ms 19032 KB Ok
10 Correct 61 ms 19204 KB Ok
11 Correct 51 ms 19032 KB Ok
12 Correct 48 ms 19032 KB Ok
13 Correct 44 ms 19036 KB Ok
14 Correct 59 ms 19088 KB Ok
15 Correct 53 ms 19288 KB Ok
16 Correct 46 ms 19212 KB Ok
17 Correct 45 ms 19032 KB Ok
18 Correct 65 ms 19292 KB Ok
19 Correct 60 ms 20104 KB Ok
20 Correct 65 ms 19472 KB Ok
21 Correct 65 ms 20096 KB Ok
22 Correct 54 ms 19596 KB Ok
23 Correct 30 ms 19416 KB Ok
24 Correct 48 ms 19036 KB Ok
25 Correct 51 ms 19192 KB Ok
26 Correct 52 ms 19036 KB Ok
27 Correct 50 ms 19192 KB Ok
28 Correct 48 ms 19032 KB Ok
29 Correct 47 ms 19196 KB Ok
30 Correct 58 ms 19032 KB Ok
31 Correct 45 ms 19032 KB Ok
32 Correct 45 ms 19036 KB Ok
33 Correct 64 ms 19288 KB Ok
34 Correct 60 ms 19188 KB Ok
35 Correct 53 ms 19036 KB Ok
36 Correct 44 ms 19036 KB Ok
37 Correct 45 ms 19036 KB Ok
38 Correct 52 ms 19188 KB Ok
39 Correct 287 ms 31180 KB Ok
40 Correct 247 ms 32128 KB Ok
41 Correct 461 ms 34144 KB Ok
42 Correct 338 ms 34244 KB Ok
43 Correct 211 ms 27084 KB Ok
44 Correct 426 ms 34736 KB Ok
45 Correct 53 ms 19296 KB Ok
46 Correct 47 ms 19284 KB Ok
47 Correct 46 ms 19280 KB Ok
48 Correct 51 ms 19088 KB Ok
49 Correct 50 ms 19280 KB Ok
50 Correct 49 ms 19232 KB Ok
51 Correct 50 ms 19268 KB Ok
52 Correct 51 ms 19284 KB Ok
53 Correct 46 ms 19280 KB Ok
54 Correct 50 ms 19284 KB Ok
55 Correct 68 ms 19544 KB Ok
56 Correct 59 ms 19536 KB Ok
57 Correct 55 ms 19468 KB Ok
58 Correct 61 ms 19540 KB Ok
59 Correct 62 ms 19552 KB Ok
60 Correct 78 ms 19536 KB Ok
61 Correct 70 ms 19540 KB Ok
62 Correct 67 ms 19544 KB Ok
63 Correct 54 ms 19464 KB Ok
64 Correct 55 ms 19540 KB Ok
65 Correct 150 ms 22092 KB Ok
66 Correct 189 ms 22452 KB Ok
67 Correct 172 ms 22476 KB Ok
68 Correct 124 ms 21544 KB Ok
69 Correct 156 ms 22468 KB Ok
70 Correct 155 ms 22220 KB Ok
71 Correct 143 ms 21876 KB Ok
72 Correct 130 ms 21940 KB Ok
73 Correct 179 ms 22732 KB Ok
74 Correct 161 ms 22036 KB Ok
75 Correct 172 ms 22432 KB Ok
76 Correct 165 ms 22308 KB Ok
77 Correct 137 ms 21960 KB Ok
78 Correct 145 ms 21680 KB Ok
79 Correct 162 ms 22276 KB Ok
80 Correct 702 ms 30896 KB Ok
81 Correct 895 ms 31328 KB Ok
82 Correct 515 ms 30916 KB Ok
83 Correct 798 ms 30680 KB Ok
84 Correct 685 ms 31168 KB Ok
85 Correct 501 ms 30720 KB Ok
86 Correct 531 ms 30652 KB Ok
87 Correct 865 ms 31060 KB Ok
88 Correct 540 ms 30804 KB Ok
89 Correct 670 ms 30576 KB Ok
90 Correct 652 ms 31172 KB Ok
91 Correct 596 ms 30664 KB Ok
92 Correct 525 ms 31176 KB Ok
93 Correct 596 ms 31004 KB Ok
94 Correct 517 ms 31048 KB Ok
95 Correct 356 ms 29888 KB Ok
96 Correct 598 ms 36032 KB Ok
97 Correct 542 ms 32640 KB Ok
98 Correct 370 ms 32220 KB Ok
99 Correct 443 ms 31168 KB Ok
100 Correct 531 ms 31972 KB Ok
101 Correct 539 ms 33388 KB Ok
102 Correct 479 ms 31732 KB Ok
103 Correct 533 ms 33740 KB Ok
104 Correct 590 ms 34912 KB Ok
105 Correct 609 ms 35500 KB Ok
106 Correct 475 ms 34188 KB Ok
107 Correct 594 ms 34244 KB Ok
108 Correct 605 ms 35452 KB Ok
109 Correct 563 ms 35516 KB Ok
110 Execution timed out 2059 ms 48208 KB Time limit exceeded
111 Halted 0 ms 0 KB -