Submission #1213067

#	Time	Username	Problem	Language	Result	Execution time	Memory
1213067		emptypringlescan	Building 4 (JOI20_building4)	C++17	100 / 100	164 ms	36788 KiB

building4

#include <bits/stdc++.h>
using namespace std;
long long arr[1000005],brr[1000005];
pair<int,int> can[2][1000005];
int32_t main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n;
	cin >> n;
	for(int i=1; i<=2*n; i++) cin >> arr[i];
	for(int i=1; i<=2*n; i++) cin >> brr[i];
	can[0][0]={0,0}; can[1][0]={0,0};
	for(int i=1; i<=2*n; i++){
		can[0][i]={1e9,-1};
		if(arr[i]>=arr[i-1]){
			can[0][i].first=min(can[0][i].first,can[0][i-1].first+1);
			can[0][i].second=max(can[0][i].second,can[0][i-1].second+1);
		}
		if(arr[i]>=brr[i-1]){
			can[0][i].first=min(can[0][i].first,can[1][i-1].first+1);
			can[0][i].second=max(can[0][i].second,can[1][i-1].second+1);
		}
		can[1][i]={1e9,-1};
		if(brr[i]>=arr[i-1]){
			can[1][i].first=min(can[1][i].first,can[0][i-1].first);
			can[1][i].second=max(can[1][i].second,can[0][i-1].second);
		}
		if(brr[i]>=brr[i-1]){
			can[1][i].first=min(can[1][i].first,can[1][i-1].first);
			can[1][i].second=max(can[1][i].second,can[1][i-1].second);
		}
		//assert(!(can[0][i].second<can[1][i].first-1||can[0][i].first>can[1][i].second+1));
		//cout << can[0][i].first << ' ' << can[0][i].second << "   " << can[1][i].first << ' ' << can[1][i].second << '\n';
	}
	if((can[0][2*n].first>n||can[0][2*n].second<n)&&(can[1][2*n].first>n||can[1][2*n].second<n)){
		cout << -1;
		return 0;
	}
	int cur=n,val=1e9;
	vector<int> ans;
	for(int i=2*n; i>0; i--){
		if(arr[i]<=val&&can[0][i].first<=cur&&can[0][i].second>=cur){
			cur--;
			val=arr[i];
			ans.push_back(0);
		}
		else{
			val=brr[i];
			ans.push_back(1);
		}
	}
	reverse(ans.begin(),ans.end());
	for(int i:ans) cout << (i?'B':'A');
}

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