oj.uz

Submission #516367

# Submission time Handle Problem Language Result Execution time Memory
516367 2022-01-21T08:35:48 Z hohohaha Nice sequence (IZhO18_sequence) C++14
100 / 100
 1152 ms 51000 KB 
#include "bits/stdc++.h"
#define int long long

using namespace std;

#define li long long
#define ld long double
#define ii pair<int, int>
#define vi vector<int> 
#define vvi vector<vi>


#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define pf push_front
#define eb emplace_back
#define em emplace
#define ob pop_back
#define om pop
#define of pop_front

#define fori(i, a, b) for(int i = (int) (a); i <= (int) (b); ++i)
#define ford(i, a, b) for(int i = (int) (a); i >= (int) (b); --i)

#define all(x) begin(x), end(x)
#define sz(x) ((int)(x).size())
#define bitc __builtin_popcountll

mt19937 rng(uint64_t(new char));
#define rand rng
#define endl '\n'
#define sp ' '

#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

void solve();

signed main() {
//	#ifdef GIAPVU
//		freopen("test.inp","r",stdin);
//		freopen("test.out","w",stdout);
//	#endif
	fastio; 
   	int tc = 1;
   	cin >> tc; 
   	fori(test, 1, tc) {
      solve();
   	}
   	return 0;
}
#define int long long
const int inf = LLONG_MAX / 100ll, mod = 1000000007 ;

const int maxn = 1e6 + 5, itsize = maxn << 1, maxit = maxn << 3, mapping = maxn; 
int n, m; 
int vs[maxn]; int ptr = 0; 
void toposort(int i, int len) { 
	vs[i] = 1; 
	if(i - m >= 0 and !vs[i - m]) {
		toposort(i - m, len);
	}
	if(i + n <= len and !vs[i + n]) { 
		toposort(i + n, len); 
	}
	vs[i] = ++ptr; 
}
bool build(int len); 
bool build(int len) { 
	fill(vs, vs + len + 1, 0); ptr = 0; 
	fori(i, 0, len) { 
		if(!vs[i]) toposort(i, len);
	}
	fori(i, 0, len) { 
		if(i - m >= 0 and vs[i] <= vs[i - m]) return 0; 
		if(i + n <= len and vs[i] <= vs[i + n]) return 0; 
	}
	return 1; 
}
void solve() {
	cin >> n >> m;
	int lo = 0, hi = n + m; 
	while(lo < hi) { 
		int mi = lo + hi + 1 >> 1; 
//		cout << "mi:" << mi << endl;
		if(build(mi)) lo = mi; 
		else hi = mi - 1; 
	}
	build(lo);
	cout << lo << endl; 
	fori(i,1,lo) { 
		cout << vs[i] - vs[i - 1] << sp; 
	} 
	cout << endl; 
}

Compilation message

sequence.cpp: In function 'void solve()':
sequence.cpp:85:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   85 |   int mi = lo + hi + 1 >> 1;
      |            ~~~~~~~~^~~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Ok
2 Correct 0 ms 204 KB Ok
3 Correct 1 ms 328 KB Ok
4 Correct 0 ms 324 KB Ok
5 Correct 0 ms 204 KB Ok
6 Correct 0 ms 332 KB Ok
7 Correct 1 ms 204 KB Ok
8 Correct 1 ms 308 KB Ok
9 Correct 1 ms 204 KB Ok
10 Correct 1 ms 204 KB Ok
11 Correct 1 ms 204 KB Ok
12 Correct 1 ms 204 KB Ok

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Ok
2 Correct 0 ms 328 KB Ok
3 Correct 1 ms 332 KB Ok
4 Correct 0 ms 204 KB Ok
5 Correct 0 ms 204 KB Ok
6 Correct 3 ms 460 KB Ok
7 Correct 14 ms 1096 KB Ok
8 Correct 6 ms 716 KB Ok
9 Correct 15 ms 1224 KB Ok
10 Correct 9 ms 844 KB Ok

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Ok
2 Correct 0 ms 204 KB Ok
3 Correct 0 ms 204 KB Ok
4 Correct 0 ms 204 KB Ok
5 Correct 0 ms 204 KB Ok
6 Correct 0 ms 204 KB Ok
7 Correct 0 ms 204 KB Ok
8 Correct 0 ms 204 KB Ok
9 Correct 0 ms 276 KB Ok
10 Correct 1 ms 204 KB Ok
11 Correct 0 ms 332 KB Ok

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Ok
2 Correct 0 ms 204 KB Ok
3 Correct 0 ms 204 KB Ok
4 Correct 0 ms 204 KB Ok
5 Correct 1 ms 204 KB Ok
6 Correct 156 ms 12040 KB Ok
7 Correct 173 ms 13280 KB Ok
8 Correct 337 ms 15916 KB Ok
9 Correct 208 ms 14084 KB Ok
10 Correct 108 ms 7160 KB Ok
11 Correct 171 ms 14616 KB Ok

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Ok
2 Correct 0 ms 204 KB Ok
3 Correct 1 ms 328 KB Ok
4 Correct 0 ms 324 KB Ok
5 Correct 0 ms 204 KB Ok
6 Correct 0 ms 332 KB Ok
7 Correct 1 ms 204 KB Ok
8 Correct 1 ms 308 KB Ok
9 Correct 1 ms 204 KB Ok
10 Correct 1 ms 204 KB Ok
11 Correct 1 ms 204 KB Ok
12 Correct 1 ms 204 KB Ok
13 Correct 1 ms 204 KB Ok
14 Correct 0 ms 204 KB Ok
15 Correct 0 ms 204 KB Ok
16 Correct 0 ms 204 KB Ok
17 Correct 0 ms 204 KB Ok
18 Correct 0 ms 204 KB Ok
19 Correct 0 ms 204 KB Ok
20 Correct 0 ms 204 KB Ok
21 Correct 0 ms 276 KB Ok
22 Correct 1 ms 204 KB Ok
23 Correct 0 ms 332 KB Ok
24 Correct 4 ms 320 KB Ok
25 Correct 2 ms 348 KB Ok
26 Correct 3 ms 332 KB Ok
27 Correct 3 ms 320 KB Ok
28 Correct 3 ms 308 KB Ok
29 Correct 2 ms 336 KB Ok
30 Correct 2 ms 332 KB Ok
31 Correct 2 ms 332 KB Ok
32 Correct 3 ms 328 KB Ok
33 Correct 3 ms 324 KB Ok
34 Correct 6 ms 596 KB Ok
35 Correct 6 ms 588 KB Ok
36 Correct 7 ms 588 KB Ok
37 Correct 6 ms 580 KB Ok
38 Correct 7 ms 576 KB Ok
39 Correct 6 ms 660 KB Ok
40 Correct 6 ms 588 KB Ok
41 Correct 5 ms 588 KB Ok
42 Correct 6 ms 588 KB Ok
43 Correct 7 ms 588 KB Ok

Subtask #6
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Ok
2 Correct 0 ms 204 KB Ok
3 Correct 1 ms 328 KB Ok
4 Correct 0 ms 324 KB Ok
5 Correct 0 ms 204 KB Ok
6 Correct 0 ms 332 KB Ok
7 Correct 1 ms 204 KB Ok
8 Correct 1 ms 308 KB Ok
9 Correct 1 ms 204 KB Ok
10 Correct 1 ms 204 KB Ok
11 Correct 1 ms 204 KB Ok
12 Correct 1 ms 204 KB Ok
13 Correct 0 ms 204 KB Ok
14 Correct 0 ms 328 KB Ok
15 Correct 1 ms 332 KB Ok
16 Correct 0 ms 204 KB Ok
17 Correct 0 ms 204 KB Ok
18 Correct 3 ms 460 KB Ok
19 Correct 14 ms 1096 KB Ok
20 Correct 6 ms 716 KB Ok
21 Correct 15 ms 1224 KB Ok
22 Correct 9 ms 844 KB Ok
23 Correct 1 ms 204 KB Ok
24 Correct 0 ms 204 KB Ok
25 Correct 0 ms 204 KB Ok
26 Correct 0 ms 204 KB Ok
27 Correct 0 ms 204 KB Ok
28 Correct 0 ms 204 KB Ok
29 Correct 0 ms 204 KB Ok
30 Correct 0 ms 204 KB Ok
31 Correct 0 ms 276 KB Ok
32 Correct 1 ms 204 KB Ok
33 Correct 0 ms 332 KB Ok
34 Correct 4 ms 320 KB Ok
35 Correct 2 ms 348 KB Ok
36 Correct 3 ms 332 KB Ok
37 Correct 3 ms 320 KB Ok
38 Correct 3 ms 308 KB Ok
39 Correct 2 ms 336 KB Ok
40 Correct 2 ms 332 KB Ok
41 Correct 2 ms 332 KB Ok
42 Correct 3 ms 328 KB Ok
43 Correct 3 ms 324 KB Ok
44 Correct 6 ms 596 KB Ok
45 Correct 6 ms 588 KB Ok
46 Correct 7 ms 588 KB Ok
47 Correct 6 ms 580 KB Ok
48 Correct 7 ms 576 KB Ok
49 Correct 6 ms 660 KB Ok
50 Correct 6 ms 588 KB Ok
51 Correct 5 ms 588 KB Ok
52 Correct 6 ms 588 KB Ok
53 Correct 7 ms 588 KB Ok
54 Correct 114 ms 2636 KB Ok
55 Correct 134 ms 3016 KB Ok
56 Correct 131 ms 3012 KB Ok
57 Correct 100 ms 2288 KB Ok
58 Correct 107 ms 2504 KB Ok
59 Correct 102 ms 2292 KB Ok
60 Correct 89 ms 2156 KB Ok
61 Correct 97 ms 2316 KB Ok
62 Correct 130 ms 2756 KB Ok
63 Correct 107 ms 2340 KB Ok
64 Correct 144 ms 3032 KB Ok
65 Correct 115 ms 2612 KB Ok
66 Correct 101 ms 2384 KB Ok
67 Correct 94 ms 2352 KB Ok
68 Correct 102 ms 2572 KB Ok
69 Correct 233 ms 11768 KB Ok
70 Correct 240 ms 12240 KB Ok
71 Correct 225 ms 11844 KB Ok
72 Correct 231 ms 11588 KB Ok
73 Correct 219 ms 11868 KB Ok
74 Correct 222 ms 11588 KB Ok
75 Correct 235 ms 11184 KB Ok
76 Correct 238 ms 12280 KB Ok
77 Correct 219 ms 11252 KB Ok
78 Correct 221 ms 11716 KB Ok
79 Correct 230 ms 11948 KB Ok
80 Correct 230 ms 11996 KB Ok
81 Correct 237 ms 11884 KB Ok
82 Correct 225 ms 11844 KB Ok
83 Correct 213 ms 11272 KB Ok

Subtask #7
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Ok
2 Correct 0 ms 204 KB Ok
3 Correct 1 ms 328 KB Ok
4 Correct 0 ms 324 KB Ok
5 Correct 0 ms 204 KB Ok
6 Correct 0 ms 332 KB Ok
7 Correct 1 ms 204 KB Ok
8 Correct 1 ms 308 KB Ok
9 Correct 1 ms 204 KB Ok
10 Correct 1 ms 204 KB Ok
11 Correct 1 ms 204 KB Ok
12 Correct 1 ms 204 KB Ok
13 Correct 0 ms 204 KB Ok
14 Correct 0 ms 328 KB Ok
15 Correct 1 ms 332 KB Ok
16 Correct 0 ms 204 KB Ok
17 Correct 0 ms 204 KB Ok
18 Correct 3 ms 460 KB Ok
19 Correct 14 ms 1096 KB Ok
20 Correct 6 ms 716 KB Ok
21 Correct 15 ms 1224 KB Ok
22 Correct 9 ms 844 KB Ok
23 Correct 1 ms 204 KB Ok
24 Correct 0 ms 204 KB Ok
25 Correct 0 ms 204 KB Ok
26 Correct 0 ms 204 KB Ok
27 Correct 0 ms 204 KB Ok
28 Correct 0 ms 204 KB Ok
29 Correct 0 ms 204 KB Ok
30 Correct 0 ms 204 KB Ok
31 Correct 0 ms 276 KB Ok
32 Correct 1 ms 204 KB Ok
33 Correct 0 ms 332 KB Ok
34 Correct 1 ms 204 KB Ok
35 Correct 0 ms 204 KB Ok
36 Correct 0 ms 204 KB Ok
37 Correct 0 ms 204 KB Ok
38 Correct 1 ms 204 KB Ok
39 Correct 156 ms 12040 KB Ok
40 Correct 173 ms 13280 KB Ok
41 Correct 337 ms 15916 KB Ok
42 Correct 208 ms 14084 KB Ok
43 Correct 108 ms 7160 KB Ok
44 Correct 171 ms 14616 KB Ok
45 Correct 4 ms 320 KB Ok
46 Correct 2 ms 348 KB Ok
47 Correct 3 ms 332 KB Ok
48 Correct 3 ms 320 KB Ok
49 Correct 3 ms 308 KB Ok
50 Correct 2 ms 336 KB Ok
51 Correct 2 ms 332 KB Ok
52 Correct 2 ms 332 KB Ok
53 Correct 3 ms 328 KB Ok
54 Correct 3 ms 324 KB Ok
55 Correct 6 ms 596 KB Ok
56 Correct 6 ms 588 KB Ok
57 Correct 7 ms 588 KB Ok
58 Correct 6 ms 580 KB Ok
59 Correct 7 ms 576 KB Ok
60 Correct 6 ms 660 KB Ok
61 Correct 6 ms 588 KB Ok
62 Correct 5 ms 588 KB Ok
63 Correct 6 ms 588 KB Ok
64 Correct 7 ms 588 KB Ok
65 Correct 114 ms 2636 KB Ok
66 Correct 134 ms 3016 KB Ok
67 Correct 131 ms 3012 KB Ok
68 Correct 100 ms 2288 KB Ok
69 Correct 107 ms 2504 KB Ok
70 Correct 102 ms 2292 KB Ok
71 Correct 89 ms 2156 KB Ok
72 Correct 97 ms 2316 KB Ok
73 Correct 130 ms 2756 KB Ok
74 Correct 107 ms 2340 KB Ok
75 Correct 144 ms 3032 KB Ok
76 Correct 115 ms 2612 KB Ok
77 Correct 101 ms 2384 KB Ok
78 Correct 94 ms 2352 KB Ok
79 Correct 102 ms 2572 KB Ok
80 Correct 233 ms 11768 KB Ok
81 Correct 240 ms 12240 KB Ok
82 Correct 225 ms 11844 KB Ok
83 Correct 231 ms 11588 KB Ok
84 Correct 219 ms 11868 KB Ok
85 Correct 222 ms 11588 KB Ok
86 Correct 235 ms 11184 KB Ok
87 Correct 238 ms 12280 KB Ok
88 Correct 219 ms 11252 KB Ok
89 Correct 221 ms 11716 KB Ok
90 Correct 230 ms 11948 KB Ok
91 Correct 230 ms 11996 KB Ok
92 Correct 237 ms 11884 KB Ok
93 Correct 225 ms 11844 KB Ok
94 Correct 213 ms 11272 KB Ok
95 Correct 277 ms 6452 KB Ok
96 Correct 411 ms 8772 KB Ok
97 Correct 396 ms 7776 KB Ok
98 Correct 281 ms 6680 KB Ok
99 Correct 366 ms 7100 KB Ok
100 Correct 364 ms 7236 KB Ok
101 Correct 358 ms 7748 KB Ok
102 Correct 360 ms 7556 KB Ok
103 Correct 357 ms 7616 KB Ok
104 Correct 434 ms 8856 KB Ok
105 Correct 408 ms 8732 KB Ok
106 Correct 357 ms 8260 KB Ok
107 Correct 386 ms 8260 KB Ok
108 Correct 435 ms 8980 KB Ok
109 Correct 396 ms 8764 KB Ok
110 Correct 1114 ms 47144 KB Ok
111 Correct 1101 ms 50012 KB Ok
112 Correct 1095 ms 49776 KB Ok
113 Correct 1111 ms 49152 KB Ok
114 Correct 1118 ms 51000 KB Ok
115 Correct 1084 ms 48724 KB Ok
116 Correct 1115 ms 50156 KB Ok
117 Correct 1152 ms 48732 KB Ok
118 Correct 1059 ms 48824 KB Ok
119 Correct 1069 ms 48744 KB Ok
120 Correct 1059 ms 48492 KB Ok
121 Correct 1054 ms 47160 KB Ok
122 Correct 1053 ms 49632 KB Ok
123 Correct 1080 ms 49992 KB Ok
124 Correct 1087 ms 47440 KB Ok
125 Correct 1144 ms 32224 KB Ok