Submission #919654

#	Time	Username	Problem	Language	Result	Execution time	Memory
919654		OAleksa	Building 4 (JOI20_building4)	C++14	11 / 100	49 ms	19036 KiB

building4

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define f first
#define s second
const int N = 5e5 + 69;
const int inf = 1e9;
int n, a[N], b[N];
int mna1[N], mxa1[N], mna2[N], mxa2[N];
int mnb1[N], mxb1[N], mnb2[N], mxb2[N];
signed main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  int tt = 1;
  //cin >> tt;
  while (tt--) {
  	cin >> n;
  	n *= 2;
  	for (int i = 1;i <= n;i++)
  		cin >> a[i];
  	for (int i = 1;i <= n;i++)
  		cin >> b[i];
  	for (int i = 1;i <= n;i++) {
  		mna1[i] = mna2[i] = mnb1[i] = mnb2[i] = inf;
  		mxa1[i] = mxa2[i] = mxb1[i] = mxb2[i] = -inf;
  	}
  	mna1[1] = mxa1[1] = mnb2[1] = mxb2[1] = 1;
  	mna2[1] = mxa2[1] = mnb1[1] = mxb1[1] = 0;
  	for (int i = 2;i <= n;i++) {
  		if (a[i] >= a[i - 1]) {
  			mxa1[i] = max(mxa1[i], mxa1[i - 1] + 1);
  			mna1[i] = min(mna1[i], mna1[i - 1] + 1);
  			mxb1[i] = max(mxb1[i], mxb1[i - 1]);
  			mnb1[i] = min(mnb1[i], mnb1[i - 1]);
  		}
  		if (a[i] >= b[i - 1]) {
  			mxa1[i] = max(mxa1[i], mxa2[i - 1] + 1);
  			mna1[i] = min(mna1[i], mna2[i - 1] + 1);
  			mxb1[i] = max(mxb1[i], mxb2[i - 1]);
  			mnb1[i] = min(mnb1[i], mnb2[i - 1]);
  		}
  		if (b[i] >= a[i - 1]) {
  			mxa2[i] = max(mxa2[i], mxa1[i - 1]);
  			mna2[i] = min(mna2[i], mna1[i - 1]);
  			mxb2[i] = max(mxb2[i], mxb1[i - 1] + 1);
  			mnb2[i] = min(mnb2[i], mnb1[i - 1] + 1);
  		}
  		if (b[i] >= b[i - 1]) {
  			mxa2[i] = max(mxa2[i], mxa2[i - 1]);
  			mna2[i] = min(mna2[i], mna2[i - 1]);
  			mxb2[i] = max(mxb2[i], mxb2[i - 1] + 1);
  			mnb2[i] = min(mnb2[i], mnb2[i - 1] + 1);
  		}
  	}
  	if (((mna1[n] > n / 2 || mxa1[n] < n / 2) && (mnb1[n] > n / 2 || mxb1[n] < n / 2)) && ((mna2[n] > n / 2 || mxa2[n] < n / 2) && (mnb2[n] > n / 2 || mxb2[n] < n / 2)))
  		cout << "-1";
  	else {
  		string ans;
  		int x = n / 2, y = n / 2, lst = inf;
  		for (int i = n;i >= 1;i--) {
  			if (mna1[i] <= x && mxa1[i] >= x && a[i] <= lst) {
  				ans += 'A';
  				x--;
  				lst = a[i];
  			}
  			else if (mnb2[i] <= y && mxb2[i] >= y && b[i] <= lst) {
  				ans += 'B';
  				y--;
  				lst = b[i];
  			}
  		}
  		reverse(ans.begin(), ans.end());
  		cout << ans;
  	}
  }
  return 0;
}

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