Submission #630218

#	Time	Username	Problem	Language	Result	Execution time	Memory
630218		Arnch	Building 4 (JOI20_building4)	C++17	0 / 100	1 ms	340 KiB

building4

// oooo
/*
 har chi delet mikhad bebar ~
 gitar o ba khodet nabar! ~
 ;Amoo_Hasan;
*/

#include<bits/stdc++.h>
//#pragma GCC optimize("O3,no-stack-protector,unroll-loops")
//#pragma GCC target("avx2,fma")

using namespace std;

typedef long long ll;
typedef long double ld;

#define Sz(x) int((x).size())
#define All(x) (x).begin(), (x).end()
#define wtf(x) cout<<#x <<" : " <<x <<endl
#define mak make_pair

//constexpr int PRI = 1000696969;
constexpr ll INF = 1e18, N = 1e6 + 10, MOD = 1e9 + 7;

int a[N], b[N];
int dp[N], ri[N];
bool mark[N];

int main() {
	ios :: sync_with_stdio(0), cin.tie(0); cout.tie(0);
	
	int n; cin >>n;
	for(int i = 0; i < 2 * n; i++) cin >>a[i];
	for(int i = 0; i < 2 * n; i++) cin >>b[i];

	vector<int> vc;
	for(int i = 0; i < 2 * n; i++) {
		int val = min(a[i], b[i]);
		if(vc.empty() || vc.back() <= val) vc.push_back(val);
		else vc.push_back(max(a[i], b[i]));
	}

	string s = "";
	for(int j = 0; j < Sz(vc); j++) {
		if(vc[j] == a[j]) s.push_back('A');
		else s.push_back('B');
	}

	int cnt = 0;
	for(int j = 0; j < Sz(vc); j++) {
		if(vc[j] == a[j]) cnt++;
		else cnt--;
	}
	if(cnt == 0) {
		return cout<<s, 0;
	}

	vector<pair<int, pair<int, int> > > nap;
	for(int i = 2 * n - 1; i >= 0; i--) {
		if(vc[i] == max(a[i], b[i])) continue;

		if(i == 2 * n - 1) {
			if(vc[i] == a[i]) dp[i] = -2;
			else dp[i] = 2;
			ri[i] = i;

			nap.push_back({dp[i], {i, i}});
			continue;
		}
		if(max(a[i], b[i]) > max(a[i + 1], b[i + 1])) {
			mark[i] = 1;
			continue;
		}
		if(max(a[i], b[i]) <= vc[i + 1]) {
			if(vc[i] == a[i]) dp[i] = -2;
			else dp[i] = 2;
			ri[i] = i;

			nap.push_back({dp[i], {i, i}});
			continue;
		}
		if(mark[i + 1]) {
			mark[i] = 1;
			continue;
		}
		dp[i] = dp[i + 1];
		if(vc[i] == a[i]) dp[i] -= 2;
		else dp[i] += 2;
		ri[i] = ri[i + 1];

		nap.push_back({dp[i], {i, ri[i]}});
	}
	
	sort(All(nap));
	if(cnt < 0) {
		while(!nap.empty() && cnt < 0) {
			int val = nap.back().first, l = nap.back().second.first, r = nap.back().second.second;
			nap.pop_back();

			if(val < 0) {
				return cout<<-1, 0;
			}
			if(val + cnt > 0) continue;
			cnt += val;
			for(int j = l; j <= r; j++) {
				if(s[j] == 'A') s[j] = 'B';
				else s[j] = 'A';
			}	
		}
		if(cnt < 0) return cout<<-1, 0;
		return cout<<s, 0;
	}
	reverse(All(nap));
	while(!nap.empty() && cnt > 0) {
		int val = nap.back().first, l = nap.back().second.first, r = nap.back().second.second;
		nap.pop_back();

		if(val > 0) {
			return cout<<-1, 0;
		}
		if(val + cnt < 0) continue;
		cnt += val;
		for(int j = l; j <= r; j++) {
			if(s[j] == 'A') s[j] = 'B';
			else s[j] = 'A';
		}	
	}
	if(cnt > 0) return cout<<-1, 0;
	return cout<<s, 0;

}

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