oj.uz

Submission #496057

# Submission time Handle Problem Language Result Execution time Memory
496057 2021-12-20T13:48:09 Z mansur Nice sequence (IZhO18_sequence) C++17
100 / 100
 1719 ms 52548 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> was(N + 7), pref(N + 7), ans, cur, tp;

int n, m;

bool c;

void dfs(int u, int len) {
 	was[u] = 2;
 	if (u - n >= 0) {
 		if (was[u - n] == 2) c = 1;
 		else if (!was[u - n]) dfs(u - n, len);
 	}
 	if (u + m <= len) {
 		if (was[u + m] == 2) c = 1;
 		else if (!was[u + m]) dfs(u + m, len);
 	}
    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--) {
		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;
			}
			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:72:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   72 | main() {
      | ^~~~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 10820 KB Ok
2 Correct 59 ms 10752 KB Ok
3 Correct 43 ms 4716 KB Ok
4 Correct 42 ms 5184 KB Ok
5 Correct 50 ms 4808 KB Ok
6 Correct 44 ms 5920 KB Ok
7 Correct 52 ms 4684 KB Ok
8 Correct 46 ms 6136 KB Ok
9 Correct 41 ms 4728 KB Ok
10 Correct 44 ms 7360 KB Ok
11 Correct 43 ms 4684 KB Ok
12 Correct 42 ms 4676 KB Ok

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 10568 KB Ok
2 Correct 51 ms 10564 KB Ok
3 Correct 61 ms 10676 KB Ok
4 Correct 60 ms 10516 KB Ok
5 Correct 51 ms 10568 KB Ok
6 Correct 72 ms 10828 KB Ok
7 Correct 109 ms 10928 KB Ok
8 Correct 60 ms 10828 KB Ok
9 Correct 79 ms 11072 KB Ok
10 Correct 76 ms 10804 KB Ok

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 10736 KB Ok
2 Correct 74 ms 10836 KB Ok
3 Correct 60 ms 10488 KB Ok
4 Correct 77 ms 10880 KB Ok
5 Correct 76 ms 10828 KB Ok
6 Correct 62 ms 10592 KB Ok
7 Correct 60 ms 10880 KB Ok
8 Correct 68 ms 10880 KB Ok
9 Correct 67 ms 10556 KB Ok
10 Correct 68 ms 10560 KB Ok
11 Correct 67 ms 10560 KB Ok

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 10828 KB Ok
2 Correct 72 ms 10828 KB Ok
3 Correct 78 ms 10828 KB Ok
4 Correct 71 ms 10768 KB Ok
5 Correct 73 ms 10880 KB Ok
6 Correct 323 ms 15860 KB Ok
7 Correct 286 ms 14952 KB Ok
8 Correct 525 ms 17784 KB Ok
9 Correct 413 ms 18636 KB Ok
10 Correct 275 ms 14640 KB Ok
11 Correct 450 ms 17076 KB Ok

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 10820 KB Ok
2 Correct 59 ms 10752 KB Ok
3 Correct 43 ms 4716 KB Ok
4 Correct 42 ms 5184 KB Ok
5 Correct 50 ms 4808 KB Ok
6 Correct 44 ms 5920 KB Ok
7 Correct 52 ms 4684 KB Ok
8 Correct 46 ms 6136 KB Ok
9 Correct 41 ms 4728 KB Ok
10 Correct 44 ms 7360 KB Ok
11 Correct 43 ms 4684 KB Ok
12 Correct 42 ms 4676 KB Ok
13 Correct 20 ms 10736 KB Ok
14 Correct 74 ms 10836 KB Ok
15 Correct 60 ms 10488 KB Ok
16 Correct 77 ms 10880 KB Ok
17 Correct 76 ms 10828 KB Ok
18 Correct 62 ms 10592 KB Ok
19 Correct 60 ms 10880 KB Ok
20 Correct 68 ms 10880 KB Ok
21 Correct 67 ms 10556 KB Ok
22 Correct 68 ms 10560 KB Ok
23 Correct 67 ms 10560 KB Ok
24 Correct 49 ms 4556 KB Ok
25 Correct 47 ms 4556 KB Ok
26 Correct 50 ms 4992 KB Ok
27 Correct 53 ms 4940 KB Ok
28 Correct 48 ms 4556 KB Ok
29 Correct 44 ms 6456 KB Ok
30 Correct 44 ms 4864 KB Ok
31 Correct 53 ms 4556 KB Ok
32 Correct 54 ms 4608 KB Ok
33 Correct 62 ms 4640 KB Ok
34 Correct 83 ms 10744 KB Ok
35 Correct 102 ms 10748 KB Ok
36 Correct 70 ms 10828 KB Ok
37 Correct 79 ms 10700 KB Ok
38 Correct 72 ms 10688 KB Ok
39 Correct 78 ms 10676 KB Ok
40 Correct 86 ms 10760 KB Ok
41 Correct 77 ms 10828 KB Ok
42 Correct 75 ms 10728 KB Ok
43 Correct 77 ms 10828 KB Ok

Subtask #6
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 10820 KB Ok
2 Correct 59 ms 10752 KB Ok
3 Correct 43 ms 4716 KB Ok
4 Correct 42 ms 5184 KB Ok
5 Correct 50 ms 4808 KB Ok
6 Correct 44 ms 5920 KB Ok
7 Correct 52 ms 4684 KB Ok
8 Correct 46 ms 6136 KB Ok
9 Correct 41 ms 4728 KB Ok
10 Correct 44 ms 7360 KB Ok
11 Correct 43 ms 4684 KB Ok
12 Correct 42 ms 4676 KB Ok
13 Correct 66 ms 10568 KB Ok
14 Correct 51 ms 10564 KB Ok
15 Correct 61 ms 10676 KB Ok
16 Correct 60 ms 10516 KB Ok
17 Correct 51 ms 10568 KB Ok
18 Correct 72 ms 10828 KB Ok
19 Correct 109 ms 10928 KB Ok
20 Correct 60 ms 10828 KB Ok
21 Correct 79 ms 11072 KB Ok
22 Correct 76 ms 10804 KB Ok
23 Correct 20 ms 10736 KB Ok
24 Correct 74 ms 10836 KB Ok
25 Correct 60 ms 10488 KB Ok
26 Correct 77 ms 10880 KB Ok
27 Correct 76 ms 10828 KB Ok
28 Correct 62 ms 10592 KB Ok
29 Correct 60 ms 10880 KB Ok
30 Correct 68 ms 10880 KB Ok
31 Correct 67 ms 10556 KB Ok
32 Correct 68 ms 10560 KB Ok
33 Correct 67 ms 10560 KB Ok
34 Correct 49 ms 4556 KB Ok
35 Correct 47 ms 4556 KB Ok
36 Correct 50 ms 4992 KB Ok
37 Correct 53 ms 4940 KB Ok
38 Correct 48 ms 4556 KB Ok
39 Correct 44 ms 6456 KB Ok
40 Correct 44 ms 4864 KB Ok
41 Correct 53 ms 4556 KB Ok
42 Correct 54 ms 4608 KB Ok
43 Correct 62 ms 4640 KB Ok
44 Correct 83 ms 10744 KB Ok
45 Correct 102 ms 10748 KB Ok
46 Correct 70 ms 10828 KB Ok
47 Correct 79 ms 10700 KB Ok
48 Correct 72 ms 10688 KB Ok
49 Correct 78 ms 10676 KB Ok
50 Correct 86 ms 10760 KB Ok
51 Correct 77 ms 10828 KB Ok
52 Correct 75 ms 10728 KB Ok
53 Correct 77 ms 10828 KB Ok
54 Correct 242 ms 7544 KB Ok
55 Correct 261 ms 8216 KB Ok
56 Correct 234 ms 7948 KB Ok
57 Correct 186 ms 7104 KB Ok
58 Correct 225 ms 7836 KB Ok
59 Correct 225 ms 7904 KB Ok
60 Correct 181 ms 7360 KB Ok
61 Correct 185 ms 7376 KB Ok
62 Correct 239 ms 8384 KB Ok
63 Correct 200 ms 7560 KB Ok
64 Correct 243 ms 8076 KB Ok
65 Correct 252 ms 7924 KB Ok
66 Correct 208 ms 7740 KB Ok
67 Correct 190 ms 7300 KB Ok
68 Correct 219 ms 7776 KB Ok
69 Correct 433 ms 17876 KB Ok
70 Correct 406 ms 18316 KB Ok
71 Correct 397 ms 18020 KB Ok
72 Correct 417 ms 17716 KB Ok
73 Correct 411 ms 18160 KB Ok
74 Correct 412 ms 17752 KB Ok
75 Correct 423 ms 17908 KB Ok
76 Correct 452 ms 18024 KB Ok
77 Correct 397 ms 17736 KB Ok
78 Correct 423 ms 17820 KB Ok
79 Correct 409 ms 18288 KB Ok
80 Correct 456 ms 17796 KB Ok
81 Correct 415 ms 18140 KB Ok
82 Correct 442 ms 17912 KB Ok
83 Correct 443 ms 17960 KB Ok

Subtask #7
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 10820 KB Ok
2 Correct 59 ms 10752 KB Ok
3 Correct 43 ms 4716 KB Ok
4 Correct 42 ms 5184 KB Ok
5 Correct 50 ms 4808 KB Ok
6 Correct 44 ms 5920 KB Ok
7 Correct 52 ms 4684 KB Ok
8 Correct 46 ms 6136 KB Ok
9 Correct 41 ms 4728 KB Ok
10 Correct 44 ms 7360 KB Ok
11 Correct 43 ms 4684 KB Ok
12 Correct 42 ms 4676 KB Ok
13 Correct 66 ms 10568 KB Ok
14 Correct 51 ms 10564 KB Ok
15 Correct 61 ms 10676 KB Ok
16 Correct 60 ms 10516 KB Ok
17 Correct 51 ms 10568 KB Ok
18 Correct 72 ms 10828 KB Ok
19 Correct 109 ms 10928 KB Ok
20 Correct 60 ms 10828 KB Ok
21 Correct 79 ms 11072 KB Ok
22 Correct 76 ms 10804 KB Ok
23 Correct 20 ms 10736 KB Ok
24 Correct 74 ms 10836 KB Ok
25 Correct 60 ms 10488 KB Ok
26 Correct 77 ms 10880 KB Ok
27 Correct 76 ms 10828 KB Ok
28 Correct 62 ms 10592 KB Ok
29 Correct 60 ms 10880 KB Ok
30 Correct 68 ms 10880 KB Ok
31 Correct 67 ms 10556 KB Ok
32 Correct 68 ms 10560 KB Ok
33 Correct 67 ms 10560 KB Ok
34 Correct 63 ms 10828 KB Ok
35 Correct 72 ms 10828 KB Ok
36 Correct 78 ms 10828 KB Ok
37 Correct 71 ms 10768 KB Ok
38 Correct 73 ms 10880 KB Ok
39 Correct 323 ms 15860 KB Ok
40 Correct 286 ms 14952 KB Ok
41 Correct 525 ms 17784 KB Ok
42 Correct 413 ms 18636 KB Ok
43 Correct 275 ms 14640 KB Ok
44 Correct 450 ms 17076 KB Ok
45 Correct 49 ms 4556 KB Ok
46 Correct 47 ms 4556 KB Ok
47 Correct 50 ms 4992 KB Ok
48 Correct 53 ms 4940 KB Ok
49 Correct 48 ms 4556 KB Ok
50 Correct 44 ms 6456 KB Ok
51 Correct 44 ms 4864 KB Ok
52 Correct 53 ms 4556 KB Ok
53 Correct 54 ms 4608 KB Ok
54 Correct 62 ms 4640 KB Ok
55 Correct 83 ms 10744 KB Ok
56 Correct 102 ms 10748 KB Ok
57 Correct 70 ms 10828 KB Ok
58 Correct 79 ms 10700 KB Ok
59 Correct 72 ms 10688 KB Ok
60 Correct 78 ms 10676 KB Ok
61 Correct 86 ms 10760 KB Ok
62 Correct 77 ms 10828 KB Ok
63 Correct 75 ms 10728 KB Ok
64 Correct 77 ms 10828 KB Ok
65 Correct 242 ms 7544 KB Ok
66 Correct 261 ms 8216 KB Ok
67 Correct 234 ms 7948 KB Ok
68 Correct 186 ms 7104 KB Ok
69 Correct 225 ms 7836 KB Ok
70 Correct 225 ms 7904 KB Ok
71 Correct 181 ms 7360 KB Ok
72 Correct 185 ms 7376 KB Ok
73 Correct 239 ms 8384 KB Ok
74 Correct 200 ms 7560 KB Ok
75 Correct 243 ms 8076 KB Ok
76 Correct 252 ms 7924 KB Ok
77 Correct 208 ms 7740 KB Ok
78 Correct 190 ms 7300 KB Ok
79 Correct 219 ms 7776 KB Ok
80 Correct 433 ms 17876 KB Ok
81 Correct 406 ms 18316 KB Ok
82 Correct 397 ms 18020 KB Ok
83 Correct 417 ms 17716 KB Ok
84 Correct 411 ms 18160 KB Ok
85 Correct 412 ms 17752 KB Ok
86 Correct 423 ms 17908 KB Ok
87 Correct 452 ms 18024 KB Ok
88 Correct 397 ms 17736 KB Ok
89 Correct 423 ms 17820 KB Ok
90 Correct 409 ms 18288 KB Ok
91 Correct 456 ms 17796 KB Ok
92 Correct 415 ms 18140 KB Ok
93 Correct 442 ms 17912 KB Ok
94 Correct 443 ms 17960 KB Ok
95 Correct 492 ms 13532 KB Ok
96 Correct 729 ms 16872 KB Ok
97 Correct 718 ms 15728 KB Ok
98 Correct 565 ms 14260 KB Ok
99 Correct 652 ms 15364 KB Ok
100 Correct 677 ms 15852 KB Ok
101 Correct 625 ms 16272 KB Ok
102 Correct 606 ms 15352 KB Ok
103 Correct 623 ms 16276 KB Ok
104 Correct 750 ms 16968 KB Ok
105 Correct 701 ms 17820 KB Ok
106 Correct 550 ms 15632 KB Ok
107 Correct 635 ms 16820 KB Ok
108 Correct 693 ms 18396 KB Ok
109 Correct 600 ms 16932 KB Ok
110 Correct 1529 ms 50032 KB Ok
111 Correct 1686 ms 48648 KB Ok
112 Correct 1569 ms 52028 KB Ok
113 Correct 1612 ms 48916 KB Ok
114 Correct 1643 ms 52424 KB Ok
115 Correct 1681 ms 51640 KB Ok
116 Correct 1584 ms 52164 KB Ok
117 Correct 1555 ms 50872 KB Ok
118 Correct 1554 ms 52548 KB Ok
119 Correct 1674 ms 49236 KB Ok
120 Correct 1625 ms 48404 KB Ok
121 Correct 1553 ms 47832 KB Ok
122 Correct 1639 ms 48464 KB Ok
123 Correct 1657 ms 51736 KB Ok
124 Correct 1515 ms 52228 KB Ok
125 Correct 1719 ms 33092 KB Ok