oj.uz

Submission #960077

# Submission time Handle Problem Language Result Execution time Memory
960077 2024-04-09T15:43:04 Z penguin133 Building 4 (JOI20_building4) C++17
100 / 100
 315 ms 147248 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define fi first
#define se second
#define pi pair <int, int> 
#define pii pair <int, pi>

int n, A[1000005], B[1000005], memo[1000005][2], memo2[1000005][2];
int dp1(int x, int f){
	if(x == 2 * n)return !f;
	if(memo[x][f] != -1)return memo[x][f];
	int val = (!f ? A[x] : B[x]);
	int tmp = 1e18;
	if(A[x + 1] >= val)tmp = min(tmp, dp1(x + 1, 0));
	if(B[x + 1] >= val)tmp = min(tmp, dp1(x + 1, 1));
	if(!f)tmp++;
	return memo[x][f] = tmp;
}
int dp2(int x, int f){
	if(x == 2 * n)return !f;
	if(memo2[x][f] != -1)return memo2[x][f];
	int val = (!f ? A[x] : B[x]);
	int tmp = -1e18;
	if(A[x + 1] >= val)tmp = max(tmp, dp2(x + 1, 0));
	if(B[x + 1] >= val)tmp = max(tmp, dp2(x + 1, 1));
	if(!f)tmp++;
	return memo2[x][f] = tmp;
}

void solve(){
	cin >> n;
	for(int i = 1; i <= 2 * n; i++)cin >> A[i];
	for(int i = 1; i <= 2 * n; i++)cin >> B[i];
	memset(memo, -1, sizeof(memo));
	memset(memo2, -1, sizeof(memo2));
	string s;
	int cura = 0, curb = 0, prv = 0;
	for(int i = 1; i <= 2 * n; i++){
		int mn = dp1(i, 0), mx = dp2(i, 0);
		//cerr << mn << ' ' << mx << ' ';
		if(mn <= n - cura && mx >= n - cura && A[i] >= prv){
			s += 'A';
			cura++;
			prv = A[i];
		}
		else{
			mn = dp1(i, 1), mx = dp2(i, 1);
			//cerr << mn << ' ' << mx << ' ';
			if(mn <= n - cura && mx >= n - cura && B[i] >= prv){
				s += 'B';
				curb++;
				prv = B[i];
			}
			else{
				cout << -1 << '\n';
				return;
			}
		}
		//cerr << s << '\n';
	}
	cout << s;
}

main(){
	ios::sync_with_stdio(0);cin.tie(0);
	int tc = 1;
	//cin >> tc;
	while(tc--)solve();
}

Compilation message

building4.cpp:65:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   65 | main(){
      | ^~~~

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 35416 KB Output is correct
2 Correct 6 ms 35416 KB Output is correct
3 Correct 6 ms 35420 KB Output is correct
4 Correct 5 ms 35416 KB Output is correct
5 Correct 7 ms 37436 KB Output is correct
6 Correct 8 ms 37724 KB Output is correct
7 Correct 7 ms 35604 KB Output is correct
8 Correct 8 ms 35676 KB Output is correct
9 Correct 7 ms 35676 KB Output is correct
10 Correct 7 ms 35676 KB Output is correct
11 Correct 8 ms 37724 KB Output is correct
12 Correct 8 ms 37924 KB Output is correct
13 Correct 8 ms 37980 KB Output is correct
14 Correct 8 ms 37724 KB Output is correct
15 Correct 9 ms 37976 KB Output is correct
16 Correct 9 ms 37724 KB Output is correct
17 Correct 9 ms 37976 KB Output is correct
18 Correct 9 ms 37720 KB Output is correct
19 Correct 9 ms 37980 KB Output is correct
20 Correct 8 ms 37836 KB Output is correct
21 Correct 10 ms 37976 KB Output is correct
22 Correct 9 ms 37720 KB Output is correct
23 Correct 9 ms 37724 KB Output is correct
24 Correct 8 ms 37920 KB Output is correct
25 Correct 9 ms 37720 KB Output is correct
26 Correct 8 ms 37788 KB Output is correct
27 Correct 9 ms 37724 KB Output is correct
28 Correct 9 ms 37652 KB Output is correct
29 Correct 9 ms 37724 KB Output is correct
30 Correct 9 ms 37860 KB Output is correct
31 Correct 9 ms 37724 KB Output is correct
32 Correct 8 ms 35676 KB Output is correct
33 Correct 9 ms 37720 KB Output is correct

Subtask #2
89.0 / 89.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 35416 KB Output is correct
2 Correct 6 ms 35416 KB Output is correct
3 Correct 6 ms 35420 KB Output is correct
4 Correct 5 ms 35416 KB Output is correct
5 Correct 7 ms 37436 KB Output is correct
6 Correct 8 ms 37724 KB Output is correct
7 Correct 7 ms 35604 KB Output is correct
8 Correct 8 ms 35676 KB Output is correct
9 Correct 7 ms 35676 KB Output is correct
10 Correct 7 ms 35676 KB Output is correct
11 Correct 8 ms 37724 KB Output is correct
12 Correct 8 ms 37924 KB Output is correct
13 Correct 8 ms 37980 KB Output is correct
14 Correct 8 ms 37724 KB Output is correct
15 Correct 9 ms 37976 KB Output is correct
16 Correct 9 ms 37724 KB Output is correct
17 Correct 9 ms 37976 KB Output is correct
18 Correct 9 ms 37720 KB Output is correct
19 Correct 9 ms 37980 KB Output is correct
20 Correct 8 ms 37836 KB Output is correct
21 Correct 10 ms 37976 KB Output is correct
22 Correct 9 ms 37720 KB Output is correct
23 Correct 9 ms 37724 KB Output is correct
24 Correct 8 ms 37920 KB Output is correct
25 Correct 9 ms 37720 KB Output is correct
26 Correct 8 ms 37788 KB Output is correct
27 Correct 9 ms 37724 KB Output is correct
28 Correct 9 ms 37652 KB Output is correct
29 Correct 9 ms 37724 KB Output is correct
30 Correct 9 ms 37860 KB Output is correct
31 Correct 9 ms 37724 KB Output is correct
32 Correct 8 ms 35676 KB Output is correct
33 Correct 9 ms 37720 KB Output is correct
34 Correct 153 ms 66212 KB Output is correct
35 Correct 250 ms 139264 KB Output is correct
36 Correct 258 ms 137488 KB Output is correct
37 Correct 249 ms 139536 KB Output is correct
38 Correct 268 ms 139896 KB Output is correct
39 Correct 263 ms 138812 KB Output is correct
40 Correct 312 ms 146088 KB Output is correct
41 Correct 306 ms 141072 KB Output is correct
42 Correct 276 ms 143608 KB Output is correct
43 Correct 277 ms 147016 KB Output is correct
44 Correct 282 ms 147020 KB Output is correct
45 Correct 274 ms 147016 KB Output is correct
46 Correct 263 ms 147016 KB Output is correct
47 Correct 283 ms 146280 KB Output is correct
48 Correct 260 ms 141616 KB Output is correct
49 Correct 270 ms 146756 KB Output is correct
50 Correct 267 ms 146260 KB Output is correct
51 Correct 270 ms 146196 KB Output is correct
52 Correct 232 ms 135244 KB Output is correct
53 Correct 218 ms 135348 KB Output is correct
54 Correct 212 ms 135440 KB Output is correct
55 Correct 211 ms 134988 KB Output is correct
56 Correct 315 ms 147248 KB Output is correct
57 Correct 262 ms 141948 KB Output is correct
58 Correct 259 ms 142152 KB Output is correct
59 Correct 252 ms 142164 KB Output is correct
60 Correct 228 ms 136296 KB Output is correct
61 Correct 270 ms 142664 KB Output is correct
62 Correct 232 ms 141244 KB Output is correct
63 Correct 280 ms 142608 KB Output is correct
64 Correct 242 ms 139256 KB Output is correct
65 Correct 251 ms 142768 KB Output is correct