Submission #212961

#	Time	Username	Problem	Language	Result	Execution time	Memory
212961		jovan_b	Building 4 (JOI20_building4)	C++17	100 / 100	348 ms	69868 KiB

building4

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;

const int INF = 1000000007;

int a[1000005];
int b[1000005];
pair <int, int> dp[1000005][2];

string res = "";

void uradi(int n, int koji, int kolko){
    if(n == 1){
        if(koji == 0) res += 'A';
        else res += 'B';
        return;
    }
    if(koji == 0){
        if(a[n] >= a[n-1] && dp[n-1][0].first <= kolko && dp[n-1][0].second >= kolko) uradi(n-1, 0, kolko-1);
        else uradi(n-1, 1, kolko);
        res += 'A';
    }
    else{
        if(b[n] >= a[n-1] && dp[n-1][0].first <= kolko && dp[n-1][0].second >= kolko) uradi(n-1, 0, kolko-1);
        else uradi(n-1, 1, kolko);
        res += 'B';
    }
}

int main(){
    ios_base::sync_with_stdio(false), cin.tie(0);
    cout.precision(10);
    cout << fixed;

	int n;
	cin >> n;
	for(int i=1; i<=2*n; i++){
        cin >> a[i];
	}
	for(int i=1; i<=2*n; i++){
        cin >> b[i];
	}
	for(int i=1; i<=2*n; i++){
        dp[i][0] = dp[i][1] = {INF, -INF};
        if(a[i] >= a[i-1]){
            dp[i][0].second = max(dp[i][0].second, dp[i-1][0].second+1);
            dp[i][0].first = min(dp[i][0].first, dp[i-1][0].first+1);
        }
        if(a[i] >= b[i-1]){
            dp[i][0].second = max(dp[i][0].second, dp[i-1][1].second+1);
            dp[i][0].first = min(dp[i][0].first, dp[i-1][1].first+1);
        }
        if(b[i] >= a[i-1]){
            dp[i][1].second = max(dp[i][1].second, dp[i-1][0].second);
            dp[i][1].first = min(dp[i][1].first, dp[i-1][0].first);
        }
        if(b[i] >= b[i-1]){
            dp[i][1].second = max(dp[i][1].second, dp[i-1][1].second);
            dp[i][1].first = min(dp[i][1].first, dp[i-1][1].first);
        }
	}
	if(dp[2*n][1].second >= n && dp[2*n][1].first <= n){
        uradi(2*n, 1, n);
        cout << res;
        return 0;
	}
	if(dp[2*n][0].second >= n && dp[2*n][0].first <= n){
        uradi(2*n, 0, n-1);
        cout << res;
        return 0;
	}
	cout << -1;
    return 0;
}
/*
1
1 2
1 2
*/

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