oj.uz

Submission #496027

# Submission time Handle Problem Language Result Execution time Memory
496027 2021-12-20T12:24:43 Z mansur Nice sequence (IZhO18_sequence) C++17
58 / 100
 2000 ms 54280 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 263 ms 46480 KB Ok
2 Correct 260 ms 46460 KB Ok
3 Correct 344 ms 31856 KB Ok
4 Correct 280 ms 32948 KB Ok
5 Correct 359 ms 31888 KB Ok
6 Correct 225 ms 34676 KB Ok
7 Correct 300 ms 31532 KB Ok
8 Correct 252 ms 34624 KB Ok
9 Correct 242 ms 31808 KB Ok
10 Correct 257 ms 38584 KB Ok
11 Correct 279 ms 31552 KB Ok
12 Correct 232 ms 31148 KB Ok

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 267 ms 46308 KB Ok
2 Correct 258 ms 46412 KB Ok
3 Correct 293 ms 46352 KB Ok
4 Correct 284 ms 46316 KB Ok
5 Correct 296 ms 46320 KB Ok
6 Correct 242 ms 46472 KB Ok
7 Correct 251 ms 46720 KB Ok
8 Correct 259 ms 46544 KB Ok
9 Correct 253 ms 46904 KB Ok
10 Correct 250 ms 46392 KB Ok

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 103 ms 46400 KB Ok
2 Correct 267 ms 46372 KB Ok
3 Correct 261 ms 46396 KB Ok
4 Correct 254 ms 46440 KB Ok
5 Correct 277 ms 46364 KB Ok
6 Correct 254 ms 46296 KB Ok
7 Correct 265 ms 46372 KB Ok
8 Correct 267 ms 46468 KB Ok
9 Correct 271 ms 46292 KB Ok
10 Correct 266 ms 46328 KB Ok
11 Correct 250 ms 46304 KB Ok

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 286 ms 46452 KB Ok
2 Correct 294 ms 46432 KB Ok
3 Correct 307 ms 46460 KB Ok
4 Correct 298 ms 46408 KB Ok
5 Correct 354 ms 46432 KB Ok
6 Correct 688 ms 51744 KB Ok
7 Correct 562 ms 50472 KB Ok
8 Correct 984 ms 53980 KB Ok
9 Correct 741 ms 54280 KB Ok
10 Correct 524 ms 50084 KB Ok
11 Correct 854 ms 52796 KB Ok

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 263 ms 46480 KB Ok
2 Correct 260 ms 46460 KB Ok
3 Correct 344 ms 31856 KB Ok
4 Correct 280 ms 32948 KB Ok
5 Correct 359 ms 31888 KB Ok
6 Correct 225 ms 34676 KB Ok
7 Correct 300 ms 31532 KB Ok
8 Correct 252 ms 34624 KB Ok
9 Correct 242 ms 31808 KB Ok
10 Correct 257 ms 38584 KB Ok
11 Correct 279 ms 31552 KB Ok
12 Correct 232 ms 31148 KB Ok
13 Correct 103 ms 46400 KB Ok
14 Correct 267 ms 46372 KB Ok
15 Correct 261 ms 46396 KB Ok
16 Correct 254 ms 46440 KB Ok
17 Correct 277 ms 46364 KB Ok
18 Correct 254 ms 46296 KB Ok
19 Correct 265 ms 46372 KB Ok
20 Correct 267 ms 46468 KB Ok
21 Correct 271 ms 46292 KB Ok
22 Correct 266 ms 46328 KB Ok
23 Correct 250 ms 46304 KB Ok
24 Correct 306 ms 30840 KB Ok
25 Correct 345 ms 31100 KB Ok
26 Correct 308 ms 32076 KB Ok
27 Correct 379 ms 31924 KB Ok
28 Correct 348 ms 31160 KB Ok
29 Correct 324 ms 35976 KB Ok
30 Correct 321 ms 31464 KB Ok
31 Correct 329 ms 31064 KB Ok
32 Correct 339 ms 30984 KB Ok
33 Correct 327 ms 31832 KB Ok
34 Correct 633 ms 46732 KB Ok
35 Correct 434 ms 46516 KB Ok
36 Correct 586 ms 46776 KB Ok
37 Correct 451 ms 46524 KB Ok
38 Correct 478 ms 46752 KB Ok
39 Correct 616 ms 46684 KB Ok
40 Correct 587 ms 46520 KB Ok
41 Correct 433 ms 46488 KB Ok
42 Correct 664 ms 46584 KB Ok
43 Correct 524 ms 46492 KB Ok

Subtask #6
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 263 ms 46480 KB Ok
2 Correct 260 ms 46460 KB Ok
3 Correct 344 ms 31856 KB Ok
4 Correct 280 ms 32948 KB Ok
5 Correct 359 ms 31888 KB Ok
6 Correct 225 ms 34676 KB Ok
7 Correct 300 ms 31532 KB Ok
8 Correct 252 ms 34624 KB Ok
9 Correct 242 ms 31808 KB Ok
10 Correct 257 ms 38584 KB Ok
11 Correct 279 ms 31552 KB Ok
12 Correct 232 ms 31148 KB Ok
13 Correct 267 ms 46308 KB Ok
14 Correct 258 ms 46412 KB Ok
15 Correct 293 ms 46352 KB Ok
16 Correct 284 ms 46316 KB Ok
17 Correct 296 ms 46320 KB Ok
18 Correct 242 ms 46472 KB Ok
19 Correct 251 ms 46720 KB Ok
20 Correct 259 ms 46544 KB Ok
21 Correct 253 ms 46904 KB Ok
22 Correct 250 ms 46392 KB Ok
23 Correct 103 ms 46400 KB Ok
24 Correct 267 ms 46372 KB Ok
25 Correct 261 ms 46396 KB Ok
26 Correct 254 ms 46440 KB Ok
27 Correct 277 ms 46364 KB Ok
28 Correct 254 ms 46296 KB Ok
29 Correct 265 ms 46372 KB Ok
30 Correct 267 ms 46468 KB Ok
31 Correct 271 ms 46292 KB Ok
32 Correct 266 ms 46328 KB Ok
33 Correct 250 ms 46304 KB Ok
34 Correct 306 ms 30840 KB Ok
35 Correct 345 ms 31100 KB Ok
36 Correct 308 ms 32076 KB Ok
37 Correct 379 ms 31924 KB Ok
38 Correct 348 ms 31160 KB Ok
39 Correct 324 ms 35976 KB Ok
40 Correct 321 ms 31464 KB Ok
41 Correct 329 ms 31064 KB Ok
42 Correct 339 ms 30984 KB Ok
43 Correct 327 ms 31832 KB Ok
44 Correct 633 ms 46732 KB Ok
45 Correct 434 ms 46516 KB Ok
46 Correct 586 ms 46776 KB Ok
47 Correct 451 ms 46524 KB Ok
48 Correct 478 ms 46752 KB Ok
49 Correct 616 ms 46684 KB Ok
50 Correct 587 ms 46520 KB Ok
51 Correct 433 ms 46488 KB Ok
52 Correct 664 ms 46584 KB Ok
53 Correct 524 ms 46492 KB Ok
54 Correct 428 ms 34308 KB Ok
55 Correct 542 ms 35024 KB Ok
56 Correct 442 ms 34740 KB Ok
57 Correct 364 ms 33832 KB Ok
58 Correct 522 ms 34544 KB Ok
59 Correct 430 ms 34392 KB Ok
60 Correct 483 ms 34056 KB Ok
61 Correct 370 ms 34212 KB Ok
62 Correct 545 ms 35032 KB Ok
63 Correct 473 ms 34360 KB Ok
64 Correct 540 ms 34768 KB Ok
65 Correct 520 ms 34668 KB Ok
66 Correct 423 ms 34268 KB Ok
67 Correct 424 ms 33988 KB Ok
68 Correct 511 ms 34636 KB Ok
69 Execution timed out 2064 ms 49404 KB Time limit exceeded
70 Halted 0 ms 0 KB -

Subtask #7
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 263 ms 46480 KB Ok
2 Correct 260 ms 46460 KB Ok
3 Correct 344 ms 31856 KB Ok
4 Correct 280 ms 32948 KB Ok
5 Correct 359 ms 31888 KB Ok
6 Correct 225 ms 34676 KB Ok
7 Correct 300 ms 31532 KB Ok
8 Correct 252 ms 34624 KB Ok
9 Correct 242 ms 31808 KB Ok
10 Correct 257 ms 38584 KB Ok
11 Correct 279 ms 31552 KB Ok
12 Correct 232 ms 31148 KB Ok
13 Correct 267 ms 46308 KB Ok
14 Correct 258 ms 46412 KB Ok
15 Correct 293 ms 46352 KB Ok
16 Correct 284 ms 46316 KB Ok
17 Correct 296 ms 46320 KB Ok
18 Correct 242 ms 46472 KB Ok
19 Correct 251 ms 46720 KB Ok
20 Correct 259 ms 46544 KB Ok
21 Correct 253 ms 46904 KB Ok
22 Correct 250 ms 46392 KB Ok
23 Correct 103 ms 46400 KB Ok
24 Correct 267 ms 46372 KB Ok
25 Correct 261 ms 46396 KB Ok
26 Correct 254 ms 46440 KB Ok
27 Correct 277 ms 46364 KB Ok
28 Correct 254 ms 46296 KB Ok
29 Correct 265 ms 46372 KB Ok
30 Correct 267 ms 46468 KB Ok
31 Correct 271 ms 46292 KB Ok
32 Correct 266 ms 46328 KB Ok
33 Correct 250 ms 46304 KB Ok
34 Correct 286 ms 46452 KB Ok
35 Correct 294 ms 46432 KB Ok
36 Correct 307 ms 46460 KB Ok
37 Correct 298 ms 46408 KB Ok
38 Correct 354 ms 46432 KB Ok
39 Correct 688 ms 51744 KB Ok
40 Correct 562 ms 50472 KB Ok
41 Correct 984 ms 53980 KB Ok
42 Correct 741 ms 54280 KB Ok
43 Correct 524 ms 50084 KB Ok
44 Correct 854 ms 52796 KB Ok
45 Correct 306 ms 30840 KB Ok
46 Correct 345 ms 31100 KB Ok
47 Correct 308 ms 32076 KB Ok
48 Correct 379 ms 31924 KB Ok
49 Correct 348 ms 31160 KB Ok
50 Correct 324 ms 35976 KB Ok
51 Correct 321 ms 31464 KB Ok
52 Correct 329 ms 31064 KB Ok
53 Correct 339 ms 30984 KB Ok
54 Correct 327 ms 31832 KB Ok
55 Correct 633 ms 46732 KB Ok
56 Correct 434 ms 46516 KB Ok
57 Correct 586 ms 46776 KB Ok
58 Correct 451 ms 46524 KB Ok
59 Correct 478 ms 46752 KB Ok
60 Correct 616 ms 46684 KB Ok
61 Correct 587 ms 46520 KB Ok
62 Correct 433 ms 46488 KB Ok
63 Correct 664 ms 46584 KB Ok
64 Correct 524 ms 46492 KB Ok
65 Correct 428 ms 34308 KB Ok
66 Correct 542 ms 35024 KB Ok
67 Correct 442 ms 34740 KB Ok
68 Correct 364 ms 33832 KB Ok
69 Correct 522 ms 34544 KB Ok
70 Correct 430 ms 34392 KB Ok
71 Correct 483 ms 34056 KB Ok
72 Correct 370 ms 34212 KB Ok
73 Correct 545 ms 35032 KB Ok
74 Correct 473 ms 34360 KB Ok
75 Correct 540 ms 34768 KB Ok
76 Correct 520 ms 34668 KB Ok
77 Correct 423 ms 34268 KB Ok
78 Correct 424 ms 33988 KB Ok
79 Correct 511 ms 34636 KB Ok
80 Execution timed out 2064 ms 49404 KB Time limit exceeded
81 Halted 0 ms 0 KB -