oj.uz

Submission #958315

# Submission time Handle Problem Language Result Execution time Memory
958315 2024-04-05T11:40:18 Z Vladth11 Building 4 (JOI20_building4) C++14
0 / 100
 1 ms 6492 KB 
#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 == NEUTRU)
        return b;
    if(b == NEUTRU)
        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){
        cout << -1;
        return 0;
    }
    int unde = 2 * n;
    int ta = n;
    int tb = n;
    string sol = "";
    int lst = 0;
    while(unde >= 1){
        if(ta > 0 && (dpa[unde].first <= tb && dpa[unde].second >= tb) && (dpa[unde] != NEUTRU) && 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

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

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Incorrect 1 ms 6488 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 89.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Incorrect 1 ms 6488 KB Output isn't correct
4 Halted 0 ms 0 KB -