Submission #1351441

#TimeUsernameProblemLanguageResultExecution timeMemory
1351441piolkBuilding 4 (JOI20_building4)C++20
11 / 100
2095 ms62820 KiB
#include <bits/stdc++.h>
using namespace std;

bool tab[4005][4005][2];
bool bt[4005][4005][2];

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int n;
    cin>>n;

    vector<vector<int>> vec(2*n,vector<int>(2));
    for (int i=0;i<2;i++){
        for (int j=0;j<2*n;j++){
            cin>>vec[j][i];
        }
    }

    tab[0][0][0]=true;
    tab[0][1][1]=true;

    for (int i=1;i<2*n;i++){
        for (int j=0;j<2*n;j++){
            for (int k=0;k<2;k++){
                if (j-k<0) continue;
                if (vec[i][k]>=vec[i-1][k]){
                    tab[i][j][k]|=tab[i-1][j-k][k];
                    if (tab[i-1][j-k][k]) bt[i][j][k]=k;
                } 
                if (vec[i][k]>=vec[i-1][k^1]){
                    tab[i][j][k]|=tab[i-1][j-k][k^1];
                    if (tab[i-1][j-k][k^1]) bt[i][j][k]=k^1;
                } 
            }
        }
    }

    if (tab[2*n-1][n][0]==0 && tab[2*n-1][n][1]==0){
        cout<<-1<<"\n";
        return 0;
    }

    string s;

    vector<int> state(3);
    if (tab[2*n-1][n][0]) state={2*n-1,n,0};
    else state={2*n-1,n,1};

    while (state[0]>=0){
        int i=state[0],b=state[1],k=state[2];
        s+=(k==0 ? 'A' : 'B');
        state={i-1,b-k,bt[i][b][k]};
    }

    reverse(s.begin(),s.end());
    cout<<s<<"\n";

    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...