oj.uz

Submission #496005

# Submission time Handle Problem Language Result Execution time Memory
496005 2021-12-20T11:22:22 Z mansur Nice sequence (IZhO18_sequence) C++14
58 / 100
 2000 ms 42548 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], was(N), ans, cur, tp;

bool c;

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

bool can(int len, int n, int m) {
	for (int i = n; i <= len; i++) {
		adj[i].pb(i - n);
	}
	for (int i = m; i <= len; i++) {
		adj[i - m].pb(i);
	}
	for (int i = 0; i <= len; i++) {
		if (!was[i]) {
			dfs(i);
		}
	}
	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;
		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;
				adj[i].clear();
			}
			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;
	}
}

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:73:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   73 | main() {
      | ^~~~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 202 ms 34740 KB Ok
2 Correct 259 ms 34616 KB Ok
3 Correct 259 ms 23768 KB Ok
4 Correct 245 ms 24560 KB Ok
5 Correct 310 ms 23780 KB Ok
6 Correct 200 ms 25856 KB Ok
7 Correct 229 ms 23500 KB Ok
8 Correct 214 ms 25808 KB Ok
9 Correct 239 ms 23720 KB Ok
10 Correct 191 ms 28744 KB Ok
11 Correct 229 ms 23532 KB Ok
12 Correct 190 ms 23280 KB Ok

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 220 ms 34624 KB Ok
2 Correct 218 ms 34596 KB Ok
3 Correct 265 ms 34624 KB Ok
4 Correct 237 ms 34572 KB Ok
5 Correct 243 ms 34632 KB Ok
6 Correct 216 ms 34648 KB Ok
7 Correct 239 ms 35028 KB Ok
8 Correct 213 ms 34768 KB Ok
9 Correct 249 ms 35240 KB Ok
10 Correct 254 ms 34764 KB Ok

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 34644 KB Ok
2 Correct 208 ms 34644 KB Ok
3 Correct 219 ms 34624 KB Ok
4 Correct 224 ms 34696 KB Ok
5 Correct 226 ms 34612 KB Ok
6 Correct 224 ms 34624 KB Ok
7 Correct 212 ms 34676 KB Ok
8 Correct 246 ms 34624 KB Ok
9 Correct 236 ms 34628 KB Ok
10 Correct 226 ms 34668 KB Ok
11 Correct 225 ms 34576 KB Ok

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 245 ms 34640 KB Ok
2 Correct 250 ms 34628 KB Ok
3 Correct 276 ms 34628 KB Ok
4 Correct 268 ms 34624 KB Ok
5 Correct 302 ms 34628 KB Ok
6 Correct 615 ms 39904 KB Ok
7 Correct 567 ms 38784 KB Ok
8 Correct 953 ms 42156 KB Ok
9 Correct 689 ms 42548 KB Ok
10 Correct 508 ms 38488 KB Ok
11 Correct 793 ms 41108 KB Ok

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 202 ms 34740 KB Ok
2 Correct 259 ms 34616 KB Ok
3 Correct 259 ms 23768 KB Ok
4 Correct 245 ms 24560 KB Ok
5 Correct 310 ms 23780 KB Ok
6 Correct 200 ms 25856 KB Ok
7 Correct 229 ms 23500 KB Ok
8 Correct 214 ms 25808 KB Ok
9 Correct 239 ms 23720 KB Ok
10 Correct 191 ms 28744 KB Ok
11 Correct 229 ms 23532 KB Ok
12 Correct 190 ms 23280 KB Ok
13 Correct 82 ms 34644 KB Ok
14 Correct 208 ms 34644 KB Ok
15 Correct 219 ms 34624 KB Ok
16 Correct 224 ms 34696 KB Ok
17 Correct 226 ms 34612 KB Ok
18 Correct 224 ms 34624 KB Ok
19 Correct 212 ms 34676 KB Ok
20 Correct 246 ms 34624 KB Ok
21 Correct 236 ms 34628 KB Ok
22 Correct 226 ms 34668 KB Ok
23 Correct 225 ms 34576 KB Ok
24 Correct 272 ms 22984 KB Ok
25 Correct 327 ms 23120 KB Ok
26 Correct 306 ms 23836 KB Ok
27 Correct 376 ms 23852 KB Ok
28 Correct 281 ms 23196 KB Ok
29 Correct 283 ms 26856 KB Ok
30 Correct 288 ms 23464 KB Ok
31 Correct 328 ms 23288 KB Ok
32 Correct 306 ms 23108 KB Ok
33 Correct 326 ms 23528 KB Ok
34 Correct 623 ms 34888 KB Ok
35 Correct 375 ms 34864 KB Ok
36 Correct 521 ms 34780 KB Ok
37 Correct 380 ms 34820 KB Ok
38 Correct 437 ms 34876 KB Ok
39 Correct 633 ms 34752 KB Ok
40 Correct 427 ms 34848 KB Ok
41 Correct 403 ms 35032 KB Ok
42 Correct 618 ms 34736 KB Ok
43 Correct 452 ms 34768 KB Ok

Subtask #6
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 202 ms 34740 KB Ok
2 Correct 259 ms 34616 KB Ok
3 Correct 259 ms 23768 KB Ok
4 Correct 245 ms 24560 KB Ok
5 Correct 310 ms 23780 KB Ok
6 Correct 200 ms 25856 KB Ok
7 Correct 229 ms 23500 KB Ok
8 Correct 214 ms 25808 KB Ok
9 Correct 239 ms 23720 KB Ok
10 Correct 191 ms 28744 KB Ok
11 Correct 229 ms 23532 KB Ok
12 Correct 190 ms 23280 KB Ok
13 Correct 220 ms 34624 KB Ok
14 Correct 218 ms 34596 KB Ok
15 Correct 265 ms 34624 KB Ok
16 Correct 237 ms 34572 KB Ok
17 Correct 243 ms 34632 KB Ok
18 Correct 216 ms 34648 KB Ok
19 Correct 239 ms 35028 KB Ok
20 Correct 213 ms 34768 KB Ok
21 Correct 249 ms 35240 KB Ok
22 Correct 254 ms 34764 KB Ok
23 Correct 82 ms 34644 KB Ok
24 Correct 208 ms 34644 KB Ok
25 Correct 219 ms 34624 KB Ok
26 Correct 224 ms 34696 KB Ok
27 Correct 226 ms 34612 KB Ok
28 Correct 224 ms 34624 KB Ok
29 Correct 212 ms 34676 KB Ok
30 Correct 246 ms 34624 KB Ok
31 Correct 236 ms 34628 KB Ok
32 Correct 226 ms 34668 KB Ok
33 Correct 225 ms 34576 KB Ok
34 Correct 272 ms 22984 KB Ok
35 Correct 327 ms 23120 KB Ok
36 Correct 306 ms 23836 KB Ok
37 Correct 376 ms 23852 KB Ok
38 Correct 281 ms 23196 KB Ok
39 Correct 283 ms 26856 KB Ok
40 Correct 288 ms 23464 KB Ok
41 Correct 328 ms 23288 KB Ok
42 Correct 306 ms 23108 KB Ok
43 Correct 326 ms 23528 KB Ok
44 Correct 623 ms 34888 KB Ok
45 Correct 375 ms 34864 KB Ok
46 Correct 521 ms 34780 KB Ok
47 Correct 380 ms 34820 KB Ok
48 Correct 437 ms 34876 KB Ok
49 Correct 633 ms 34752 KB Ok
50 Correct 427 ms 34848 KB Ok
51 Correct 403 ms 35032 KB Ok
52 Correct 618 ms 34736 KB Ok
53 Correct 452 ms 34768 KB Ok
54 Correct 456 ms 26640 KB Ok
55 Correct 482 ms 26956 KB Ok
56 Correct 460 ms 26888 KB Ok
57 Correct 382 ms 26040 KB Ok
58 Correct 494 ms 26836 KB Ok
59 Correct 440 ms 26560 KB Ok
60 Correct 381 ms 26224 KB Ok
61 Correct 373 ms 26320 KB Ok
62 Correct 543 ms 27144 KB Ok
63 Correct 471 ms 26440 KB Ok
64 Correct 518 ms 26856 KB Ok
65 Correct 477 ms 26760 KB Ok
66 Correct 438 ms 26504 KB Ok
67 Correct 380 ms 26208 KB Ok
68 Correct 437 ms 26716 KB Ok
69 Execution timed out 2047 ms 38476 KB Time limit exceeded
70 Halted 0 ms 0 KB -

Subtask #7
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 202 ms 34740 KB Ok
2 Correct 259 ms 34616 KB Ok
3 Correct 259 ms 23768 KB Ok
4 Correct 245 ms 24560 KB Ok
5 Correct 310 ms 23780 KB Ok
6 Correct 200 ms 25856 KB Ok
7 Correct 229 ms 23500 KB Ok
8 Correct 214 ms 25808 KB Ok
9 Correct 239 ms 23720 KB Ok
10 Correct 191 ms 28744 KB Ok
11 Correct 229 ms 23532 KB Ok
12 Correct 190 ms 23280 KB Ok
13 Correct 220 ms 34624 KB Ok
14 Correct 218 ms 34596 KB Ok
15 Correct 265 ms 34624 KB Ok
16 Correct 237 ms 34572 KB Ok
17 Correct 243 ms 34632 KB Ok
18 Correct 216 ms 34648 KB Ok
19 Correct 239 ms 35028 KB Ok
20 Correct 213 ms 34768 KB Ok
21 Correct 249 ms 35240 KB Ok
22 Correct 254 ms 34764 KB Ok
23 Correct 82 ms 34644 KB Ok
24 Correct 208 ms 34644 KB Ok
25 Correct 219 ms 34624 KB Ok
26 Correct 224 ms 34696 KB Ok
27 Correct 226 ms 34612 KB Ok
28 Correct 224 ms 34624 KB Ok
29 Correct 212 ms 34676 KB Ok
30 Correct 246 ms 34624 KB Ok
31 Correct 236 ms 34628 KB Ok
32 Correct 226 ms 34668 KB Ok
33 Correct 225 ms 34576 KB Ok
34 Correct 245 ms 34640 KB Ok
35 Correct 250 ms 34628 KB Ok
36 Correct 276 ms 34628 KB Ok
37 Correct 268 ms 34624 KB Ok
38 Correct 302 ms 34628 KB Ok
39 Correct 615 ms 39904 KB Ok
40 Correct 567 ms 38784 KB Ok
41 Correct 953 ms 42156 KB Ok
42 Correct 689 ms 42548 KB Ok
43 Correct 508 ms 38488 KB Ok
44 Correct 793 ms 41108 KB Ok
45 Correct 272 ms 22984 KB Ok
46 Correct 327 ms 23120 KB Ok
47 Correct 306 ms 23836 KB Ok
48 Correct 376 ms 23852 KB Ok
49 Correct 281 ms 23196 KB Ok
50 Correct 283 ms 26856 KB Ok
51 Correct 288 ms 23464 KB Ok
52 Correct 328 ms 23288 KB Ok
53 Correct 306 ms 23108 KB Ok
54 Correct 326 ms 23528 KB Ok
55 Correct 623 ms 34888 KB Ok
56 Correct 375 ms 34864 KB Ok
57 Correct 521 ms 34780 KB Ok
58 Correct 380 ms 34820 KB Ok
59 Correct 437 ms 34876 KB Ok
60 Correct 633 ms 34752 KB Ok
61 Correct 427 ms 34848 KB Ok
62 Correct 403 ms 35032 KB Ok
63 Correct 618 ms 34736 KB Ok
64 Correct 452 ms 34768 KB Ok
65 Correct 456 ms 26640 KB Ok
66 Correct 482 ms 26956 KB Ok
67 Correct 460 ms 26888 KB Ok
68 Correct 382 ms 26040 KB Ok
69 Correct 494 ms 26836 KB Ok
70 Correct 440 ms 26560 KB Ok
71 Correct 381 ms 26224 KB Ok
72 Correct 373 ms 26320 KB Ok
73 Correct 543 ms 27144 KB Ok
74 Correct 471 ms 26440 KB Ok
75 Correct 518 ms 26856 KB Ok
76 Correct 477 ms 26760 KB Ok
77 Correct 438 ms 26504 KB Ok
78 Correct 380 ms 26208 KB Ok
79 Correct 437 ms 26716 KB Ok
80 Execution timed out 2047 ms 38476 KB Time limit exceeded
81 Halted 0 ms 0 KB -