Submission #958354

#	Time	Username	Problem	Language	Result	Execution time	Memory
958354		Vladth11	Building 4 (JOI20_building4)	C++14	100 / 100	196 ms	69076 KiB

building4

#include <bits/stdc++.h>
#define debug(x) cerr << #x << " " << x << "\n"
#define debugs(x) cerr << #x << " " << x << " "
#pragma GCC optimize ("Ofast")
#pragma GCC target ("avx2")

#define int ll

using namespace std;
typedef long long ll;
typedef pair <ll, ll> pii;

const ll NMAX = 1000001;
const ll INF = 1e9;
const ll nrbits = 20;
const ll MOD = 998244353;

int a[NMAX];
int b[NMAX];

pii dpa[NMAX];
pii dpb[NMAX];

const pii NEUTRU = {0, -1};

pii unite(pii a, pii b){
    if(a.first > a.second)
        return b;
    if(b.first > b.second)
        return a;
    return {min(a.first, b.first), max(a.second, b.second)};
}

signed main() {
#ifdef HOME
    ifstream cin(".in");
    ofstream cout(".out");
#endif // HOME
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    srand(time(0));
    int n, i, k;
    cin >> n;
    for(i = 1; i <= 2 * n; i++){
        cin >> a[i];
    }
    for(i = 1; i <= 2 * n; i++){
        cin >> b[i];
    }
    dpb[1] = {1, 1};
    dpa[1] = {0, 0};
    for(i = 2; i <= 2 * n; i++){
        dpa[i] = dpb[i] = NEUTRU;
        if(a[i] >= a[i - 1]){
            dpa[i] = unite(dpa[i], dpa[i - 1]);
        }
        if(a[i] >= b[i - 1]){
            dpa[i] = unite(dpa[i], dpb[i - 1]);
        }
        if(b[i] >= b[i - 1]){
            dpb[i] = unite(dpb[i], {dpb[i - 1].first + 1, dpb[i - 1].second + 1});
        }
        if(b[i] >= a[i - 1]){
            dpb[i] = unite(dpb[i], {dpa[i - 1].first + 1, dpa[i - 1].second + 1});
        }
    }
    if((dpb[2 * n].first > n || dpb[2 * n].second < n) && ((dpa[2 * n].first > n || dpa[2 * n].second < n))){
        cout << -1;
        return 0;
    }
    int unde = 2 * n;
    int ta = n;
    int tb = n;
    string sol = "";
    int lst = 2e9;
    while(unde >= 1){
        if(ta > 0 && ((dpa[unde].first <= tb && dpa[unde].second >= tb) || tb == 0) && a[unde] <= lst){
            ta--;
            sol += "A";
            lst = a[unde];
        }else{
            sol += "B";
            tb--;
            lst = b[unde];
        }

        unde--;
    }
    reverse(sol.begin(), sol.end());
    cout << sol;
    return 0;
}

Compilation message (stderr)

building4.cpp: In function 'int main()':
building4.cpp:43:15: warning: unused variable 'k' [-Wunused-variable]
   43 |     int n, i, k;
      |               ^

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