Submission #960077

#	Time	Username	Problem	Language	Result	Execution time	Memory
960077		penguin133	Building 4 (JOI20_building4)	C++17	100 / 100	315 ms	147248 KiB

building4

#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 (stderr)

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

• Subtask 1: 11 / 11
• Subtask 2: 89 / 89