Submission #234980

#	Time	Username	Problem	Language	Result	Execution time	Memory
234980		AMO5	Building 4 (JOI20_building4)	C++98	0 / 100	14 ms	16128 KiB

building4

#include <bits/stdc++.h>

using namespace std;

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define all(x) (x).begin(), (x).end() 
#define MOD 1000000007

typedef long long ll;
typedef pair <int, int> ii;
typedef pair <ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef long double ld;

ll INF=LLONG_MAX;

int const mxn = 1e6+5;
int dp[mxn][2][2]; //pos, cur, last
int a[mxn],b[mxn];

void maxs(int &a, int b){
	a=max(a,b);
	return;
}

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    //freopen("input.txt","r",stdin); freopen("output.txt","w",stdout);
	int n; cin >> n;
	memset(dp,-1,sizeof(dp));
	for(int i=1; i<=n*2; i++)cin >> a[i];
	for(int i=1; i<=n*2; i++)cin >> b[i];
	dp[1][0][0] = 0;
	dp[1][1][0] = 1;
	for(int i=1; i<n*2; i++){
		for(int j=0; j<2; j++){
			for(int k=0; k<2; k++){
				if(dp[i][j][k]!=-5){
					if(!j){//now is A
						if(a[i]<=a[i+1])maxs(dp[i+1][0][0],dp[i][j][k]);
						if(a[i]<=b[i+1])maxs(dp[i+1][1][0],dp[i][j][k]+1);
					}else{//now is b
						if(b[i]<=a[i+1])maxs(dp[i+1][0][1],dp[i][j][k]);
						if(b[i]<=b[i+1])maxs(dp[i+1][1][1],dp[i][j][k]+1);
					}
				}
			}
		}
	}
	bool find=0,cur=0,last=0;
	for(int i=0; i<2&&!find; i++){
		for(int j=0; j<2&&!find; j++){
			if(dp[n*2][i][j]>=n){
				cur = i;
				last = j;
				find = 1;
			}
		}
	}
	if(!find){
		cout << -1 << endl;
		return 0;
	}
	//start backtracking
	string s="";
	int ptr = 2*n, cnt = n;
	while(ptr!=0){
		bool aa=0,bb=0;
		if(!cur){
			s+="A";
		}else{
			s+="B";
			cnt--;
			if(cnt<0){
				cout << -1 << endl;
				return 0;
			}
		}
		if(dp[ptr-1][last][0] >= cnt)aa=1;
		if(dp[ptr-1][last][1] >= cnt)bb=1;
		if(aa&&bb){
			if(dp[ptr-1][last][0]<=dp[ptr-1][last][1]){
				cur = last;
				last = 0;
			}else{
				cur = last;
				last = 1;
			}
		}else if(aa){
			cur = last;
			last = 0;
		}else if(bb){
			cur = last;
			last = 1;
		}else if(ptr>1){
			cout << -1 << endl;
			return 0;
		}
		ptr--;
	}
	reverse(all(s));
	cout << s << endl;
}	

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