Submission #899068

#	Time	Username	Problem	Language	Result	Execution time	Memory
899068		sunwukong123	건물 4 (JOI20_building4)	C++14	0 / 100	4 ms	4952 KiB

building4

#include <bits/stdc++.h>
using namespace std;
#define int long long 
#ifdef LOCAL
void debug_out() {cerr<<endl;}
template <typename Head, typename... Tail>
void debug_out(Head _H, Tail... _T) {cerr<<" "<<to_string(_H);debug_out(_T...);}
#define debug(...) cerr<<"["<<#__VA_ARGS__<<"]:",debug_out(__VA_ARGS__)
#else
#define debug(...)
#endif
const int MAXN = 1000005;
const int inf=1000000500ll;
const long long oo =1000000000000000500ll;
const int MOD = (int)1e9 + 7;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef pair<int,int> pi; 
int n;
int A[MAXN][2];
pi dp[MAXN][2]; // {position, A/B}
pi combi(pi A, pi B){
	int st=min(A.first,B.first);
	int en=max(A.second,B.second);
	return make_pair(st,en);
}
bool in(int x, pi r){
	return r.first <= x && x<=r.second;
}
vector<char>out;
void backtrack(pi cur, int val){
	debug(cur.first,cur.second);
	if(cur.second == 0)out.push_back('A');
	else out.push_back('B');
	if(cur.first == 1)return;
	int nval=val-(cur.second == 0);
	debug(A[cur.first-1][0],A[cur.first][cur.second],dp[cur.first-1][0].first,dp[cur.first-1][0].second,nval);
	if(A[cur.first-1][0] <= A[cur.first][cur.second] && in(nval,dp[cur.first-1][0])){
		pi ncur=make_pair(cur.first-1,0);
		backtrack(ncur,nval);
	} else {
		assert(A[cur.first-1][1] <= A[cur.first][cur.second] && in(nval,dp[cur.first-1][1]));
		pi ncur=make_pair(cur.first-1,1);
		backtrack(ncur,nval);
	}
}
int32_t main() 
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin>>n;
	for(int i=1;i<=2*n;i++)cin>>A[i][0];
	for(int i=1;i<=2*n;i++)cin>>A[i][1];
	
	for(int i=1;i<=2*n;i++){
		for(int j=0;j<=1;j++){
			dp[i][j]={-1,-1};
		}
	}
	dp[0][0]={0,0};
	dp[0][1]={0,0};

	for(int i=1;i<=2*n;i++){
		for(int j=0;j<=1;j++){
			for(int k=0;k<=1;k++){
				if(A[i-1][k] <= A[i][j]){
					if(dp[i][j].first == -1){
						if(j==0)dp[i][j]=make_pair(dp[i-1][k].first+1,dp[i-1][k].second+1);
						else dp[i][j]=dp[i-1][k];
					} else{
						if(dp[i-1][k].first==-1)continue;
						if(j==0)dp[i][j]=combi(dp[i][j],make_pair(dp[i-1][k].first+1,dp[i-1][k].second+1));
						else dp[i][j]=combi(dp[i][j],dp[i-1][k]);
					}
				}
			}
		}
		debug(i,dp[i][0].first,dp[i][0].second);
		debug(i,dp[i][1].first,dp[i][1].second);
	}

	if(in(n,dp[2*n][0])){
		pi cur=make_pair(2*n,0);
		backtrack(cur,n);
		reverse(out.begin(),out.end());
		for(auto x:out)cout<<x;
		exit(0);
	}
	if(in(n,dp[2*n][1])){
		pi cur=make_pair(2*n,1);
		backtrack(cur,n);
		reverse(out.begin(),out.end());
		for(auto x:out)cout<<x;
		exit(0);
	}
	cout<<-1;
}	

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