Submission #211512

#	Time	Username	Problem	Language	Result	Execution time	Memory
211512		bensonlzl	Building 4 (JOI20_building4)	C++14	100 / 100	584 ms	95572 KiB

building4

#include <bits/stdc++.h>

using namespace std;

typedef pair<int,int> pi;

int N, num[2][1000005];
int fix[1000005];
int curchar[1000005];
int linkend[1000005], linkchange[1000005];
int lowminpref, lowmaxsuff;

vector<pi> chains[1000005];
vector<int> flippos;

void die(){
	cout << -1 << '\n';
	exit(0);
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cin >> N;
	for (int i = 1; i <= 2*N; ++i){
		cin >> num[0][i];
	}
	for (int i = 1; i <= 2*N; ++i){
		cin >> num[1][i];
	}
	num[0][2*N+1] = num[1][2*N+1] = 1e9+10;

	for (int i = 1; i <= 2*N; ++i){
		fix[i] = -1;
	}


	for (int i = 1; i <= 2*N; ++i){
		//cerr << i << '\n';
		if (num[0][i] < lowminpref && num[1][i] < lowminpref){
			die();
		}
		else if (num[0][i] >= lowminpref && num[1][i] < lowminpref){
			fix[i] = 0;
			lowminpref = num[0][i];
		}
		else if (num[0][i] < lowminpref && num[1][i] >= lowminpref){
			fix[i] = 1;
			lowminpref = num[1][i];
		}
		else{
			lowminpref = max(lowminpref,min(num[0][i],num[1][i]));
		}
	}
	lowmaxsuff = 1e9+10;
	for (int i = 2*N; i >= 1; --i){
		//cerr << i << '\n';
		if (num[0][i] > lowmaxsuff && num[1][i] > lowmaxsuff){
			die();
		}
		else if (num[0][i] <= lowmaxsuff && num[1][i] > lowmaxsuff){
			if (fix[i] == 1) die();
			fix[i] = 0;
			lowmaxsuff = num[0][i];
		}
		else if (num[0][i] > lowmaxsuff && num[1][i] <= lowmaxsuff){
			if (fix[i] == 0) die();
			fix[i] = 1;
			lowmaxsuff = num[1][i];
		}
		else{
			if (fix[i] != -1) lowmaxsuff = min(lowmaxsuff,num[fix[i]][i]);
			else lowmaxsuff = min(lowmaxsuff,max(num[0][i],num[1][i]));
		}
	}
	int as = 0;
	for (int i = 1; i <= 2*N; ++i){
		if (fix[i] != -1) curchar[i] = fix[i];
		else{
			if (num[0][i] <= num[1][i]) curchar[i] = 0;
			else curchar[i] = 1;
		}
		if (curchar[i] == 0) as++;
	}
	for (int i = 2*N; i >= 1; --i){
		if (fix[i] == -1){
			linkend[i] = i;
			linkchange[i] = (curchar[i] == 0 ? -1 : 1);
			if (num[1-curchar[i]][i] > num[curchar[i+1]][i+1]){
				linkend[i] = linkend[i+1];
				linkchange[i] += linkchange[i+1];
			}
			chains[linkend[i]].push_back(pi(linkchange[i],i));
		}
	}
	for (int i = 1; i <= 2*N; ++i){
		chains[i].push_back(pi(0,1e9));
		sort(chains[i].begin(),chains[i].end());
	}
	if (as < N){
		for (int i = 1; i <= 2*N; ++i){
			reverse(chains[i].begin(),chains[i].end());
		}
		
	}
	//cerr << as << '\n';
	int diff = 0;
	for (int i = 1; i <= 2*N; ++i){
		if (as + diff == N) break;
		if (chains[i].size()){
			if (as < N){
				if (as + diff + chains[i][0].first >= N){
					for (auto it : chains[i]){
						if (as + diff + it.first == N){
							flippos.push_back(it.second);
							diff += it.first;
							break;
						}
					}
				}
				else{
					diff += chains[i][0].first;
					flippos.push_back(chains[i][0].second);
				}
			}
			else if (as > N){
				if (as + diff + chains[i][0].first <= N){
					for (auto it : chains[i]){
						if (as + diff + it.first == N){
							flippos.push_back(it.second);
							diff += it.first;
							break;
						}
					}
				}
				else{
					diff += chains[i][0].first;
					flippos.push_back(chains[i][0].second);
				}
			}
			
		}
	}
	//cerr << as << '\n';
	if (as + diff != N) die();
	for (auto it : flippos){
		if (it == 1e9) continue;
		int x = it;
		while (x != linkend[x]){
			curchar[x] = 1 - curchar[x];
			x++;
		}
		curchar[x] = 1 - curchar[x];
	}
	for (int i = 1; i <= 2*N; ++i){
		if (curchar[i] == 0) cout << 'A';
		else cout << 'B';
	}
	cout << '\n';
}


/*
3
2 5 4 9 15 11
6 7 6 8 12 14


2
1 4 10 20
3 5 8 13


2
3 4 5 6
10 9 8 7


6
25 18 40 37 29 95 41 53 39 69 61 90
14 18 22 28 18 30 32 32 63 58 71 78

6
14 18 22 28 18 30 32 32 63 58 71 78
25 18 40 37 29 95 41 53 39 69 61 90

BABBABAABABA
ABAABABBABAB

*/

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