Submission #1038191

#	Time	Username	Problem	Language	Result	Execution time	Memory
1038191		hotboy2703	Building 4 (JOI20_building4)	C++17	11 / 100	45 ms	21852 KiB

building4

#include<bits/stdc++.h>
using ll = long long;
using namespace std;
#define pll pair <ll,ll>
#define fi first
#define se second
#define MP make_pair
#define sz(a) (ll((a).size()))
#define BIT(mask,i) (((mask) >> (i))&1)
#define MASK(i) (1LL << (i))
const ll MAXN = 5e5+100;
ll A[MAXN][2];
bool ans[MAXN];
ll n;
int main(){
	ios_base::sync_with_stdio(0);cin.tie(nullptr);
	cin>>n;
	n*=2;
	for (ll i = 1;i <= n;i ++)cin>>A[i][0];
	for (ll i = 1;i <= n;i ++)cin>>A[i][1];
	ll last = -1;
	for (ll i = 1;i <= n;i ++){
		bool sw = 0;
		if (A[i][0] > A[i][1]){
			swap(A[i][0],A[i][1]);
			sw = 1;
		}
		if (max(A[i][0],A[i][1]) < last){
			cout<<-1<<endl;
			return 0;
		}
		if (A[i][0] >= last){
			ans[i] = 0;
			last = A[i][0];
		}
		else {
			ans[i] = 1;
			last = A[i][1];
		}
		if (sw){
			swap(A[i][0],A[i][1]);
			ans[i] = 1-ans[i];
		}
	}
	ll sum = 0;
	for (ll i = 1;i <= n;i ++)sum += ans[i] ? -1 : +1;
	last = -1;
	auto solve = [&](ll l,ll r){
		ll cur = sum;
		ll res = sum;
		ll res_id = r+1;
		for (ll j = r;j >= l;j --){
			cur += ans[j] ? +2 : -2;
			if (abs(cur) < abs(res)){
				res = cur;
				res_id = j;
			}
		}
		sum = res;
		for (ll j = res_id;j <= r;j ++)ans[j] = 1-ans[j];
	};
	
	for (ll i = n;i >= 1;i --){
		if (A[i][ans[i]] > A[i][1-ans[i]]){
			if (last != -1)solve(i+1,last);
			last = -1;
		}
		else{
			if (i == n || A[i][1-ans[i]] <= A[i+1][ans[i+1]]){
				if (last != -1)solve(i+1,last);
				last = i;
			}
			else{
				if (A[i][1-ans[i]] <= A[i+1][1-ans[i+1]]){

				}
				else{
					if (last != -1)solve(i+1,last);
					last = -1;
				}
			}
		}
	}
	if (last != -1)solve(1,last);
	if (sum != 0)cout<<-1<<endl;
	else for (ll i = 1;i <= n; i++)cout<<char('A' + ans[i]);
}

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