Submission #611952

#	Time	Username	Problem	Language	Result	Execution time	Memory
611952		alireza_kaviani	Building 4 (JOI20_building4)	C++17	100 / 100	333 ms	44336 KiB

building4

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

typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;

#define all(x)      (x).begin(),(x).end()
#define X           first
#define Y           second
#define sep         ' '
#define endl        '\n'
#define SZ(x)       ll(x.size())

const ll MAXN = 1e6 + 10;
const ll LOG = 22;
const ll INF = 8e18;
const ll MOD = 1e9 + 7; //998244353; //1e9 + 9;

int n , A[MAXN][2] , mn[MAXN][2] , mx[MAXN][2];

int main() {
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

    cin >> n; n *= 2;
    for(int i = 1 ; i <= n ; i++){
        cin >> A[i][0];
    }
    for(int i = 1 ; i <= n ; i++){
        cin >> A[i][1];
    }

    mn[n][0] = mx[n][0] = 1;
    mn[n][1] = mx[n][1] = -1;
    for(int i = n - 1 ; i >= 1 ; i--){
        for(int j = 0 ; j < 2 ; j++){
            mn[i][j] = MOD; mx[i][j] = -MOD;
            for(int k = 0 ; k < 2 ; k++){
                if(A[i][j] > A[i + 1][k])   continue;
                mn[i][j] = min(mn[i][j] , mn[i + 1][k] + 1 - j * 2);
                mx[i][j] = max(mx[i][j] , mx[i + 1][k] + 1 - j * 2);
            }
        }
    }

    if((0 < mn[1][0] || mx[1][0] < 0) && (0 < mn[1][1] || mx[1][1] < 0)){
        return cout << -1 << endl , 0;
    }
    int last = -MOD , cur = 0;
    for(int i = 1 ; i <= n ; i++){
        int ind = -1;
        for(int j = 0 ; j < 2 ; j++){
            if(last <= A[i][j] && mn[i][j] <= cur && cur <= mx[i][j]){
                ind = j;
                break;
            }
        }
        last = A[i][ind];
        cur += ind * 2 - 1;
        cout << char(65 + ind);
    }

    return 0;
}
/*

*/

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