Submission #543624

#	Time	Username	Problem	Language	Result	Execution time	Memory
543624		Cookie197	Building 4 (JOI20_building4)	C++17	11 / 100	219 ms	29276 KiB

building4

// Cookie197 
// the people who invented competitive programming must be ******* crazy
// why am i still here suffering while i can do something else more valuable?
// WHY???
#pragma GCC optimize("O4,unroll-loops,no-stack-protector")
#pragma GCC optimize("Ofast")
//#pragma GCC target("avx,avx2,fma")
#include<iostream>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<string>
#include<iomanip>
#include<math.h>
#include<unordered_map>
#include<numeric>
#include<random>
using namespace std;
#define Why_does_competitive_programming_even_exist ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define ll long long
#define pii pair<int,int>
#define pdd pair<double ,double>
#define mp make_pair
//#define mod 998244353
#define mod 1000000007
#define endl "\n"
#define inf (ll)1e18
#define out(x) cout << #x << " = " << x <<endl;
#define out2(a,b) cout<< #a << "[" << b << "]" << " = " << a[b] << endl;
#define outp(x) cout << #x << " first = " << x.first << "  second = " << x.second << endl

int a[1000006], b[1000006], arr[100006][2];
int n;
//bool ok[1000005][2];
//int dpx[1000005][2], dpy[1000005][2];
//char pre[1000005][2];
pii dp[1000005][2];
void ch(int &x,int y,int z,int i,int j){
    //if (y<0) y = 1e9;
    //if (z<0) z = 1e9;
    //x = min(x,min(y,z));
    //if (y==z && y==1e9) return;
    //if (y<z) pre[i][j] = 'A';
    //else pre[i][j] = 'B';
}
signed main(){
    Why_does_competitive_programming_even_exist;
    cin>>n;
    for (int i=1;i<=2*n;i++) cin>>a[i], arr[i][0] = a[i];
    for (int i=1;i<=2*n;i++) cin>>b[i], arr[i][1] = b[i];

    //ok[1][0] = ok[1][1] = true;
    dp[1][0] = mp(1,1), dp[1][1] = mp(0,0);
    for (int i=2;i<=n*2;i++) dp[i][0] = mp(1e9,-1);

    for (int i=2;i<=n*2;i++){
        int x=1e9, y=1e9;
        if (a[i-1] <= a[i]) x = dp[i-1][0].first;
        if (b[i-1] <= a[i]) y = dp[i-1][1].first;
        dp[i][0].first = min(x,y) + 1;

        x = -1e9, y = -1e9;
        if (a[i-1] <= a[i]) x = dp[i-1][0].second;
        if (b[i-1] <= a[i]) y = dp[i-1][1].second;
        dp[i][0].second = max(x,y) + 1;

        x=1e9, y=1e9;
        if (a[i-1] <= b[i]) x = dp[i-1][0].first;
        if (b[i-1] <= b[i]) y = dp[i-1][1].first;
        dp[i][1].first = min(x,y);

        x = -1e9, y = -1e9;
        if (a[i-1] <= b[i]) x = dp[i-1][0].second;
        if (b[i-1] <= b[i]) y = dp[i-1][1].second;
        dp[i][1].second = max(x,y);

        //outp(dp[i][0]); outp(dp[i][1]);
    }

    int pos = -1, now = n;
    if (dp[n*2][0].first <= n && n <= dp[n*2][0].second) pos = 0;
    else if (dp[n*2][1].first <= n && n <= dp[n*2][1].second) pos = 1;
    if (pos == -1){
        cout<<-1<<endl;
        return 0;
    }

    string ans = "";
    for (int i=n*2;i>=1;i--){
        ans += (pos==0 ? 'A' : 'B');
        now -= (pos==0 ? 1 : 0);
        if (arr[i-1][0] <= arr[i][pos] && dp[i-1][0].first <= now && now <= dp[i-1][0].second) pos = 0;
        else if (arr[i-1][1] <= arr[i][pos] && dp[i-1][1].first <= now && now <= dp[i-1][1].second) pos = 1;
    }
    reverse(ans.begin(),ans.end());
    cout<<ans<<endl;
    /*dpx[1][0] = 1; dpy[1][1] = 1;
    for (int i=1;i<2*n;i++){
        if (ok[i][0] && a[i] <= a[i+1]){
            ch(dpx[i+1][0], dpx[i][0] + 1, -(dpy[i][0] - 1), i+1, 0);
            ch(dpy[i+1][0], dpy[i][0] - 1, -(dpx[i][0] + 1), i+1, 0);
            ok[i+1][0] = true;
        }
        if (ok[i][1] && b[i] <= a[i+1]){
            ch(dpx[i+1][0], dpx[i][1] + 1, -(dpy[i][1] - 1), i+1, 0);
            ch(dpy[i+1][0], dpy[i][1] - 1, -(dpx[i][1] + 1), i+1, 0);
            ok[i+1][0] = true;
        }
        if (ok[i][0] && a[i] <= b[i+1]){
            ch(dpx[i+1][1], dpx[i][0] - 1, -(dpy[i][0] + 1), i+1, 1);
            ch(dpy[i+1][1], dpy[i][0] + 1, -(dpx[i][0] - 1), i+1, 1);
            ok[i+1][1] = true;
        }
        if (ok[i][1] && b[i] <= b[i+1]){
            ch(dpx[i+1][1], dpx[i][1] - 1, -(dpy[i][1] + 1), i+1, 1);
            ch(dpy[i+1][1], dpy[i][1] + 1, -(dpx[i][1] - 1), i+1, 1);
            ok[i+1][1] = true;
        }
    }

    for (int i=1;i<=n*2;i++){
        cout<<dpx[i][0]<<" "<<dpx[i][1]<<"  "<<dpy[i][0]<<" "<<dpy[i][1]<<endl;
    }

    //return 0;
    if (ok[2*n][0] == false && ok[2*n][1] == false) {
        cout<<-1<<endl;
        return 0;
    }
    if (dpx[2*n][0] != 0 && dpx[2*n][1] != 0 && dpy[2*n][0] != 0 && dpy[2*n][1] != 0) {
        cout<<-1<<endl;
        return 0;
    }

    string ans = "";
    int pos;
    if (ok[n][0]) ans += 'A', pos = 0;
    else ans += 'B', pos = 1;
    for (int i=2*n;i>=2;i--){
        ans += pre[i][pos];
        if (pre[i][pos]=='A') pos = 0;
        else pos = 1;
    }
    reverse(ans.begin(),ans.end());
    cout<<ans<<endl;*/
}

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