제출 #211788

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
211788		zscoder	건물 4 (JOI20_building4)	C++17	100 / 100	328 ms	44780 KiB

building4

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;
 
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define fbo find_by_order
#define ook order_of_key
 
typedef long long ll;
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef long double ld; 
typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> pbds;

const int N = 1055555;
int a[2][N+1];
ii dp[N+1][2];

//int dp[5555][5555];

void uni(ii &a, ii b)
{
	a.fi=min(a.fi,b.fi);
	a.se=max(a.se,b.se);
}

int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	int n; cin>>n; n*=2;
	const bool DEBUG = 0;
	for(int cc=1;;cc++)
	{
		if(!DEBUG)
		{
			for(int i=0;i<n;i++)
			{
				cin>>a[0][i];
			}
			for(int i=0;i<n;i++)
			{
				cin>>a[1][i];
			}
		}
		else
		{
			for(int i=0;i<n;i++)
			{
				a[0][i]=rand();
				a[1][i]=rand();
			}
		}
		/*
		for(int i=0;i<n;i++)
		{
			for(int j=0;j<=n;j++)
			{
				dp[i][j]=int(1e9)+7;
			}
		}
		dp[0][1]=a[0][0];
		dp[0][0]=a[1][0];
		for(int i=1;i<n;i++)
		{
			for(int j=0;j<=i+1;j++)
			{
				//choose a
				if(j&&dp[i-1][j-1]<=a[0][i]) dp[i][j]=min(dp[i][j],a[0][i]);
				if(dp[i-1][j]<=a[1][i]) dp[i][j]=min(dp[i][j],a[1][i]);
			}
			int l=int(1e9);
			int r=0;
			int cnt=0;
			for(int j=0;j<=i+1;j++)
			{
				if(dp[i][j]<int(1e9)+7)
				{
					l=min(l,j); r=max(r,j); cnt++;
				}
			}
			if(l>r) l=r+1;
			assert(cnt==r-l+1);
		}
		*/
		dp[0][0]={0,0};
		dp[0][1]={1,1};
		for(int i=1;i<n;i++)
		{
			for(int j=0;j<2;j++)
			{
				dp[i][j]={int(1e9),-int(1e9)};
				//use a[j][i]
				for(int k=0;k<2;k++)
				{
					if(dp[i-1][k].fi>dp[i-1][k].se) continue;
					if(a[k][i-1]<=a[j][i]) uni(dp[i][j],{dp[i-1][k].fi+j,dp[i-1][k].se+j});
				}
				//cerr<<i<<' '<<j<<' '<<dp[i][j].fi<<' '<<dp[i][j].se<<'\n';
			}
		}
		int endpos=-1;
		for(int i=0;i<2;i++)
		{
			if(dp[n-1][i].fi<=n/2&&dp[n-1][i].se>=n/2)
			{
				endpos=i; break;
			}
		}
		if(endpos==-1)
		{
			cout<<endpos<<'\n';
		}
		else
		{
			string s;
			int cnt=n/2;
			for(int i=n-1;i>=0;i--)
			{
				s+=char('A'+endpos);
				cnt-=endpos;
				if(i>0)
				{
					//look at dp[endpos][i]
					int pos=0;
					for(int j=0;j<2;j++)
					{
						if(dp[i-1][j].fi<=cnt&&cnt<=dp[i-1][j].se&&a[j][i-1]<=a[endpos][i])
						{
							endpos=j; pos=1;
							break;
						}
					}
					assert(pos);
				}
			}
			reverse(s.begin(),s.end());
			cout<<s<<'\n';
		}
		if(DEBUG)
		{
			cerr<<"Case #"<<cc<<" completed\n";
		}
		else return 0;
	}
}

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