Submission #212738

#	Time	Username	Problem	Language	Result	Execution time	Memory
212738		someone_aa	Building 4 (JOI20_building4)	C++17	100 / 100	1237 ms	45676 KiB

building4

#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define mp make_pair
using namespace std;
const int maxn = 500100;
const int inf = 1e7;
int a[2*maxn], b[2*maxn];
int dpmax[2*maxn][2], dpmin[2*maxn][2];
int n;

int main() {
	cin>>n;
	for(int i=1;i<=2*n;i++) {
		cin>>a[i];
	}
	for(int i=1;i<=2*n;i++) {
		cin>>b[i];
	}

	dpmin[1][0] = dpmax[1][0] = 1;
	dpmin[1][1] = dpmax[1][1] = 0;

	for(int i=2;i<=2*n;i++) {
		dpmin[i][0] = inf;
		dpmax[i][0] = 0;
		if(a[i] >= a[i-1]) {
			dpmin[i][0] = min(dpmin[i-1][0] + 1, dpmin[i][0]);
			dpmax[i][0] = max(dpmax[i-1][0] + 1, dpmax[i][0]);
		}
		if(a[i] >= b[i-1]) {
			dpmin[i][0] = min(dpmin[i][0], dpmin[i-1][1] + 1);
			dpmax[i][0] = max(dpmax[i][0], dpmax[i-1][1] + 1);
		}

		dpmin[i][1] = inf;
		dpmax[i][1] = 0;
		if(b[i] >= b[i-1]) {
			dpmin[i][1] = min(dpmin[i-1][1], dpmin[i][1]);
			dpmax[i][1] = max(dpmax[i-1][1], dpmax[i][1]);
		}
		if(b[i] >= a[i-1]) {
			dpmin[i][1] = min(dpmin[i][1], dpmin[i-1][0]);
			dpmax[i][1] = max(dpmax[i][1], dpmax[i-1][0]);
		}
	}

	if(!(dpmin[2*n][0]<=n && dpmax[2*n][0]>=n) && !(dpmin[2*n][1]<=n && dpmax[2*n][1]>=n)) {
		cout<<"-1\n";
		return 0;
	}


	if(dpmin[2*n][0] <= n && dpmax[2*n][0]>=n) {
		// last is "A"
		string result = "A";
		int lft = n - 1;
		bool lst = false;
		for(int i=2*n-1;i>=1;i--) {

			// if we put B on this position, can we put lft A's behind me

			/*cout<<"At position: "<<i<<" there are "<<lft<<"\n";
			cout<<"With A: "<<dpmin[i][0]<<" and "<<dpmax[i][0]<<"\n";
			cout<<"With B: "<<dpmin[i][1]<<" and "<<dpmax[i][1]<<"\n"; */

			bool nlst;
			if(!lst) {
				if(b[i] <= a[i+1] && dpmin[i][1] <= lft && dpmax[i][1] >= lft) {
					result += 'B';
					nlst = true;
					//cout<<"Adding B\n";
				}
				else if(a[i] <= a[i+1] && dpmin[i][0] <= lft && dpmax[i][0] >= lft && lft >= 1) {
					result += 'A';
					nlst = false;
					lft--;
					//cout<<"Adding A\n";
				}
			}
			else {
				if(b[i] <= b[i+1] && dpmin[i][1] <= lft && dpmax[i][1] >= lft) {
					result += 'B';
					nlst = true;
					//cout<<"Adding B\n";
				}
				else if(a[i] <= b[i+1] && dpmin[i][0] <= lft && dpmax[i][0] >= lft && lft >= 1) {
					result += 'A';
					nlst = false;
					lft--;
					//cout<<"Adding A\n";
				}
			}
			lst = nlst;
		}

		reverse(result.begin(), result.end());
		cout<<result<<"\n";
	}
	else if(dpmin[2*n][1] <= n && dpmax[2*n][1]>=n) {
		// last is "A"
		string result = "B";
		int lft = n;
		bool lst = true;
		for(int i=2*n-1;i>=1;i--) {

			// if we put B on this position, can we put lft A's behind me

			/*cout<<"At position: "<<i<<" there are "<<lft<<"\n";
			cout<<"With A: "<<dpmin[i][0]<<" and "<<dpmax[i][0]<<"\n";
			cout<<"With B: "<<dpmin[i][1]<<" and "<<dpmax[i][1]<<"\n"; */

			bool nlst;
			if(!lst) {
				if(b[i] <= a[i+1] && dpmin[i][1] <= lft && dpmax[i][1] >= lft) {
					result += 'B';
					nlst = true;
					//cout<<"Adding B\n";
				}
				else if(a[i] <= a[i+1] && dpmin[i][0] <= lft && dpmax[i][0] >= lft && lft >= 1) {
					result += 'A';
					nlst = false;
					lft--;
					//cout<<"Adding A\n";
				}
			}
			else {
				if(b[i] <= b[i+1] && dpmin[i][1] <= lft && dpmax[i][1] >= lft) {
					result += 'B';
					nlst = true;
					//cout<<"Adding B\n";
				}
				else if(a[i] <= b[i+1] && dpmin[i][0] <= lft && dpmax[i][0] >= lft && lft >= 1) {
					result += 'A';
					nlst = false;
					lft--;
					//cout<<"Adding A\n";
				}
			}
			lst = nlst;
		}

		reverse(result.begin(), result.end());
		cout<<result<<"\n";
	}
}

Compilation message (stderr)

building4.cpp: In function 'int main()':
building4.cpp:114:4: warning: 'nlst' may be used uninitialized in this function [-Wmaybe-uninitialized]
    if(!lst) {
    ^~
building4.cpp:68:4: warning: 'nlst' may be used uninitialized in this function [-Wmaybe-uninitialized]
    if(!lst) {
    ^~

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