oj.uz

Submission #496006

# Submission time Handle Problem Language Result Execution time Memory
496006 2021-12-20T11:23:52 Z mansur Nice sequence (IZhO18_sequence) C++14
58 / 100
 2000 ms 42592 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) {
 	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 214 ms 34716 KB Ok
2 Correct 218 ms 34632 KB Ok
3 Correct 232 ms 23760 KB Ok
4 Correct 226 ms 24572 KB Ok
5 Correct 295 ms 23760 KB Ok
6 Correct 201 ms 25864 KB Ok
7 Correct 209 ms 23412 KB Ok
8 Correct 214 ms 25804 KB Ok
9 Correct 217 ms 23616 KB Ok
10 Correct 222 ms 28752 KB Ok
11 Correct 251 ms 23592 KB Ok
12 Correct 187 ms 23268 KB Ok

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 218 ms 34576 KB Ok
2 Correct 222 ms 34576 KB Ok
3 Correct 243 ms 34624 KB Ok
4 Correct 227 ms 34680 KB Ok
5 Correct 250 ms 34624 KB Ok
6 Correct 236 ms 34692 KB Ok
7 Correct 225 ms 35140 KB Ok
8 Correct 217 ms 34824 KB Ok
9 Correct 246 ms 35136 KB Ok
10 Correct 210 ms 34752 KB Ok

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 34696 KB Ok
2 Correct 260 ms 34644 KB Ok
3 Correct 212 ms 34624 KB Ok
4 Correct 222 ms 34640 KB Ok
5 Correct 234 ms 34628 KB Ok
6 Correct 238 ms 34640 KB Ok
7 Correct 243 ms 34644 KB Ok
8 Correct 220 ms 34728 KB Ok
9 Correct 244 ms 34576 KB Ok
10 Correct 234 ms 34664 KB Ok
11 Correct 233 ms 34684 KB Ok

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 243 ms 34628 KB Ok
2 Correct 235 ms 34648 KB Ok
3 Correct 294 ms 34676 KB Ok
4 Correct 277 ms 34628 KB Ok
5 Correct 318 ms 34680 KB Ok
6 Correct 633 ms 39908 KB Ok
7 Correct 577 ms 38680 KB Ok
8 Correct 933 ms 42164 KB Ok
9 Correct 724 ms 42592 KB Ok
10 Correct 492 ms 38516 KB Ok
11 Correct 776 ms 41088 KB Ok

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 214 ms 34716 KB Ok
2 Correct 218 ms 34632 KB Ok
3 Correct 232 ms 23760 KB Ok
4 Correct 226 ms 24572 KB Ok
5 Correct 295 ms 23760 KB Ok
6 Correct 201 ms 25864 KB Ok
7 Correct 209 ms 23412 KB Ok
8 Correct 214 ms 25804 KB Ok
9 Correct 217 ms 23616 KB Ok
10 Correct 222 ms 28752 KB Ok
11 Correct 251 ms 23592 KB Ok
12 Correct 187 ms 23268 KB Ok
13 Correct 80 ms 34696 KB Ok
14 Correct 260 ms 34644 KB Ok
15 Correct 212 ms 34624 KB Ok
16 Correct 222 ms 34640 KB Ok
17 Correct 234 ms 34628 KB Ok
18 Correct 238 ms 34640 KB Ok
19 Correct 243 ms 34644 KB Ok
20 Correct 220 ms 34728 KB Ok
21 Correct 244 ms 34576 KB Ok
22 Correct 234 ms 34664 KB Ok
23 Correct 233 ms 34684 KB Ok
24 Correct 280 ms 23036 KB Ok
25 Correct 298 ms 23192 KB Ok
26 Correct 280 ms 23872 KB Ok
27 Correct 356 ms 23800 KB Ok
28 Correct 306 ms 23192 KB Ok
29 Correct 285 ms 26868 KB Ok
30 Correct 301 ms 23596 KB Ok
31 Correct 309 ms 23176 KB Ok
32 Correct 347 ms 23084 KB Ok
33 Correct 303 ms 23644 KB Ok
34 Correct 579 ms 34804 KB Ok
35 Correct 374 ms 34864 KB Ok
36 Correct 511 ms 34932 KB Ok
37 Correct 413 ms 34868 KB Ok
38 Correct 389 ms 34740 KB Ok
39 Correct 545 ms 34712 KB Ok
40 Correct 455 ms 34788 KB Ok
41 Correct 412 ms 34744 KB Ok
42 Correct 609 ms 34836 KB Ok
43 Correct 397 ms 34796 KB Ok

Subtask #6
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 214 ms 34716 KB Ok
2 Correct 218 ms 34632 KB Ok
3 Correct 232 ms 23760 KB Ok
4 Correct 226 ms 24572 KB Ok
5 Correct 295 ms 23760 KB Ok
6 Correct 201 ms 25864 KB Ok
7 Correct 209 ms 23412 KB Ok
8 Correct 214 ms 25804 KB Ok
9 Correct 217 ms 23616 KB Ok
10 Correct 222 ms 28752 KB Ok
11 Correct 251 ms 23592 KB Ok
12 Correct 187 ms 23268 KB Ok
13 Correct 218 ms 34576 KB Ok
14 Correct 222 ms 34576 KB Ok
15 Correct 243 ms 34624 KB Ok
16 Correct 227 ms 34680 KB Ok
17 Correct 250 ms 34624 KB Ok
18 Correct 236 ms 34692 KB Ok
19 Correct 225 ms 35140 KB Ok
20 Correct 217 ms 34824 KB Ok
21 Correct 246 ms 35136 KB Ok
22 Correct 210 ms 34752 KB Ok
23 Correct 80 ms 34696 KB Ok
24 Correct 260 ms 34644 KB Ok
25 Correct 212 ms 34624 KB Ok
26 Correct 222 ms 34640 KB Ok
27 Correct 234 ms 34628 KB Ok
28 Correct 238 ms 34640 KB Ok
29 Correct 243 ms 34644 KB Ok
30 Correct 220 ms 34728 KB Ok
31 Correct 244 ms 34576 KB Ok
32 Correct 234 ms 34664 KB Ok
33 Correct 233 ms 34684 KB Ok
34 Correct 280 ms 23036 KB Ok
35 Correct 298 ms 23192 KB Ok
36 Correct 280 ms 23872 KB Ok
37 Correct 356 ms 23800 KB Ok
38 Correct 306 ms 23192 KB Ok
39 Correct 285 ms 26868 KB Ok
40 Correct 301 ms 23596 KB Ok
41 Correct 309 ms 23176 KB Ok
42 Correct 347 ms 23084 KB Ok
43 Correct 303 ms 23644 KB Ok
44 Correct 579 ms 34804 KB Ok
45 Correct 374 ms 34864 KB Ok
46 Correct 511 ms 34932 KB Ok
47 Correct 413 ms 34868 KB Ok
48 Correct 389 ms 34740 KB Ok
49 Correct 545 ms 34712 KB Ok
50 Correct 455 ms 34788 KB Ok
51 Correct 412 ms 34744 KB Ok
52 Correct 609 ms 34836 KB Ok
53 Correct 397 ms 34796 KB Ok
54 Correct 422 ms 26524 KB Ok
55 Correct 506 ms 26980 KB Ok
56 Correct 451 ms 26896 KB Ok
57 Correct 328 ms 26048 KB Ok
58 Correct 483 ms 26768 KB Ok
59 Correct 442 ms 26560 KB Ok
60 Correct 389 ms 26176 KB Ok
61 Correct 387 ms 26324 KB Ok
62 Correct 566 ms 27184 KB Ok
63 Correct 429 ms 26504 KB Ok
64 Correct 535 ms 26936 KB Ok
65 Correct 490 ms 26876 KB Ok
66 Correct 449 ms 26508 KB Ok
67 Correct 363 ms 26212 KB Ok
68 Correct 479 ms 26608 KB Ok
69 Execution timed out 2082 ms 38500 KB Time limit exceeded
70 Halted 0 ms 0 KB -

Subtask #7
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 214 ms 34716 KB Ok
2 Correct 218 ms 34632 KB Ok
3 Correct 232 ms 23760 KB Ok
4 Correct 226 ms 24572 KB Ok
5 Correct 295 ms 23760 KB Ok
6 Correct 201 ms 25864 KB Ok
7 Correct 209 ms 23412 KB Ok
8 Correct 214 ms 25804 KB Ok
9 Correct 217 ms 23616 KB Ok
10 Correct 222 ms 28752 KB Ok
11 Correct 251 ms 23592 KB Ok
12 Correct 187 ms 23268 KB Ok
13 Correct 218 ms 34576 KB Ok
14 Correct 222 ms 34576 KB Ok
15 Correct 243 ms 34624 KB Ok
16 Correct 227 ms 34680 KB Ok
17 Correct 250 ms 34624 KB Ok
18 Correct 236 ms 34692 KB Ok
19 Correct 225 ms 35140 KB Ok
20 Correct 217 ms 34824 KB Ok
21 Correct 246 ms 35136 KB Ok
22 Correct 210 ms 34752 KB Ok
23 Correct 80 ms 34696 KB Ok
24 Correct 260 ms 34644 KB Ok
25 Correct 212 ms 34624 KB Ok
26 Correct 222 ms 34640 KB Ok
27 Correct 234 ms 34628 KB Ok
28 Correct 238 ms 34640 KB Ok
29 Correct 243 ms 34644 KB Ok
30 Correct 220 ms 34728 KB Ok
31 Correct 244 ms 34576 KB Ok
32 Correct 234 ms 34664 KB Ok
33 Correct 233 ms 34684 KB Ok
34 Correct 243 ms 34628 KB Ok
35 Correct 235 ms 34648 KB Ok
36 Correct 294 ms 34676 KB Ok
37 Correct 277 ms 34628 KB Ok
38 Correct 318 ms 34680 KB Ok
39 Correct 633 ms 39908 KB Ok
40 Correct 577 ms 38680 KB Ok
41 Correct 933 ms 42164 KB Ok
42 Correct 724 ms 42592 KB Ok
43 Correct 492 ms 38516 KB Ok
44 Correct 776 ms 41088 KB Ok
45 Correct 280 ms 23036 KB Ok
46 Correct 298 ms 23192 KB Ok
47 Correct 280 ms 23872 KB Ok
48 Correct 356 ms 23800 KB Ok
49 Correct 306 ms 23192 KB Ok
50 Correct 285 ms 26868 KB Ok
51 Correct 301 ms 23596 KB Ok
52 Correct 309 ms 23176 KB Ok
53 Correct 347 ms 23084 KB Ok
54 Correct 303 ms 23644 KB Ok
55 Correct 579 ms 34804 KB Ok
56 Correct 374 ms 34864 KB Ok
57 Correct 511 ms 34932 KB Ok
58 Correct 413 ms 34868 KB Ok
59 Correct 389 ms 34740 KB Ok
60 Correct 545 ms 34712 KB Ok
61 Correct 455 ms 34788 KB Ok
62 Correct 412 ms 34744 KB Ok
63 Correct 609 ms 34836 KB Ok
64 Correct 397 ms 34796 KB Ok
65 Correct 422 ms 26524 KB Ok
66 Correct 506 ms 26980 KB Ok
67 Correct 451 ms 26896 KB Ok
68 Correct 328 ms 26048 KB Ok
69 Correct 483 ms 26768 KB Ok
70 Correct 442 ms 26560 KB Ok
71 Correct 389 ms 26176 KB Ok
72 Correct 387 ms 26324 KB Ok
73 Correct 566 ms 27184 KB Ok
74 Correct 429 ms 26504 KB Ok
75 Correct 535 ms 26936 KB Ok
76 Correct 490 ms 26876 KB Ok
77 Correct 449 ms 26508 KB Ok
78 Correct 363 ms 26212 KB Ok
79 Correct 479 ms 26608 KB Ok
80 Execution timed out 2082 ms 38500 KB Time limit exceeded
81 Halted 0 ms 0 KB -