Submission #223031

#	Time	Username	Problem	Language	Result	Execution time	Memory
223031		savacska	Building 4 (JOI20_building4)	C++14	100 / 100	431 ms	36600 KiB

building4

#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define x first
#define y second

using namespace std;

typedef long long ll;

int mas[5][1000005], ans[1000005], type[1000005];

int main()
{
 	//freopen("input.txt", "r", stdin);
 	//freopen("output.txt", "w", stdout);
 	ios_base::sync_with_stdio(0); cin.tie(0);
 	int n;
 	cin >> n;
 	for (int i = 1; i <= 2 * n; i++) cin >> mas[1][i];
 	for (int i = 1; i <= 2 * n; i++) cin >> mas[2][i];

 	for (int i = 1; i <= 2 * n; i++) ans[i] = min(mas[1][i], mas[2][i]);
 	for (int i = 2; i <= 2 * n; i++)
 	{
 	 	if (ans[i] < ans[i - 1]) ans[i] = max(mas[1][i], mas[2][i]);
 	 	if (ans[i] < ans[i - 1]) cout << "-1\n", exit(0);
 	}

 	int bal = 0;
 	for (int i = 1; i <= 2 * n; i++)
 		if (ans[i] == mas[1][i]) bal++, type[i] = 1;
 		else bal--, type[i] = 2;

 	int uk = 1;
 	while (uk <= 2 * n && bal != 0)
 	{
 	    if (ans[uk] != min(mas[1][uk], mas[2][uk])) {uk++; continue;}
 	    int cop = uk;
 	    while (cop + 1 <= 2 * n && ans[cop + 1] == min(mas[1][cop + 1], mas[2][cop + 1])
 	    		&& max(mas[1][cop + 1], mas[2][cop + 1]) >= max(mas[1][cop], mas[2][cop])
 	    		&& min(mas[1][cop + 1], mas[2][cop + 1]) < max(mas[1][cop], mas[2][cop])) cop++;

 	    if (cop == 2 * n || max(mas[1][cop], mas[2][cop]) <= min(mas[1][cop + 1], mas[2][cop + 1])
 	    	|| (ans[cop + 1] != min(mas[1][cop + 1], mas[2][cop + 1]) && ans[cop + 1] >= max(mas[1][cop], mas[2][cop])))
 	    {
 	    	int mx = 0, del = 0;
 	    	for (int i = cop; i >= uk; i--)
 	    	{
 	    	 	if (type[i] == 1) del -= 2;
 	    	 	else del += 2;
 	    	 	if (bal > 0) mx = min(mx, del);
 	    	 	else mx = max(mx, del);
 	     	}
 	     	del = 0;
 	     	if (bal > 0 && bal + mx < 0) mx = -bal;
 	     	if (bal < 0 && bal + mx > 0) mx = -bal;
 	     	if (mx != 0)
 	     	{
 	     		for (int i = cop; i >= uk; i--)
 	     		{
 	     	 		if (type[i] == 1) del -= 2;
 	     	 		else del += 2;
 	     	 		type[i] = 3 - type[i];
 	     	 		if (del == mx) break; 
 	     		}
 	     	}
 	     	bal += mx;
 	    }
 		uk = cop + 1;
 	}
 	if (bal != 0) cout << "-1\n", exit(0);

 	for (int i = 1; i <= 2 * n; i++)
 		if (type[i] == 1) cout << 'A';
 		else cout << 'B';
 	cout << '\n';
 	return 0;
}

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