Submission #630799

#	Time	Username	Problem	Language	Result	Execution time	Memory
630799		codr0	Building 4 (JOI20_building4)	C++14	100 / 100	267 ms	31384 KiB

building4

#include <bits/stdc++.h>
#define ll long long
#define pll pair<ll,ll>
#define pii pair<int,int>

#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define FORR(i,a,b) for(int i=a;i>=b;i--)
#define F first
#define S second
#define err(x) cerr<<#x<<" : "<<x<<'\n';
#define dmid int mid=(r+l)/2
#define lc 2*id
#define rc 2*id+1
#define pb push_back
#define all(x) x.begin(),x.end()
#define SZ(x) (int)x.size()
#define maxm(a,b) a=max(a,b)
#define minm(a,b) a=min(a,b)

using namespace std;
const int N=1e6+4;
int l[2][N],r[2][N],a[2][N];
bool ans[N];

	int main(){
	iostream::sync_with_stdio(0); cin.tie(0);

	int n; cin>>n;
	FOR(b,0,1) FOR(i,1,2*n) cin>>a[b][i];
	FOR(b,0,1) FOR(i,1,2*n) r[b][i]=-1;
	FOR(b,0,1) FOR(i,1,2*n) l[b][i]=1e9;
	FOR(i,1,2*n){
		FOR(b,0,1){
			if(a[1][i]>=a[b][i-1]&&r[b][i-1]!=-1){ maxm(r[1][i],r[b][i-1]+1); minm(l[1][i],l[b][i-1]+1);}
		}
		FOR(b,0,1){
			if(a[0][i]>=a[b][i-1]&&r[b][i-1]!=-1){ maxm(r[0][i],r[b][i-1]); minm(l[0][i],l[b][i-1]);}
		}
	}
	bool last;
	bool ok=0;
	if(n>=l[0][2*n]&&n<=r[0][2*n]){
		ok=1; ans[2*n]=0; last=0;
	}
	if(n>=l[1][2*n]&&n<=r[1][2*n]){
		ok=1; ans[2*n]=1; last=1;
	}
	if(!ok){
		cout<<"-1\n";
		return 0;
	}
	int x=n-ans[2*n];
	FORR(i,2*n-1,1){
		if(x>=l[0][i]&&x<=r[0][i]&&a[0][i]<=a[last][i+1]){
			ans[i]=0;
			last=0;
		}else if(x>=l[1][i]&&x<=r[1][i]&&a[1][i]<=a[last][i+1]){
			ans[i]=1;
			last=1;
			x--;
		}
	}
	FOR(i,1,2*n) cout<<(char)('A'+ans[i]);
	cout<<'\n';

	return 0;
	}

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