Submission #673095

#	Time	Username	Problem	Language	Result	Execution time	Memory
673095		Carmel_Ab1	Building 4 (JOI20_building4)	C++17	100 / 100	440 ms	247768 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});

    int cntA = n, cntB = n;
    int idx = 2*n, last = 0;

    while (cntA >= 1 || cntB >= 1)
    {
        if (a[idx][0] <= a[idx + 1][last] && dp[idx][0][0] >= cntA && dp[idx][1][0] >= cntB)
        {
            ans[idx - 1] = 'A';
            last = 0;
            cntA--;
            idx--;
            continue;
        }

        if (a[idx][1] <= a[idx + 1][last] && dp[idx][0][1] >= cntA && dp[idx][1][1] >= cntB)
        {
            ans[idx - 1] = 'B';
            last = 1;
            cntB--;
            idx--;
            continue;
        }

        std::cout << -1 << '\n';
        return;
    }

    ans.pop_back();
    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
 */

Compilation message (stderr)

building4.cpp: In function 'void solve()':
building4.cpp:95:9: warning: unused variable 'a_left' [-Wunused-variable]
   95 |     int a_left=n,b_left=n;
      |         ^~~~~~
building4.cpp:95:18: warning: unused variable 'b_left' [-Wunused-variable]
   95 |     int a_left=n,b_left=n;
      |                  ^~~~~~
building4.cpp:96:9: warning: unused variable 'lst' [-Wunused-variable]
   96 |     int lst=0;
      |         ^~~

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