Submission #1280889

#	Time	Username	Problem	Language	Result	Execution time	Memory
1280889		WH8	건물 4 (JOI20_building4)	C++20	100 / 100	738 ms	56208 KiB

building4

#include <bits/stdc++.h>
using namespace std;
#define int long long 
#define pll pair<int, int>
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define endl '\n'
#define ld long double

	
signed main(){
	int n;cin>>n;
	vector<array<int,2>> a(2*n); 
	for(int i=0;i<2*n;i++)cin>>a[i][0];
	for(int i=0;i<2*n;i++)cin>>a[i][1];
	vector<array<pair<int,int>,2>> r(2*n);
	for(int i=0;i<2*n;i++){
		r[i][1]=r[i][0]={(int)1e15, -1};
	}
	r[0][0]={1, 1};
	r[0][1]={0, 0};
	for(int i=1;i<2*n;i++){
		for(int j=0;j<2;j++){
			for(int k=0;k<2;k++){
				if(a[i-1][k]<=a[i][j]) r[i][j].f=min(r[i-1][k].f, r[i][j].f),
				r[i][j].s=max(r[i-1][k].s,r[i][j].s);
			}
			if(j==0 and r[i][j].s != -1)r[i][j].f++,r[i][j].s++;
			//~ printf("x %lld y %lld, l %lld r %lld\n", i,j,r[i][j].f,r[i][j].s);
		}
	}
	vector<int> ans(2*n,-1);
	auto dfs=[&](auto& dfs, int x, int y, int t)->void{
		//~ printf("dfs x %lld, y %lld, t %lld\n",x,y,t);
		//~ fflush(stdout);
		assert(r[x][y].f <= t and r[x][y].s >= t);
		ans[x]=y;
		if(y==0)t--;
		if(x==0)return;
		for(int j=0;j<2;j++){
			if(a[x-1][j]<=a[x][y] and r[x-1][j].f <= t and t<=r[x-1][j].s){
				dfs(dfs, x-1, j, t);
				break;
			}
		}
	};
	if(r[2*n-1][0].f <= n and n <= r[2*n-1][0].s){
		dfs(dfs, 2*n-1, 0, n);
	}
	else if (r[2*n-1][1].f <= n and n <= r[2*n-1][1].s){
		dfs(dfs, 2*n-1, 1, n);
	}
	else {
		cout<<-1;
		return 0;
	}
	for(int i=0;i<2*n;i++){
		assert(ans[i]!=-1);
		if(ans[i]==0)cout<<'A';
		else cout<<'B';
	}
}

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