Submission #1008389

#	Time	Username	Problem	Language	Result	Execution time	Memory
1008389		giorgi_pkhaladze	Building 4 (JOI20_building4)	C++14	100 / 100	466 ms	45344 KiB

building4

#include <bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pb push_back
#define ff first
#define ss second
using namespace std;
int n,m,k,i,j,ans,a[2][1000005],d[2][1000005][2];
int main() {
	cin>>n;
	n*=2;
	for(k=1; k<=n; k++)
		cin>>a[1][k];
	for(k=1; k<=n; k++)
		cin>>a[0][k];
	for(k=1; k<=n; k++){
		for(i=0; i<=1; i++){
			d[i][k][0]=n+1; 
			d[i][k][1]=-1;
			for(j=0; j<=1; j++){
				if(a[j][k-1]<=a[i][k]){
					d[i][k][0]=min(d[i][k][0],d[j][k-1][0]+i);
					d[i][k][1]=max(d[i][k][1],d[j][k-1][1]+i);
				}
			}
		}
	}
	int sz=-1;
	int pos=-1;
	if(d[0][n][0]<=n/2 && d[0][n][1]>=n/2){
		sz=n;
		pos=0;
	}
	if(d[1][n][0]<=n/2 && d[1][n][1]>=n/2){
		sz=n;
		pos=1;
	}
	string s(n,' ');
	if(sz==-1){
		cout<<-1;
		return 0;
	}
	int cnt;
	cnt=n/2;
	while(sz--){
		if(pos==0){
			s[sz]='B';
		}
		else s[sz]='A';
		cnt-=pos;
		if(a[pos][sz+1]>=a[1][sz] && d[1][sz][0]<=cnt && d[1][sz][1]>=cnt){
			pos=1;
		}
		else pos=0;
	}
	cout<<s;
}

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