oj.uz

Submission #496026

# Submission time Handle Problem Language Result Execution time Memory
496026 2021-12-20T12:23:27 Z mansur Nice sequence (IZhO18_sequence) C++14
58 / 100
 2000 ms 54244 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 = 5e5 + 1, mod = 998244353;                    

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

vector<int> adj[N + 7], was(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 pref[len + 1], 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 247 ms 46380 KB Ok
2 Correct 254 ms 46420 KB Ok
3 Correct 317 ms 31880 KB Ok
4 Correct 253 ms 33008 KB Ok
5 Correct 337 ms 31832 KB Ok
6 Correct 225 ms 34616 KB Ok
7 Correct 248 ms 31468 KB Ok
8 Correct 238 ms 34720 KB Ok
9 Correct 261 ms 31748 KB Ok
10 Correct 228 ms 38572 KB Ok
11 Correct 266 ms 31568 KB Ok
12 Correct 248 ms 31200 KB Ok

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 241 ms 46392 KB Ok
2 Correct 266 ms 46404 KB Ok
3 Correct 290 ms 46392 KB Ok
4 Correct 267 ms 46464 KB Ok
5 Correct 273 ms 46392 KB Ok
6 Correct 241 ms 46476 KB Ok
7 Correct 256 ms 46648 KB Ok
8 Correct 261 ms 46520 KB Ok
9 Correct 265 ms 46940 KB Ok
10 Correct 261 ms 46464 KB Ok

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 111 ms 46432 KB Ok
2 Correct 257 ms 46432 KB Ok
3 Correct 258 ms 46288 KB Ok
4 Correct 246 ms 46412 KB Ok
5 Correct 262 ms 46364 KB Ok
6 Correct 266 ms 46420 KB Ok
7 Correct 262 ms 46396 KB Ok
8 Correct 257 ms 46352 KB Ok
9 Correct 264 ms 46416 KB Ok
10 Correct 254 ms 46372 KB Ok
11 Correct 267 ms 46328 KB Ok

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 286 ms 46396 KB Ok
2 Correct 320 ms 46464 KB Ok
3 Correct 309 ms 46360 KB Ok
4 Correct 297 ms 46400 KB Ok
5 Correct 315 ms 46392 KB Ok
6 Correct 685 ms 51604 KB Ok
7 Correct 578 ms 50460 KB Ok
8 Correct 969 ms 53968 KB Ok
9 Correct 776 ms 54244 KB Ok
10 Correct 541 ms 50080 KB Ok
11 Correct 777 ms 52932 KB Ok

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 247 ms 46380 KB Ok
2 Correct 254 ms 46420 KB Ok
3 Correct 317 ms 31880 KB Ok
4 Correct 253 ms 33008 KB Ok
5 Correct 337 ms 31832 KB Ok
6 Correct 225 ms 34616 KB Ok
7 Correct 248 ms 31468 KB Ok
8 Correct 238 ms 34720 KB Ok
9 Correct 261 ms 31748 KB Ok
10 Correct 228 ms 38572 KB Ok
11 Correct 266 ms 31568 KB Ok
12 Correct 248 ms 31200 KB Ok
13 Correct 111 ms 46432 KB Ok
14 Correct 257 ms 46432 KB Ok
15 Correct 258 ms 46288 KB Ok
16 Correct 246 ms 46412 KB Ok
17 Correct 262 ms 46364 KB Ok
18 Correct 266 ms 46420 KB Ok
19 Correct 262 ms 46396 KB Ok
20 Correct 257 ms 46352 KB Ok
21 Correct 264 ms 46416 KB Ok
22 Correct 254 ms 46372 KB Ok
23 Correct 267 ms 46328 KB Ok
24 Correct 295 ms 30864 KB Ok
25 Correct 332 ms 31032 KB Ok
26 Correct 316 ms 31848 KB Ok
27 Correct 325 ms 31992 KB Ok
28 Correct 327 ms 31056 KB Ok
29 Correct 331 ms 36012 KB Ok
30 Correct 299 ms 31556 KB Ok
31 Correct 341 ms 31032 KB Ok
32 Correct 343 ms 30972 KB Ok
33 Correct 360 ms 31612 KB Ok
34 Correct 649 ms 46520 KB Ok
35 Correct 425 ms 46612 KB Ok
36 Correct 601 ms 46520 KB Ok
37 Correct 469 ms 46544 KB Ok
38 Correct 446 ms 46444 KB Ok
39 Correct 572 ms 46544 KB Ok
40 Correct 515 ms 46512 KB Ok
41 Correct 447 ms 46472 KB Ok
42 Correct 641 ms 46536 KB Ok
43 Correct 510 ms 46520 KB Ok

Subtask #6
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 247 ms 46380 KB Ok
2 Correct 254 ms 46420 KB Ok
3 Correct 317 ms 31880 KB Ok
4 Correct 253 ms 33008 KB Ok
5 Correct 337 ms 31832 KB Ok
6 Correct 225 ms 34616 KB Ok
7 Correct 248 ms 31468 KB Ok
8 Correct 238 ms 34720 KB Ok
9 Correct 261 ms 31748 KB Ok
10 Correct 228 ms 38572 KB Ok
11 Correct 266 ms 31568 KB Ok
12 Correct 248 ms 31200 KB Ok
13 Correct 241 ms 46392 KB Ok
14 Correct 266 ms 46404 KB Ok
15 Correct 290 ms 46392 KB Ok
16 Correct 267 ms 46464 KB Ok
17 Correct 273 ms 46392 KB Ok
18 Correct 241 ms 46476 KB Ok
19 Correct 256 ms 46648 KB Ok
20 Correct 261 ms 46520 KB Ok
21 Correct 265 ms 46940 KB Ok
22 Correct 261 ms 46464 KB Ok
23 Correct 111 ms 46432 KB Ok
24 Correct 257 ms 46432 KB Ok
25 Correct 258 ms 46288 KB Ok
26 Correct 246 ms 46412 KB Ok
27 Correct 262 ms 46364 KB Ok
28 Correct 266 ms 46420 KB Ok
29 Correct 262 ms 46396 KB Ok
30 Correct 257 ms 46352 KB Ok
31 Correct 264 ms 46416 KB Ok
32 Correct 254 ms 46372 KB Ok
33 Correct 267 ms 46328 KB Ok
34 Correct 295 ms 30864 KB Ok
35 Correct 332 ms 31032 KB Ok
36 Correct 316 ms 31848 KB Ok
37 Correct 325 ms 31992 KB Ok
38 Correct 327 ms 31056 KB Ok
39 Correct 331 ms 36012 KB Ok
40 Correct 299 ms 31556 KB Ok
41 Correct 341 ms 31032 KB Ok
42 Correct 343 ms 30972 KB Ok
43 Correct 360 ms 31612 KB Ok
44 Correct 649 ms 46520 KB Ok
45 Correct 425 ms 46612 KB Ok
46 Correct 601 ms 46520 KB Ok
47 Correct 469 ms 46544 KB Ok
48 Correct 446 ms 46444 KB Ok
49 Correct 572 ms 46544 KB Ok
50 Correct 515 ms 46512 KB Ok
51 Correct 447 ms 46472 KB Ok
52 Correct 641 ms 46536 KB Ok
53 Correct 510 ms 46520 KB Ok
54 Correct 446 ms 34348 KB Ok
55 Correct 471 ms 34844 KB Ok
56 Correct 468 ms 34844 KB Ok
57 Correct 352 ms 33848 KB Ok
58 Correct 481 ms 34688 KB Ok
59 Correct 440 ms 34484 KB Ok
60 Correct 406 ms 34076 KB Ok
61 Correct 360 ms 34156 KB Ok
62 Correct 564 ms 34956 KB Ok
63 Correct 449 ms 34228 KB Ok
64 Correct 502 ms 34868 KB Ok
65 Correct 460 ms 34616 KB Ok
66 Correct 381 ms 34360 KB Ok
67 Correct 382 ms 34136 KB Ok
68 Correct 470 ms 34548 KB Ok
69 Execution timed out 2053 ms 50748 KB Time limit exceeded
70 Halted 0 ms 0 KB -

Subtask #7
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 247 ms 46380 KB Ok
2 Correct 254 ms 46420 KB Ok
3 Correct 317 ms 31880 KB Ok
4 Correct 253 ms 33008 KB Ok
5 Correct 337 ms 31832 KB Ok
6 Correct 225 ms 34616 KB Ok
7 Correct 248 ms 31468 KB Ok
8 Correct 238 ms 34720 KB Ok
9 Correct 261 ms 31748 KB Ok
10 Correct 228 ms 38572 KB Ok
11 Correct 266 ms 31568 KB Ok
12 Correct 248 ms 31200 KB Ok
13 Correct 241 ms 46392 KB Ok
14 Correct 266 ms 46404 KB Ok
15 Correct 290 ms 46392 KB Ok
16 Correct 267 ms 46464 KB Ok
17 Correct 273 ms 46392 KB Ok
18 Correct 241 ms 46476 KB Ok
19 Correct 256 ms 46648 KB Ok
20 Correct 261 ms 46520 KB Ok
21 Correct 265 ms 46940 KB Ok
22 Correct 261 ms 46464 KB Ok
23 Correct 111 ms 46432 KB Ok
24 Correct 257 ms 46432 KB Ok
25 Correct 258 ms 46288 KB Ok
26 Correct 246 ms 46412 KB Ok
27 Correct 262 ms 46364 KB Ok
28 Correct 266 ms 46420 KB Ok
29 Correct 262 ms 46396 KB Ok
30 Correct 257 ms 46352 KB Ok
31 Correct 264 ms 46416 KB Ok
32 Correct 254 ms 46372 KB Ok
33 Correct 267 ms 46328 KB Ok
34 Correct 286 ms 46396 KB Ok
35 Correct 320 ms 46464 KB Ok
36 Correct 309 ms 46360 KB Ok
37 Correct 297 ms 46400 KB Ok
38 Correct 315 ms 46392 KB Ok
39 Correct 685 ms 51604 KB Ok
40 Correct 578 ms 50460 KB Ok
41 Correct 969 ms 53968 KB Ok
42 Correct 776 ms 54244 KB Ok
43 Correct 541 ms 50080 KB Ok
44 Correct 777 ms 52932 KB Ok
45 Correct 295 ms 30864 KB Ok
46 Correct 332 ms 31032 KB Ok
47 Correct 316 ms 31848 KB Ok
48 Correct 325 ms 31992 KB Ok
49 Correct 327 ms 31056 KB Ok
50 Correct 331 ms 36012 KB Ok
51 Correct 299 ms 31556 KB Ok
52 Correct 341 ms 31032 KB Ok
53 Correct 343 ms 30972 KB Ok
54 Correct 360 ms 31612 KB Ok
55 Correct 649 ms 46520 KB Ok
56 Correct 425 ms 46612 KB Ok
57 Correct 601 ms 46520 KB Ok
58 Correct 469 ms 46544 KB Ok
59 Correct 446 ms 46444 KB Ok
60 Correct 572 ms 46544 KB Ok
61 Correct 515 ms 46512 KB Ok
62 Correct 447 ms 46472 KB Ok
63 Correct 641 ms 46536 KB Ok
64 Correct 510 ms 46520 KB Ok
65 Correct 446 ms 34348 KB Ok
66 Correct 471 ms 34844 KB Ok
67 Correct 468 ms 34844 KB Ok
68 Correct 352 ms 33848 KB Ok
69 Correct 481 ms 34688 KB Ok
70 Correct 440 ms 34484 KB Ok
71 Correct 406 ms 34076 KB Ok
72 Correct 360 ms 34156 KB Ok
73 Correct 564 ms 34956 KB Ok
74 Correct 449 ms 34228 KB Ok
75 Correct 502 ms 34868 KB Ok
76 Correct 460 ms 34616 KB Ok
77 Correct 381 ms 34360 KB Ok
78 Correct 382 ms 34136 KB Ok
79 Correct 470 ms 34548 KB Ok
80 Execution timed out 2053 ms 50748 KB Time limit exceeded
81 Halted 0 ms 0 KB -