제출 #228797

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
228797		emaborevkovic	건물 4 (JOI20_building4)	C++14	0 / 100	71 ms	117756 KiB

building4

#include <iostream>
#include <cstdio>
#include <vector>

//maksimumi i minimumi su rastuci
// a +1  b -1

using namespace std;

#define ss second
#define ff first
#define mp make_pair
#define pb push_back
#define ll long long

const int N = 1e6+11;
int n;
int a[N], b[N];
int res;
vector <int> v[N];
vector <int> s1[N];
vector <int> s2[N];
vector <int> koji1[N];
vector <int> koji2[N];
int mali[N];
int veliki[N];
int br;
int uzeo[N];
int sol[N];

void ne() {
	cout << -1;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> n;
	for (int i=0;i<2*n;i++) {
		cin >> a[i];
	}
	for (int i=0;i<2*n;i++) {
		cin >> b[i];
	}
	int mini = min(a[0], b[0]);
	for (int i=1;i<2*n;i++) {
		if (a[i] < mini && b[i] < mini) {
			ne();
			return 0;
		}
		if (a[i] < mini) {
			a[i] = -1;
			mini = b[i];
		}
		else if (b[i] < mini) {
			b[i] = -1;
			mini = b[i];
		}
		else {
			mini = min(a[i], b[i]);
		}
	}
	int maksi = max(a[2*n-1], b[2*n-1]);
	for (int i=2*n-2; i >= 0; i--) {
		if (a[i] > maksi && b[i] > maksi) {
			ne();
			return 0;
		}
		if (a[i] > maksi) {
			a[i] = -1;
			maksi = b[i];
		}
		else if (b[i] > maksi) {
			b[i] = -1;
			maksi = a[i];
		}
		else {
			maksi = max(a[i], b[i]);
		}
		if (a[i] == -1 && b[i] == -1) {
			ne();
			return 0;
		}
	}
	int a1 = 1e9+1, b1 = 1e9+1;
	for (int i=0;i<2*n;i++) {
		if (a[i] == -1) res -= 1;
		else if (b[i] == -1) res += 1;
		else {
			if (a1 <= a[i] && a1 <= b[i] && b1 <= b[i] && a1 <= b[i]) {
				br++;
				v[br].pb(i);
				a1 = a[i];
				b1 = b[i];
			}
			else {
				v[br].pb(i);
				a1 = a[i];
				b1 = b[i];
			}
		}
	}
	br++;
	for (int i=0;i<br;i++) {
		int siz = v[i].size();
		for (int j=0;j<siz;j++) {
			int x = v[i][j];
			if (a[x] < b[x]) {
				s1[i].pb(1);
				koji1[i].pb(1);
				s2[i].pb(-1);
				koji2[i].pb(-1);
			}
			else {
				s1[i].pb(-1);
				koji1[i].pb(-1);
				s2[i].pb(1);
				koji2[i].pb(1);
			}
		}
		for (int j=1;j<siz;j++) {
			s1[i][j] += s1[i][j-1];
		}
		for (int j=siz-2;j>=0;j--) {
			s2[i][j] += s2[i][j+1];
		}
		int manji, veci;
		veci = max(s2[i][0], s1[i][siz-1]);
		manji = min(s2[i][0], s1[i][siz-1]);
		for (int j=1;j<siz;j++) {
			int sada = s2[i][j] + s1[i][j-1];
			veci = max(sada, veci);
			manji = min(sada, manji);
		}
		mali[i] = manji;
		veliki[i] = veci;
		uzeo[i] = manji;
		res += manji;
	}
	if (res % 2 == 1 || res > 0) {
		ne();
		return 0;
	}
	for (int i=0;i<br;i++) {
		int uzmi = veliki[i] - mali[i];
		uzmi = min(uzmi, -res);
		uzeo[i] = mali[i] + uzmi;
		res += uzmi;
	}
	if (res != 0) {
		ne();
		return 0;
	}
	for (int i=0;i<br;i++) {
		int siz = v[i].size();
		int c = uzeo[i];
		if (s1[i][siz-1] == c) {
			for (int j=0;j<siz;j++) {
				sol[v[i][j]] = koji1[i][j];
			}
			continue;
		}
		if (s2[i][0] == c) {
			for (int j=0;j<siz;j++) {
				sol[v[i][j]] = koji2[i][j];
			}
			continue;
		}
		for (int j=1;j<siz;j++) {
			if (s2[i][j] + s1[i][j-1] == c) {
				for (int k=0;k<j;k++) {
					sol[v[i][j]] = koji1[i][k];
				}
				for (int k=j;k<siz;k++) {
					sol[v[i][j]] = koji2[i][k];
				}
				break;
			}
		}
	}
	for (int i=0;i<2*n;i++) {
		if (a[i] == -1) cout << "B";
		else if (b[i] == -1) cout << "A";
		else if (sol[i] == -1) cout << "B";
		else if (sol[i] == 1) cout << "A";
	}
	return 0;
}

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