Submission #673087

#	Time	Username	Problem	Language	Result	Execution time	Memory
673087		Carmel_Ab1	Building 4 (JOI20_building4)	C++17	0 / 100	2 ms	1236 KiB

building4

/*
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
 */
#include<bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>

//using namespace __gnu_pbds;
using namespace std;

typedef long double ld;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int>vi;
typedef vector<vector<int>>vvi;
typedef vector<ll>vl;
typedef vector<vl> vvl;
typedef pair<int,int>pi;
typedef pair<ll,ll> pl;
typedef vector<pl> vpl;
typedef vector<ld> vld;
typedef pair<ld,ld> pld;
typedef vector<pi> vpi;

//typedef tree<ll, null_type, less_equal<ll>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
template<typename T> ostream& operator<<(ostream& os, vector<T>& a){os<<"[";for(int i=0; i<ll(a.size()); i++){os << a[i] << ((i!=ll(a.size()-1)?" ":""));}os << "]\n"; return os;}

#define all(x) x.begin(),x.end()
#define YES out("YES")
#define NO out("NO")
#define out(x){cout << x << "\n"; return;}
#define outfl(x){cout << x << endl;return;}
#define GLHF ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
#define print(x){for(auto ait:x) cout << ait << " "; cout << "\n";}
#define pb push_back
#define umap unordered_map


template<typename T>
void read(vector<T>& v){
    int n=v.size();
    for(int i=0; i<n; i++)
        cin >> v[i];
}
template<typename T>
vector<T>UNQ(vector<T>a){
    vector<T>ans;
    for(T t:a)
        if(ans.empty() || t!=ans.back())
            ans.push_back(t);
    return ans;
}



void solve();
int main(){
    GLHF;
    int t=1;
    //cin >> t;
    while(t--)
        solve();
}
void solve() {
    int n;
    cin >> n;
    vvi a(2*n+1,vi(2));
    for(int j=0; j<2; j++)
        for(int i=1; i<=2*n; i++)
            cin >> a[i][j];

    vector<vvi> dp(2*n+1,vvi(2,vi(2,-1e9)));
    for(int i:{0,1})for(int j:{0,1})dp[0][i][j]=0;

    //dp[i][j][k] = max appearances of sequence j, at the first i terms, where the sequence k it the last used

    for(int i=1; i<=2*n; i++){
        for(int j=0; j<=1; j++)
            for(int k=0; k<=1; k++)
                for(int lst=0; lst<=1; lst++){
                    if(a[i][k]<a[i-1][lst])continue;
                    //a[i][k] >= a[i-1][lst]
                    if(j!=k)
                        dp[i][j][k] = max(dp[i][j][k], dp[i-1][j][lst]);
                    else
                        dp[i][j][k] = max(dp[i][j][k],dp[i-1][j][lst]+1);
                }
    }
    if(*max_element(all(dp[2*n][0]))<n || *max_element(all(dp[2*n][1]))<n)out(-1)

    string ans(2*n+1,'A');

    int a_left=n,b_left=n;
    int lst=0;
    a.pb({INT_MAX,INT_MAX});

    for(int i=2*n; i>=1; i--){
        bool pick_a=true;

        //dp[i][1][0] = max B's if I take now an A
        if(dp[i][1][0]<b_left || !a_left || a[i][0]>a[i+1][lst])
            pick_a = false;
        if(pick_a)
            ans[i]='A',a_left--,lst=0;
        else
            ans[i]='B',b_left--,lst=1;
    }

    ans=ans.substr(1,2*n);
    out(ans)
}
/*
3
 2 5 4 9 15 11
 6 7 6 8 12 14

 2
1 4 10 20
3 5 8 13

2
 3 4 5 6
 10 9 8 7

 6
 25 18 40 37 29 95 41 53 39 69 61 90
 14 18 22 28 18 30 32 32 63 58 71 78
 */

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