Submission #1061930

#	Time	Username	Problem	Language	Result	Execution time	Memory
1061930		phong	Building 4 (JOI20_building4)	C++17	100 / 100	238 ms	128448 KiB

building4

#include<bits/stdc++.h>

#define ll long long
const int nmax = 1e6 + 5, N = 1e6;
const ll oo = 1e18 + 1, base = 311;
const int lg = 19, M = 10;
const ll mod = 1e9 + 2277, mod2 = 1e9 + 5277;
#define pii pair<int, int>
#define fi first
#define se second
#define endl "\n"
#define debug(a, n) for(int i = 1; i <= n; ++i) cout << a[i] << ' '; cout << "\n";
using namespace std;

int n, a[nmax][2], b[nmax];
int dp[nmax][2][2], F[nmax][2][2];
bool check(int i, int t, int x, int idx){
    if(i == 0) return 1;
    return F[i][t][idx] >= x && dp[i][t][idx] <= x;
}
vector<int> ans;
void trace(int i, int ta, int tb, int idx){
    ans.push_back(idx);
//    cout << ta << ' ' << tb << endl;
    if(i == 1) return;
    for(int x = 0; x < 2;++x){
        int cur;
        if(x == 0) cur = ta - (idx == 0);
        else cur = tb - (idx == 1);
        if(a[i - 1][x] <= a[i][idx] && check(i - 1, x, cur, x)){
            trace(i - 1, ta - (idx == 0), tb - (idx == 1), x);
            return;
        }
    }
}
main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
//    freopen("code.inp", "r", stdin);
//    freopen("code.out", "w", stdout);
    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];
    memset(dp, 0x3f, sizeof dp);
    memset(F, -63, sizeof F);
    for(int idx = 0; idx < 2; ++idx){
        for(int x = 0; x < 2; ++x){
            dp[0][x][idx] = 0;
            F[0][x][idx] = 0;
        }
    }
    for(int i = 1; i <= n; ++i){
        for(int x = 0; x < 2; ++x){
            for(int y = 0; y < 2; ++y){
                if(a[i - 1][x] > a[i][y]) continue;
                for(int idx = 0; idx < 2; ++idx){
                    F[i][y][idx] = max(F[i - 1][x][idx] + (y == idx), F[i][y][idx]);
                    dp[i][y][idx] = min(dp[i - 1][x][idx] + (y == idx), dp[i][y][idx]);
                }
            }
        }
    }
//    cout <<dp[3][1];
    if(check(n, 0, n / 2, 0)){
        trace(n, n / 2, n / 2, 0);
    }
    else if(check(n, 1, n / 2, 1)){
//        cout << "?";
        trace(n, n / 2, n / 2, 1);
    }
    else cout << -1, exit(0);
    reverse(ans.begin(), ans.end());
    for(auto p : ans){
        if(p == 0) cout << "A";
        else cout << "B";
    }

}
/*

3
1 2 3 4 5 6
7 8 9 10 11
*/

Compilation message (stderr)

building4.cpp:36:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   36 | main(){
      | ^~~~

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