Submission #211826

#	Time	Username	Problem	Language	Result	Execution time	Memory
211826		MarcoMeijer	Building 4 (JOI20_building4)	C++14	100 / 100	322 ms	42232 KiB

building4

#include <bits/stdc++.h>
using namespace std;

//macros
typedef long long ll;
typedef pair<int, int> ii;
typedef tuple<int, int, int> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<iii> viii;
typedef vector<ll> vll;
#define REP(a,b,c) for(int a=int(b); a<int(c); a++)
#define RE(a,c) REP(a,0,c)
#define RE1(a,c) REP(a,1,c+1)
#define REI(a,b,c) REP(a,b,c+1)
#define REV(a,b,c) for(int a=int(c-1); a>=int(b); a--)
#define INF 1e9
#define pb push_back
#define fi first
#define se second
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

//===================//
//  Added libraries  //
//===================//

//===================//
//end added libraries//
//===================//

void program();
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	program();
}


//===================//
//   begin program   //
//===================//

const int MX = 2e6;
int n, a[MX][2];
ii dp[MX][2];
string ans;

void fillAns(int i, int j, int k) {
	ans[i] = 'A'+j;
	if(i == 0) return;
	if(a[i][j] >= a[i-1][0] && dp[i-1][0].fi <= k && k <= dp[i-1][0].se) fillAns(i-1,0,k);
	else fillAns(i-1,1,k-1);
}

void program() {
	cin>>n;
	n *= 2;
	RE(i,n) cin>>a[i][0];
	RE(i,n) cin>>a[i][1];
	dp[0][0] = {0,0};
	dp[0][1] = {1,1};
	REP(i,1,n) RE(j,2) {
		dp[i][j] = {INF,-INF};
		RE(k,2) {
			if(a[i][j] >= a[i-1][k]) {
				dp[i][j].fi = min(dp[i][j].fi, dp[i-1][k].fi+j);
				dp[i][j].se = max(dp[i][j].se, dp[i-1][k].se+j);
			}
		}
	}
	ans.resize(n);
		 if(dp[n-1][0].fi <= n/2 && n/2 <= dp[n-1][0].se) fillAns(n-1,0,n/2);
	else if(dp[n-1][1].fi <= n/2 && n/2 <= dp[n-1][1].se) fillAns(n-1,1,n/2-1);
	else {
		cout<<-1<<endl;
		return;
	}
	cout<<ans<<endl;
}

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