Submission #211512

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
211512	2020-03-20T16:26:39 Z	bensonlzl	Building 4 (JOI20_building4)	C++14	100 / 100	584 ms	95572 KB

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.0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	17 ms	23808 KB	Output is correct
2	Correct	17 ms	23936 KB	Output is correct
3	Correct	17 ms	23936 KB	Output is correct
4	Correct	20 ms	23936 KB	Output is correct
5	Correct	22 ms	23936 KB	Output is correct
6	Correct	23 ms	24064 KB	Output is correct
7	Correct	18 ms	24040 KB	Output is correct
8	Correct	21 ms	24108 KB	Output is correct
9	Correct	20 ms	24192 KB	Output is correct
10	Correct	18 ms	24064 KB	Output is correct
11	Correct	18 ms	24064 KB	Output is correct
12	Correct	19 ms	24064 KB	Output is correct
13	Correct	19 ms	24064 KB	Output is correct
14	Correct	19 ms	24064 KB	Output is correct
15	Correct	19 ms	24192 KB	Output is correct
16	Correct	20 ms	24064 KB	Output is correct
17	Correct	22 ms	24064 KB	Output is correct
18	Correct	19 ms	24064 KB	Output is correct
19	Correct	19 ms	24064 KB	Output is correct
20	Correct	19 ms	24064 KB	Output is correct
21	Correct	18 ms	24064 KB	Output is correct
22	Correct	19 ms	24064 KB	Output is correct
23	Correct	22 ms	24192 KB	Output is correct
24	Correct	19 ms	24192 KB	Output is correct
25	Correct	20 ms	24064 KB	Output is correct
26	Correct	19 ms	24192 KB	Output is correct
27	Correct	20 ms	24100 KB	Output is correct
28	Correct	22 ms	24192 KB	Output is correct
29	Correct	18 ms	24192 KB	Output is correct
30	Correct	18 ms	24192 KB	Output is correct
31	Correct	22 ms	24192 KB	Output is correct
32	Correct	21 ms	24064 KB	Output is correct
33	Correct	19 ms	24192 KB	Output is correct

Subtask #2

89.0 / 89.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	17 ms	23808 KB	Output is correct
2	Correct	17 ms	23936 KB	Output is correct
3	Correct	17 ms	23936 KB	Output is correct
4	Correct	20 ms	23936 KB	Output is correct
5	Correct	22 ms	23936 KB	Output is correct
6	Correct	23 ms	24064 KB	Output is correct
7	Correct	18 ms	24040 KB	Output is correct
8	Correct	21 ms	24108 KB	Output is correct
9	Correct	20 ms	24192 KB	Output is correct
10	Correct	18 ms	24064 KB	Output is correct
11	Correct	18 ms	24064 KB	Output is correct
12	Correct	19 ms	24064 KB	Output is correct
13	Correct	19 ms	24064 KB	Output is correct
14	Correct	19 ms	24064 KB	Output is correct
15	Correct	19 ms	24192 KB	Output is correct
16	Correct	20 ms	24064 KB	Output is correct
17	Correct	22 ms	24064 KB	Output is correct
18	Correct	19 ms	24064 KB	Output is correct
19	Correct	19 ms	24064 KB	Output is correct
20	Correct	19 ms	24064 KB	Output is correct
21	Correct	18 ms	24064 KB	Output is correct
22	Correct	19 ms	24064 KB	Output is correct
23	Correct	22 ms	24192 KB	Output is correct
24	Correct	19 ms	24192 KB	Output is correct
25	Correct	20 ms	24064 KB	Output is correct
26	Correct	19 ms	24192 KB	Output is correct
27	Correct	20 ms	24100 KB	Output is correct
28	Correct	22 ms	24192 KB	Output is correct
29	Correct	18 ms	24192 KB	Output is correct
30	Correct	18 ms	24192 KB	Output is correct
31	Correct	22 ms	24192 KB	Output is correct
32	Correct	21 ms	24064 KB	Output is correct
33	Correct	19 ms	24192 KB	Output is correct
34	Correct	305 ms	35352 KB	Output is correct
35	Correct	397 ms	68364 KB	Output is correct
36	Correct	391 ms	68560 KB	Output is correct
37	Correct	390 ms	68980 KB	Output is correct
38	Correct	453 ms	75768 KB	Output is correct
39	Correct	431 ms	83552 KB	Output is correct
40	Correct	494 ms	86968 KB	Output is correct
41	Correct	485 ms	92124 KB	Output is correct
42	Correct	397 ms	70348 KB	Output is correct
43	Correct	445 ms	72980 KB	Output is correct
44	Correct	422 ms	73188 KB	Output is correct
45	Correct	422 ms	73704 KB	Output is correct
46	Correct	471 ms	79584 KB	Output is correct
47	Correct	444 ms	87612 KB	Output is correct
48	Correct	453 ms	87520 KB	Output is correct
49	Correct	477 ms	87340 KB	Output is correct
50	Correct	414 ms	75868 KB	Output is correct
51	Correct	404 ms	72056 KB	Output is correct
52	Correct	288 ms	79976 KB	Output is correct
53	Correct	299 ms	80088 KB	Output is correct
54	Correct	328 ms	81768 KB	Output is correct
55	Correct	320 ms	81124 KB	Output is correct
56	Correct	533 ms	95568 KB	Output is correct
57	Correct	423 ms	81512 KB	Output is correct
58	Correct	415 ms	81764 KB	Output is correct
59	Correct	584 ms	95572 KB	Output is correct
60	Correct	396 ms	81760 KB	Output is correct
61	Correct	432 ms	85344 KB	Output is correct
62	Correct	433 ms	84828 KB	Output is correct
63	Correct	439 ms	85732 KB	Output is correct
64	Correct	413 ms	83548 KB	Output is correct
65	Correct	438 ms	85664 KB	Output is correct