제출 #211506

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
211506		theStaticMind	건물 4 (JOI20_building4)	C++14	100 / 100	907 ms	206244 KiB

building4

#include<bits/stdc++.h>
#define pb push_back
#define ii pair<int,int>
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
#define INF 100000000000000000
#define modulo 1000000007
#define mod 998244353
#define int long long int
using namespace std;

#define iii pair<ii, int>

int32_t main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	int n;
	cin >> n; n *= 2;
	vector<iii> arr;
	for(int i = 0; i < n; i++){
		int x;
		cin >> x;
		arr.pb({{x, i}, 1});
	}
	for(int i = 0; i < n; i++){
		int x;
		cin >> x;
		arr.pb({{x, i}, -1});
	}
	sort(all(arr));
	
	vector<int> L, R;
	int l = 0;
	for(int i = 0; i < n; i++){
		while(l < sz(arr) && i != arr[l].first.second) l++;

		if(l == sz(arr)){
			cout << -1;
			return 0;
		}

		L.pb(l); 
	}

	int r = sz(arr) - 1;
	for(int i = n - 1; i >= 0; i--){
		while(i != arr[r].first.second) r--;
		R.pb(r);
	}

	reverse(all(R));

	vector<vector<int> > Lgrp, Rgrp;
	vector<ii> range;
	vector<int> tl, tr;

	l = 0, r = 0;
	while(l < sz(L) && r < sz(R)){
		tl.clear(), tr.clear();
		int sum = 0;
		int mn, mx;
		do{
			if(l != sz(L) && (r == sz(R) || L[l] <= R[r])){
				sum++;
				tl.pb(L[l++]);
			}
			else{
				sum--;
				tr.pb(R[r++]);
			}
		}while(sz(tl) != sz(tr));

		for(auto p : tl){
			sum += arr[p].second;
		}
		mn = mx = sum;

		for(int i = sz(tl) - 1; i >= 0; i--){
			sum -= arr[tl[i]].second;
			sum += arr[tr[i]].second;
			mn = min(mn, sum);
			mx = max(mx, sum);
		}
		Lgrp.pb(tl);
		Rgrp.pb(tr);
		range.pb({mn, mx});
	}

	vector<int> g;
	int S = 0;
	for(auto p : range) S += p.first, g.pb(p.first);

	if(S > 0 || (S + INF) % 2){
		cout << -1;
		return 0;
	}

	l = 0;
	for(int i = 0; i < sz(range); i++){
		int c = min(range[i].second - range[i].first, -S);
		S += c;
		g[i] += c;
	}

	if(S < 0){
		cout << -1;
		return 0;
	}
	vector<int> ans(n);
	for(int i = 0; i < sz(range); i++){
		int sum = 0;
		for(int j = sz(Lgrp[i]) - 1; j >= 0; j--){
			ans[arr[Lgrp[i][j]].first.second] = arr[Lgrp[i][j]].second;
			sum += arr[Lgrp[i][j]].second;
		}
		for(int j = sz(Lgrp[i]) - 1; j >= 0 && sum != g[i]; j--){
			sum -= arr[Lgrp[i][j]].second;
			sum += arr[Rgrp[i][j]].second;
			ans[arr[Lgrp[i][j]].first.second] = arr[Rgrp[i][j]].second;
		}
	}
	for(int i = 0; i < n; i++) cout << (ans[i] == 1 ? 'A' : 'B');

}

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