제출 #285436

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
285436		YJU	건물 4 (JOI20_building4)	C++14	100 / 100	315 ms	75988 KiB

building4

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
typedef long double ld;
const ll MOD=1e9+7;
const ll N=2e6+5;
const ld pi=3.14159265359;
const ll INF=(1LL<<60);
#define REP(i,n) for(ll i=0;i<n;i++)
#define REP1(i,n) for(ll i=1;i<=n;i++)
#define pb push_back
#define mp make_pair
#define X first
#define Y second
#define setp setprecision
#define lwb lower_bound
#define SZ(a) (ll)a.size()
 
ll n,u[N][2],mn[N][2],mx[N][2];
vector<ll> ans;
 
int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	cin>>n;
	n*=2;
	REP(j,2)REP1(i,n)cin>>u[i][j];
	mn[1][0]=mx[1][0]=0;
	mn[1][1]=mx[1][1]=1;
	for(int i=2;i<=n;i++){
		mn[i][0]=mn[i][1]=INF;mx[i][0]=mx[i][1]=-INF;
		REP(take,2)REP(lst,2){
			if(u[i][take]>=u[i-1][lst]){
				mn[i][take]=min(mn[i][take],mn[i-1][lst]+take);
				mx[i][take]=max(mx[i][take],mx[i-1][lst]+take);
			}
		}
	}
	ll le=n/2,lst=INF;
	for(int i=n;i>=1;i--){
		ll flag=-1;
		REP(take,2){
			if(u[i][take]<=lst&&mn[i][take]<=le&&le<=mx[i][take]){
				flag=take;
				lst=u[i][take];
				break;
			}
		}
		if(flag==-1){cout<<"-1\n";return 0;}
		ans.pb(flag);le-=flag;
	}
	reverse(ans.begin(),ans.end());
	for(ll i:ans)cout<<(i?'B':'A');
	cout<<"\n";
	return 0;
}

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