Submission #1222538

#	Time	Username	Problem	Language	Result	Execution time	Memory
1222538		boclobanchat	건물 4 (JOI20_building4)	C++20	0 / 100	1 ms	328 KiB

building4

#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e6+5;
pair<int,int> dp[MAXN][2];
int A[MAXN][2];
bool ck[MAXN][2];
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin>>n;
    for(int i=1;i<=n*2;i++) cin>>A[i][0];
    for(int i=1;i<=n*2;i++) cin>>A[i][1];
    for(int i=1;i<=n*2;i++) if(i==1) dp[i][0]={1,1},dp[i][1]={0,0};
    else for(int a=0;a<2;a++)
    {
    	dp[i][a]={-1,-1};
    	for(int b=0;b<2;b++) if(A[i-1][b]<=A[i][a]) 
    	{
    		if(dp[i][a].first==-1) dp[i][a]={dp[i-1][b].first+(a==0),dp[i-1][b].second+(a==0)};
    		else dp[i][a]={min(dp[i][a].first,dp[i-1][b].first+(a==0)),max(dp[i][a].second,dp[i-1][b].second+(a==0))};
		}
	}
	ck[n*2][0]=(dp[n*2][0].first<=n&&n<=dp[n*2][0].second);
	ck[n*2][1]=(dp[n*2][1].first<=n&&n<=dp[n*2][1].second);
	if(!ck[n*2][0]&&!ck[n*2][1]) return cout<<-1,0;
	int pos=0;
	if(!ck[n*2][0]) pos=1;
	int k=n;
	string ans;
	for(int i=n*2;i;i--)
	{
		ans+=char(pos+'A'),k-=(pos==0);
		if(i>1)
		{
			if(A[i-1][0]<=A[i][pos]&&dp[i-1][0].first<=k&&k<=dp[i-1][0].second&&k>0) pos=0;
			else pos=1;
		}
	}
	reverse(ans.begin(),ans.end());
	cout<<ans;
}

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