oj.uz

Submission #496049

# Submission time Handle Problem Language Result Execution time Memory
496049 2021-12-20T13:33:23 Z mansur Nice sequence (IZhO18_sequence) C++17
58 / 100
 2000 ms 46708 KB 
#include<bits/stdc++.h>	
 
#pragma optimize ("g",on)
#pragma GCC optimize ("inline")
#pragma GCC optimize ("Ofast")
#pragma GCC optimize ("unroll-loops")
#pragma GCC optimize ("03")
#pragma GCC target ("sse,sse2,sse3,ssse3,sse4,popcnt,abm,avx2,mmx,fma,avx,tune=native")
#pragma comment(linker, "/stack:200000000")

//01001101 01100001 01101011 01101000 01100001  01100111 01100001 01111001 

using namespace std;

#define all(a) a.begin(), a.end()                                                   
#define rall(a) a.rbegin(), a.rend()
#define ll long long
#define pb push_back
#define sz(a) a.size()
#define nl '\n'
#define popb pop_back()                                                                   
#define ld double
#define ull unsigned long long
#define ff first                                         
#define ss second  
#define fix fixed << setprecision
#define pii pair<int, int>                          
#define E exit (0)
 
const int inf = 1e6, N = 4e5 + 1, mod = 998244353;                    

vector<pii> dir = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};

vector<int> adj[N + 7], was(N + 7), pref(N + 7), ans, cur, tp;

bool c;

void dfs(int u, int len) {
 	was[u] = 2;
 	for (auto e: adj[u]) {
 	    if (e > len) continue;
    	if (!was[e]) {
    		dfs(e, len);
    	}else if (was[e] == 2) c = 1;
    }
    was[u] = 1;
    tp.pb(u);
}	

bool can(int len, int n, int m) {
	for (int i = 0; i <= len; i++) {
		if (!was[i]) {
			dfs(i, len);           
		}
	}
	if (c) return 0;
	reverse(all(tp));
	int cnt = 0;
	for (auto e: tp) {
		pref[e] = cnt++;
	}
	for (int i = 1; i <= len; i++) {
		cur.pb(pref[i] - pref[i - 1]);	
	}
	return 1;
}

main() {                                                         
	//freopen("cowrect.in", "r", stdin);                                                                                     
	//freopen("cowrect.out", "w", stdout);                                                                                     
	ios_base::sync_with_stdio(NULL);                                                                                        
	cin.tie(NULL);
	int t;
	cin >> t;
	while (t--) {
		int n, m;
		cin >> n >> m;
		for (int i = 1; i <= N; i++) {
			if (i >= n) adj[i].pb(i - n);
			if (i >= m) adj[i - m].pb(i);	
		}
		int l = 1, r = N;
		vector<int> ans;
		while (l <= r) {
			int mid = (l + r) / 2;
			c = 0;
			tp.clear();  
			cur.clear();
			for (int i = 0; i <= mid; i++) {                                               
				was[i] = 0;
			}
			if (can(mid, n, m)) {
			 	ans = cur;
			 	l = mid + 1;
			}else {
				r = mid - 1;
			}
		}
		cout << sz(ans) << nl;
		for (auto e: ans) cout << e << ' ';
		cout << nl;
		for (int i = 0; i <= N; i++) adj[i].clear();
	}
}

Compilation message

sequence.cpp:3: warning: ignoring '#pragma optimize ' [-Wunknown-pragmas]
    3 | #pragma optimize ("g",on)
      | 
sequence.cpp:9: warning: ignoring '#pragma comment ' [-Wunknown-pragmas]
    9 | #pragma comment(linker, "/stack:200000000")
      | 
sequence.cpp:68:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   68 | main() {
      | ^~~~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 200 ms 38944 KB Ok
2 Correct 193 ms 38972 KB Ok
3 Correct 222 ms 27192 KB Ok
4 Correct 212 ms 27928 KB Ok
5 Correct 254 ms 27164 KB Ok
6 Correct 186 ms 29400 KB Ok
7 Correct 203 ms 26864 KB Ok
8 Correct 192 ms 29560 KB Ok
9 Correct 201 ms 26988 KB Ok
10 Correct 183 ms 32464 KB Ok
11 Correct 214 ms 27000 KB Ok
12 Correct 192 ms 26612 KB Ok

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 199 ms 38752 KB Ok
2 Correct 208 ms 38732 KB Ok
3 Correct 218 ms 38716 KB Ok
4 Correct 209 ms 38700 KB Ok
5 Correct 220 ms 38680 KB Ok
6 Correct 193 ms 38884 KB Ok
7 Correct 204 ms 38976 KB Ok
8 Correct 202 ms 38932 KB Ok
9 Correct 209 ms 39268 KB Ok
10 Correct 204 ms 38928 KB Ok

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 91 ms 38972 KB Ok
2 Correct 205 ms 38924 KB Ok
3 Correct 199 ms 38760 KB Ok
4 Correct 210 ms 38952 KB Ok
5 Correct 207 ms 38952 KB Ok
6 Correct 202 ms 38764 KB Ok
7 Correct 196 ms 39032 KB Ok
8 Correct 203 ms 38992 KB Ok
9 Correct 203 ms 38672 KB Ok
10 Correct 198 ms 38788 KB Ok
11 Correct 205 ms 38668 KB Ok

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 224 ms 39008 KB Ok
2 Correct 232 ms 38936 KB Ok
3 Correct 247 ms 39020 KB Ok
4 Correct 231 ms 38936 KB Ok
5 Correct 245 ms 38972 KB Ok
6 Correct 633 ms 44164 KB Ok
7 Correct 525 ms 42728 KB Ok
8 Correct 905 ms 46016 KB Ok
9 Correct 752 ms 46708 KB Ok
10 Correct 510 ms 42720 KB Ok
11 Correct 749 ms 45288 KB Ok

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 200 ms 38944 KB Ok
2 Correct 193 ms 38972 KB Ok
3 Correct 222 ms 27192 KB Ok
4 Correct 212 ms 27928 KB Ok
5 Correct 254 ms 27164 KB Ok
6 Correct 186 ms 29400 KB Ok
7 Correct 203 ms 26864 KB Ok
8 Correct 192 ms 29560 KB Ok
9 Correct 201 ms 26988 KB Ok
10 Correct 183 ms 32464 KB Ok
11 Correct 214 ms 27000 KB Ok
12 Correct 192 ms 26612 KB Ok
13 Correct 91 ms 38972 KB Ok
14 Correct 205 ms 38924 KB Ok
15 Correct 199 ms 38760 KB Ok
16 Correct 210 ms 38952 KB Ok
17 Correct 207 ms 38952 KB Ok
18 Correct 202 ms 38764 KB Ok
19 Correct 196 ms 39032 KB Ok
20 Correct 203 ms 38992 KB Ok
21 Correct 203 ms 38672 KB Ok
22 Correct 198 ms 38788 KB Ok
23 Correct 205 ms 38668 KB Ok
24 Correct 229 ms 26452 KB Ok
25 Correct 267 ms 26660 KB Ok
26 Correct 268 ms 27324 KB Ok
27 Correct 289 ms 27196 KB Ok
28 Correct 265 ms 26528 KB Ok
29 Correct 260 ms 30332 KB Ok
30 Correct 238 ms 27044 KB Ok
31 Correct 266 ms 26508 KB Ok
32 Correct 256 ms 26556 KB Ok
33 Correct 267 ms 27004 KB Ok
34 Correct 472 ms 38936 KB Ok
35 Correct 358 ms 38828 KB Ok
36 Correct 478 ms 39120 KB Ok
37 Correct 391 ms 38824 KB Ok
38 Correct 373 ms 38828 KB Ok
39 Correct 490 ms 38900 KB Ok
40 Correct 427 ms 39048 KB Ok
41 Correct 385 ms 38976 KB Ok
42 Correct 483 ms 39048 KB Ok
43 Correct 394 ms 38844 KB Ok

Subtask #6
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 200 ms 38944 KB Ok
2 Correct 193 ms 38972 KB Ok
3 Correct 222 ms 27192 KB Ok
4 Correct 212 ms 27928 KB Ok
5 Correct 254 ms 27164 KB Ok
6 Correct 186 ms 29400 KB Ok
7 Correct 203 ms 26864 KB Ok
8 Correct 192 ms 29560 KB Ok
9 Correct 201 ms 26988 KB Ok
10 Correct 183 ms 32464 KB Ok
11 Correct 214 ms 27000 KB Ok
12 Correct 192 ms 26612 KB Ok
13 Correct 199 ms 38752 KB Ok
14 Correct 208 ms 38732 KB Ok
15 Correct 218 ms 38716 KB Ok
16 Correct 209 ms 38700 KB Ok
17 Correct 220 ms 38680 KB Ok
18 Correct 193 ms 38884 KB Ok
19 Correct 204 ms 38976 KB Ok
20 Correct 202 ms 38932 KB Ok
21 Correct 209 ms 39268 KB Ok
22 Correct 204 ms 38928 KB Ok
23 Correct 91 ms 38972 KB Ok
24 Correct 205 ms 38924 KB Ok
25 Correct 199 ms 38760 KB Ok
26 Correct 210 ms 38952 KB Ok
27 Correct 207 ms 38952 KB Ok
28 Correct 202 ms 38764 KB Ok
29 Correct 196 ms 39032 KB Ok
30 Correct 203 ms 38992 KB Ok
31 Correct 203 ms 38672 KB Ok
32 Correct 198 ms 38788 KB Ok
33 Correct 205 ms 38668 KB Ok
34 Correct 229 ms 26452 KB Ok
35 Correct 267 ms 26660 KB Ok
36 Correct 268 ms 27324 KB Ok
37 Correct 289 ms 27196 KB Ok
38 Correct 265 ms 26528 KB Ok
39 Correct 260 ms 30332 KB Ok
40 Correct 238 ms 27044 KB Ok
41 Correct 266 ms 26508 KB Ok
42 Correct 256 ms 26556 KB Ok
43 Correct 267 ms 27004 KB Ok
44 Correct 472 ms 38936 KB Ok
45 Correct 358 ms 38828 KB Ok
46 Correct 478 ms 39120 KB Ok
47 Correct 391 ms 38824 KB Ok
48 Correct 373 ms 38828 KB Ok
49 Correct 490 ms 38900 KB Ok
50 Correct 427 ms 39048 KB Ok
51 Correct 385 ms 38976 KB Ok
52 Correct 483 ms 39048 KB Ok
53 Correct 394 ms 38844 KB Ok
54 Correct 403 ms 29552 KB Ok
55 Correct 467 ms 30160 KB Ok
56 Correct 443 ms 29868 KB Ok
57 Correct 331 ms 29072 KB Ok
58 Correct 475 ms 29708 KB Ok
59 Correct 430 ms 29928 KB Ok
60 Correct 398 ms 29412 KB Ok
61 Correct 337 ms 29300 KB Ok
62 Correct 519 ms 30456 KB Ok
63 Correct 426 ms 29448 KB Ok
64 Correct 449 ms 29904 KB Ok
65 Correct 478 ms 29872 KB Ok
66 Correct 388 ms 29724 KB Ok
67 Correct 338 ms 29256 KB Ok
68 Correct 437 ms 29624 KB Ok
69 Correct 1669 ms 46148 KB Ok
70 Correct 1955 ms 46580 KB Ok
71 Correct 1978 ms 46176 KB Ok
72 Correct 1713 ms 45988 KB Ok
73 Correct 1994 ms 46372 KB Ok
74 Execution timed out 2001 ms 45992 KB Time limit exceeded
75 Halted 0 ms 0 KB -

Subtask #7
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 200 ms 38944 KB Ok
2 Correct 193 ms 38972 KB Ok
3 Correct 222 ms 27192 KB Ok
4 Correct 212 ms 27928 KB Ok
5 Correct 254 ms 27164 KB Ok
6 Correct 186 ms 29400 KB Ok
7 Correct 203 ms 26864 KB Ok
8 Correct 192 ms 29560 KB Ok
9 Correct 201 ms 26988 KB Ok
10 Correct 183 ms 32464 KB Ok
11 Correct 214 ms 27000 KB Ok
12 Correct 192 ms 26612 KB Ok
13 Correct 199 ms 38752 KB Ok
14 Correct 208 ms 38732 KB Ok
15 Correct 218 ms 38716 KB Ok
16 Correct 209 ms 38700 KB Ok
17 Correct 220 ms 38680 KB Ok
18 Correct 193 ms 38884 KB Ok
19 Correct 204 ms 38976 KB Ok
20 Correct 202 ms 38932 KB Ok
21 Correct 209 ms 39268 KB Ok
22 Correct 204 ms 38928 KB Ok
23 Correct 91 ms 38972 KB Ok
24 Correct 205 ms 38924 KB Ok
25 Correct 199 ms 38760 KB Ok
26 Correct 210 ms 38952 KB Ok
27 Correct 207 ms 38952 KB Ok
28 Correct 202 ms 38764 KB Ok
29 Correct 196 ms 39032 KB Ok
30 Correct 203 ms 38992 KB Ok
31 Correct 203 ms 38672 KB Ok
32 Correct 198 ms 38788 KB Ok
33 Correct 205 ms 38668 KB Ok
34 Correct 224 ms 39008 KB Ok
35 Correct 232 ms 38936 KB Ok
36 Correct 247 ms 39020 KB Ok
37 Correct 231 ms 38936 KB Ok
38 Correct 245 ms 38972 KB Ok
39 Correct 633 ms 44164 KB Ok
40 Correct 525 ms 42728 KB Ok
41 Correct 905 ms 46016 KB Ok
42 Correct 752 ms 46708 KB Ok
43 Correct 510 ms 42720 KB Ok
44 Correct 749 ms 45288 KB Ok
45 Correct 229 ms 26452 KB Ok
46 Correct 267 ms 26660 KB Ok
47 Correct 268 ms 27324 KB Ok
48 Correct 289 ms 27196 KB Ok
49 Correct 265 ms 26528 KB Ok
50 Correct 260 ms 30332 KB Ok
51 Correct 238 ms 27044 KB Ok
52 Correct 266 ms 26508 KB Ok
53 Correct 256 ms 26556 KB Ok
54 Correct 267 ms 27004 KB Ok
55 Correct 472 ms 38936 KB Ok
56 Correct 358 ms 38828 KB Ok
57 Correct 478 ms 39120 KB Ok
58 Correct 391 ms 38824 KB Ok
59 Correct 373 ms 38828 KB Ok
60 Correct 490 ms 38900 KB Ok
61 Correct 427 ms 39048 KB Ok
62 Correct 385 ms 38976 KB Ok
63 Correct 483 ms 39048 KB Ok
64 Correct 394 ms 38844 KB Ok
65 Correct 403 ms 29552 KB Ok
66 Correct 467 ms 30160 KB Ok
67 Correct 443 ms 29868 KB Ok
68 Correct 331 ms 29072 KB Ok
69 Correct 475 ms 29708 KB Ok
70 Correct 430 ms 29928 KB Ok
71 Correct 398 ms 29412 KB Ok
72 Correct 337 ms 29300 KB Ok
73 Correct 519 ms 30456 KB Ok
74 Correct 426 ms 29448 KB Ok
75 Correct 449 ms 29904 KB Ok
76 Correct 478 ms 29872 KB Ok
77 Correct 388 ms 29724 KB Ok
78 Correct 338 ms 29256 KB Ok
79 Correct 437 ms 29624 KB Ok
80 Correct 1669 ms 46148 KB Ok
81 Correct 1955 ms 46580 KB Ok
82 Correct 1978 ms 46176 KB Ok
83 Correct 1713 ms 45988 KB Ok
84 Correct 1994 ms 46372 KB Ok
85 Execution timed out 2001 ms 45992 KB Time limit exceeded
86 Halted 0 ms 0 KB -