Submission #473619

#	Time	Username	Problem	Language	Result	Execution time	Memory
473619		keta_tsimakuridze	Building 4 (JOI20_building4)	C++14	100 / 100	543 ms	78372 KiB

building4

#include<bits/stdc++.h>
#define f first
#define s second
#define pii pair<int,int>
using namespace std;
const int N = 1e6 + 5, mod = 1e9 + 7; // !
int t, a[N], b[N], n, c[N], pos[N];
map<int,int> id;
main(){
	ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin >> n;
	n *= 2;
	for(int i = 1; i <= n; i++) cin >> a[i];
	for(int i = 1; i <= n; i++) cin >> b[i];
	int sum  = 0;
	for(int i = 1; i <= n; i++) {
		if(c[i - 1] > max(a[i],b[i]))  {
			cout << -1;
			return 0;
		}
		if(c[i - 1] > min(a[i],b[i])) {
			c[i] = max(a[i],b[i]);
			if(a[i] < b[i]) pos[i] = 1;
			else pos[i] = -1;
		}
		else {
			c[i] = min(a[i],b[i]);
			if(a[i] < b[i]) pos[i] = -1;
			else pos[i] = 1;
		}
		sum += pos[i];
	}
	int changed = 0;
	if(sum > 0) {
		changed = 1;
		swap(a,b);
		for(int i = 1; i <= n; i++) {
			pos[i] *= - 1;
		}
		sum = -sum;
	}
	sum = -sum;
	for(int i = 1; i <= n; i++) {
		int j = i; 
		if(c[j] == max(a[j],b[j]) && a[j] != b[j]) continue;
		int f = 0;
		while(j < n) {
			if(max(a[j + 1],b[j + 1]) < max(a[j],b[j])) {
				f = 1; break;
			}
			if(max(a[j],b[j]) <= c[j + 1]) {
				break;
			}
			else j++;
		}
		if(!f) { 
			int max_ = 0, cur = 0;
			id.clear();
			id[0] = j + 1;
			for(int k = j; k >= i; k--) {
				cur += -2 * pos[k];
				id[cur] = k;
				if(cur > max_) {
					max_ = cur;
				} 
			}
			if (max_ <= sum) {
				sum -= max_;
				for(int k = j; k >= id[max_]; k--) {
					pos[k] *= -1;
				}
			}
			else {
				for(int k = j; k >= id[sum]; k--) {
					pos[k] *= -1;
				}
				sum = 0;
			}	
		}
		i = j;
	}
	if(sum) {
		cout << -1;
		return 0;
	}
	sum = 0;
	for(int i = 1; i <= n; i++) {
		if(changed) pos[i] *= -1;
		if(pos[i] == 1) cout << 'B';
		else cout << 'A';
		sum += pos[i];
	}
}

Compilation message (stderr)

building4.cpp:9:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
    9 | main(){
      | ^~~~

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