oj.uz

Submission #957138

# Submission time Handle Problem Language Result Execution time Memory
957138 2024-04-03T04:48:06 Z pragmatist Nice sequence (IZhO18_sequence) C++17
76 / 100
 2000 ms 51196 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, dp[N];
bool ok;
vector<int> g[N], ord, ans;
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;
	}
	ans = ord;
	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);
	reverse(ans.begin(), ans.end());
	int timer = 0;
	for(auto i : ans) {
		dp[i] = ++timer;
	}
	cout << len << "\n";
	for(int i = 1; i <= len; ++i) {
		cout << dp[i]-dp[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 46 ms 19036 KB Ok
2 Correct 43 ms 19036 KB Ok
3 Correct 44 ms 18984 KB Ok
4 Correct 47 ms 19032 KB Ok
5 Correct 48 ms 19192 KB Ok
6 Correct 47 ms 19032 KB Ok
7 Correct 44 ms 19036 KB Ok
8 Correct 46 ms 19036 KB Ok
9 Correct 45 ms 19036 KB Ok
10 Correct 44 ms 19036 KB Ok
11 Correct 44 ms 19032 KB Ok
12 Correct 44 ms 19032 KB Ok

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 19188 KB Ok
2 Correct 47 ms 19036 KB Ok
3 Correct 45 ms 19036 KB Ok
4 Correct 45 ms 19036 KB Ok
5 Correct 46 ms 19188 KB Ok
6 Correct 49 ms 19292 KB Ok
7 Correct 59 ms 19880 KB Ok
8 Correct 51 ms 19544 KB Ok
9 Correct 68 ms 20308 KB Ok
10 Correct 54 ms 19572 KB Ok

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 19032 KB Ok
2 Correct 45 ms 19288 KB Ok
3 Correct 45 ms 19036 KB Ok
4 Correct 44 ms 19036 KB Ok
5 Correct 45 ms 19032 KB Ok
6 Correct 45 ms 19188 KB Ok
7 Correct 45 ms 19184 KB Ok
8 Correct 51 ms 19032 KB Ok
9 Correct 48 ms 19036 KB Ok
10 Correct 44 ms 19136 KB Ok
11 Correct 44 ms 19036 KB Ok

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 19032 KB Ok
2 Correct 48 ms 19032 KB Ok
3 Correct 44 ms 19036 KB Ok
4 Correct 44 ms 19032 KB Ok
5 Correct 44 ms 19036 KB Ok
6 Correct 288 ms 32280 KB Ok
7 Correct 240 ms 32152 KB Ok
8 Correct 433 ms 35724 KB Ok
9 Correct 379 ms 34928 KB Ok
10 Correct 235 ms 27672 KB Ok
11 Correct 347 ms 35664 KB Ok

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 19036 KB Ok
2 Correct 43 ms 19036 KB Ok
3 Correct 44 ms 18984 KB Ok
4 Correct 47 ms 19032 KB Ok
5 Correct 48 ms 19192 KB Ok
6 Correct 47 ms 19032 KB Ok
7 Correct 44 ms 19036 KB Ok
8 Correct 46 ms 19036 KB Ok
9 Correct 45 ms 19036 KB Ok
10 Correct 44 ms 19036 KB Ok
11 Correct 44 ms 19032 KB Ok
12 Correct 44 ms 19032 KB Ok
13 Correct 22 ms 19032 KB Ok
14 Correct 45 ms 19288 KB Ok
15 Correct 45 ms 19036 KB Ok
16 Correct 44 ms 19036 KB Ok
17 Correct 45 ms 19032 KB Ok
18 Correct 45 ms 19188 KB Ok
19 Correct 45 ms 19184 KB Ok
20 Correct 51 ms 19032 KB Ok
21 Correct 48 ms 19036 KB Ok
22 Correct 44 ms 19136 KB Ok
23 Correct 44 ms 19036 KB Ok
24 Correct 46 ms 19292 KB Ok
25 Correct 46 ms 19284 KB Ok
26 Correct 48 ms 19304 KB Ok
27 Correct 46 ms 19288 KB Ok
28 Correct 50 ms 19548 KB Ok
29 Correct 46 ms 19208 KB Ok
30 Correct 45 ms 19280 KB Ok
31 Correct 46 ms 19280 KB Ok
32 Correct 47 ms 19288 KB Ok
33 Correct 50 ms 19236 KB Ok
34 Correct 53 ms 19540 KB Ok
35 Correct 55 ms 19536 KB Ok
36 Correct 52 ms 19540 KB Ok
37 Correct 57 ms 19536 KB Ok
38 Correct 55 ms 19544 KB Ok
39 Correct 51 ms 19536 KB Ok
40 Correct 57 ms 19536 KB Ok
41 Correct 55 ms 19536 KB Ok
42 Correct 53 ms 19536 KB Ok
43 Correct 54 ms 19540 KB Ok

Subtask #6
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 19036 KB Ok
2 Correct 43 ms 19036 KB Ok
3 Correct 44 ms 18984 KB Ok
4 Correct 47 ms 19032 KB Ok
5 Correct 48 ms 19192 KB Ok
6 Correct 47 ms 19032 KB Ok
7 Correct 44 ms 19036 KB Ok
8 Correct 46 ms 19036 KB Ok
9 Correct 45 ms 19036 KB Ok
10 Correct 44 ms 19036 KB Ok
11 Correct 44 ms 19032 KB Ok
12 Correct 44 ms 19032 KB Ok
13 Correct 53 ms 19188 KB Ok
14 Correct 47 ms 19036 KB Ok
15 Correct 45 ms 19036 KB Ok
16 Correct 45 ms 19036 KB Ok
17 Correct 46 ms 19188 KB Ok
18 Correct 49 ms 19292 KB Ok
19 Correct 59 ms 19880 KB Ok
20 Correct 51 ms 19544 KB Ok
21 Correct 68 ms 20308 KB Ok
22 Correct 54 ms 19572 KB Ok
23 Correct 22 ms 19032 KB Ok
24 Correct 45 ms 19288 KB Ok
25 Correct 45 ms 19036 KB Ok
26 Correct 44 ms 19036 KB Ok
27 Correct 45 ms 19032 KB Ok
28 Correct 45 ms 19188 KB Ok
29 Correct 45 ms 19184 KB Ok
30 Correct 51 ms 19032 KB Ok
31 Correct 48 ms 19036 KB Ok
32 Correct 44 ms 19136 KB Ok
33 Correct 44 ms 19036 KB Ok
34 Correct 46 ms 19292 KB Ok
35 Correct 46 ms 19284 KB Ok
36 Correct 48 ms 19304 KB Ok
37 Correct 46 ms 19288 KB Ok
38 Correct 50 ms 19548 KB Ok
39 Correct 46 ms 19208 KB Ok
40 Correct 45 ms 19280 KB Ok
41 Correct 46 ms 19280 KB Ok
42 Correct 47 ms 19288 KB Ok
43 Correct 50 ms 19236 KB Ok
44 Correct 53 ms 19540 KB Ok
45 Correct 55 ms 19536 KB Ok
46 Correct 52 ms 19540 KB Ok
47 Correct 57 ms 19536 KB Ok
48 Correct 55 ms 19544 KB Ok
49 Correct 51 ms 19536 KB Ok
50 Correct 57 ms 19536 KB Ok
51 Correct 55 ms 19536 KB Ok
52 Correct 53 ms 19536 KB Ok
53 Correct 54 ms 19540 KB Ok
54 Correct 141 ms 22604 KB Ok
55 Correct 160 ms 23240 KB Ok
56 Correct 155 ms 22560 KB Ok
57 Correct 118 ms 21736 KB Ok
58 Correct 151 ms 22968 KB Ok
59 Correct 144 ms 22324 KB Ok
60 Correct 129 ms 21976 KB Ok
61 Correct 141 ms 22512 KB Ok
62 Correct 175 ms 22700 KB Ok
63 Correct 143 ms 22340 KB Ok
64 Correct 166 ms 22480 KB Ok
65 Correct 155 ms 22844 KB Ok
66 Correct 130 ms 22540 KB Ok
67 Correct 124 ms 21824 KB Ok
68 Correct 153 ms 22380 KB Ok
69 Correct 582 ms 30912 KB Ok
70 Correct 624 ms 31556 KB Ok
71 Correct 552 ms 31060 KB Ok
72 Correct 559 ms 31388 KB Ok
73 Correct 572 ms 31044 KB Ok
74 Correct 527 ms 31112 KB Ok
75 Correct 469 ms 30968 KB Ok
76 Correct 644 ms 31160 KB Ok
77 Correct 477 ms 31520 KB Ok
78 Correct 635 ms 30792 KB Ok
79 Correct 555 ms 31904 KB Ok
80 Correct 521 ms 30772 KB Ok
81 Correct 490 ms 31300 KB Ok
82 Correct 575 ms 31468 KB Ok
83 Correct 539 ms 31084 KB Ok

Subtask #7
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 19036 KB Ok
2 Correct 43 ms 19036 KB Ok
3 Correct 44 ms 18984 KB Ok
4 Correct 47 ms 19032 KB Ok
5 Correct 48 ms 19192 KB Ok
6 Correct 47 ms 19032 KB Ok
7 Correct 44 ms 19036 KB Ok
8 Correct 46 ms 19036 KB Ok
9 Correct 45 ms 19036 KB Ok
10 Correct 44 ms 19036 KB Ok
11 Correct 44 ms 19032 KB Ok
12 Correct 44 ms 19032 KB Ok
13 Correct 53 ms 19188 KB Ok
14 Correct 47 ms 19036 KB Ok
15 Correct 45 ms 19036 KB Ok
16 Correct 45 ms 19036 KB Ok
17 Correct 46 ms 19188 KB Ok
18 Correct 49 ms 19292 KB Ok
19 Correct 59 ms 19880 KB Ok
20 Correct 51 ms 19544 KB Ok
21 Correct 68 ms 20308 KB Ok
22 Correct 54 ms 19572 KB Ok
23 Correct 22 ms 19032 KB Ok
24 Correct 45 ms 19288 KB Ok
25 Correct 45 ms 19036 KB Ok
26 Correct 44 ms 19036 KB Ok
27 Correct 45 ms 19032 KB Ok
28 Correct 45 ms 19188 KB Ok
29 Correct 45 ms 19184 KB Ok
30 Correct 51 ms 19032 KB Ok
31 Correct 48 ms 19036 KB Ok
32 Correct 44 ms 19136 KB Ok
33 Correct 44 ms 19036 KB Ok
34 Correct 45 ms 19032 KB Ok
35 Correct 48 ms 19032 KB Ok
36 Correct 44 ms 19036 KB Ok
37 Correct 44 ms 19032 KB Ok
38 Correct 44 ms 19036 KB Ok
39 Correct 288 ms 32280 KB Ok
40 Correct 240 ms 32152 KB Ok
41 Correct 433 ms 35724 KB Ok
42 Correct 379 ms 34928 KB Ok
43 Correct 235 ms 27672 KB Ok
44 Correct 347 ms 35664 KB Ok
45 Correct 46 ms 19292 KB Ok
46 Correct 46 ms 19284 KB Ok
47 Correct 48 ms 19304 KB Ok
48 Correct 46 ms 19288 KB Ok
49 Correct 50 ms 19548 KB Ok
50 Correct 46 ms 19208 KB Ok
51 Correct 45 ms 19280 KB Ok
52 Correct 46 ms 19280 KB Ok
53 Correct 47 ms 19288 KB Ok
54 Correct 50 ms 19236 KB Ok
55 Correct 53 ms 19540 KB Ok
56 Correct 55 ms 19536 KB Ok
57 Correct 52 ms 19540 KB Ok
58 Correct 57 ms 19536 KB Ok
59 Correct 55 ms 19544 KB Ok
60 Correct 51 ms 19536 KB Ok
61 Correct 57 ms 19536 KB Ok
62 Correct 55 ms 19536 KB Ok
63 Correct 53 ms 19536 KB Ok
64 Correct 54 ms 19540 KB Ok
65 Correct 141 ms 22604 KB Ok
66 Correct 160 ms 23240 KB Ok
67 Correct 155 ms 22560 KB Ok
68 Correct 118 ms 21736 KB Ok
69 Correct 151 ms 22968 KB Ok
70 Correct 144 ms 22324 KB Ok
71 Correct 129 ms 21976 KB Ok
72 Correct 141 ms 22512 KB Ok
73 Correct 175 ms 22700 KB Ok
74 Correct 143 ms 22340 KB Ok
75 Correct 166 ms 22480 KB Ok
76 Correct 155 ms 22844 KB Ok
77 Correct 130 ms 22540 KB Ok
78 Correct 124 ms 21824 KB Ok
79 Correct 153 ms 22380 KB Ok
80 Correct 582 ms 30912 KB Ok
81 Correct 624 ms 31556 KB Ok
82 Correct 552 ms 31060 KB Ok
83 Correct 559 ms 31388 KB Ok
84 Correct 572 ms 31044 KB Ok
85 Correct 527 ms 31112 KB Ok
86 Correct 469 ms 30968 KB Ok
87 Correct 644 ms 31160 KB Ok
88 Correct 477 ms 31520 KB Ok
89 Correct 635 ms 30792 KB Ok
90 Correct 555 ms 31904 KB Ok
91 Correct 521 ms 30772 KB Ok
92 Correct 490 ms 31300 KB Ok
93 Correct 575 ms 31468 KB Ok
94 Correct 539 ms 31084 KB Ok
95 Correct 330 ms 30100 KB Ok
96 Correct 591 ms 37900 KB Ok
97 Correct 509 ms 32204 KB Ok
98 Correct 332 ms 33304 KB Ok
99 Correct 433 ms 31092 KB Ok
100 Correct 480 ms 32144 KB Ok
101 Correct 451 ms 37336 KB Ok
102 Correct 461 ms 33168 KB Ok
103 Correct 471 ms 33908 KB Ok
104 Correct 527 ms 35976 KB Ok
105 Correct 556 ms 35860 KB Ok
106 Correct 440 ms 36996 KB Ok
107 Correct 538 ms 35292 KB Ok
108 Correct 567 ms 36524 KB Ok
109 Correct 470 ms 35596 KB Ok
110 Execution timed out 2029 ms 51196 KB Time limit exceeded
111 Halted 0 ms 0 KB -