Submission #383846

#	Time	Username	Problem	Language	Result	Execution time	Memory
383846		ec1117	Building 4 (JOI20_building4)	C++17	11 / 100	788 ms	524292 KiB

building4

#include "bits/stdc++.h"
using namespace std;

#define mp make_pair
#define f first
#define s second
#define FOR(i,a,b) for(int i=a;i<b;i++)
#define For(i,b) FOR(i,0,b)
#define trav(a,b) for(auto& a:b)
#define vi vector<int>
#define vpi vector<pi>
#define pb push_back
#define bk back()
#define ins insert
#define pi pair<int,int>
#define ll long long
#define sz(x) (int) x.size()
#define all(x) x.begin(),x.end()
#define nl '\n'

const int MX=1e6+10;
const int MX2=4e6+10;
int n,a[MX][2];
vector<vector<vi>> dp[MX];//hold val of hm A left
vector<vector<vpi>> dp2[MX];//hold val of hm A left
//dp[i][j][k][l]

// void dbg(){
// 	cerr<<endl;
// }
// template<class A,class... B> dbg(A a, B... b){
// 	cerr<<a;
// 	if(sizeof...(b))cerr<<", ";
// 	dbg(b...);
// }

struct DivC{
	void go(int x,int l, int r){
		dp[x]=vector<vector<vi>>(r-l+2,vector<vi>(2,vi(2,-1)));
		dp2[x]=vector<vector<vpi>>(r-l+2,vector<vpi>(2,vpi(2,{-1,-1})));
		if(l==r){
			dp[x][1][0][0]=1;
			dp[x][0][1][1]=0;
			return;
		}
		if(l!=r){
			int m=(l+r)/2;
			go(x*2,l,m);
			go(x*2+1,m+1,r);
			For(i,r-l+2){//16nlog
				For(t1,2)For(t2,2){
					For(t3,2)For(t4,2){
						For(k,i+1){  
							if(k<sz(dp[x*2]) && i-k<sz(dp[x*2+1])){
								if(a[m][t3]<=a[m+1][t4]){
									if(dp[x*2][k][t1][t3]!=-1 && dp[x*2+1][i-k][t4][t2]!=-1){
										dp[x][i][t1][t2]=k;
										dp2[x][i][t1][t2]={t3,t4};
										break;
									}
								}
							}
						}
					}
				}
			}
		}
	}
};

DivC dc;
string ret;

void go2(int x, int as, int l, int r){
	if(sz(dp[x])==2){
		ret+=(as?"A":"B");
	} else {
		int num=dp[x][as][l][r];
		int t1=dp2[x][as][l][r].f;
		int t2=dp2[x][as][l][r].s;
		go2(x*2,num,l,t1);
		go2(x*2+1,as-num,t2,r);
	}
}

int main(){
	cin.tie(0)->sync_with_stdio(0);
	cin>>n;
	For(i,2*n)cin>>a[i][0];
	For(i,2*n)cin>>a[i][1];
	dc.go(1,0,2*n-1);
	For(i,2)For(j,2){
		// cout<<i<<" "<<j<<" "<<dp[1][n][i][j]<<nl;
		if(dp[1][n][i][j]!=-1){
			go2(1,n,i,j);
			cout<<ret<<nl;
			return 0;
		}
	}
	cout<<-1<<nl;
}

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