Submission #1000355

#	Time	Username	Problem	Language	Result	Execution time	Memory
1000355		MarwenElarbi	Building 4 (JOI20_building4)	C++17	100 / 100	515 ms	45384 KiB

building4

#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define ll long long
#define pb push_back
#define ii pair<int,int>
const int nax=1e6+5;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int dp[2][nax][2];
int tab[2][nax];
int main() {
    int n;
    cin>>n;
    n*=2;
    for (int i = 0; i < 2; ++i)
    {
        for (int j = 1; j <= n; ++j)
        {
            cin>>tab[i][j];
        }
    }
    for (int i = 1; i <= n; ++i)
    {
        for (int j = 0; j < 2; ++j)
        {
            dp[j][i][0]=n+1;
            dp[j][i][1]=-1;
            for (int k = 0; k < 2; ++k)
            {
                if(tab[j][i]>=tab[k][i-1]){
                    dp[j][i][0]=min(dp[j][i][0],dp[k][i-1][0]+j);
                    dp[j][i][1]=max(dp[j][i][1],dp[k][i-1][1]+j);
                }
            }
        }
    }
    int lst=-1;
    for (int i = 0; i < 2; ++i)
    {
        if(dp[i][n][0]<=n/2&&n/2<=dp[i][n][1]){
            lst=i;
        }
    }
    if(lst<0){
        cout <<-1<<endl;
    }else{
        string ans="";
        int c=n/2;
        while(n){
            ans.pb(char('A'+lst));
            c-=lst;
            lst=(tab[1][n-1]<=tab[lst][n]&&dp[1][n-1][0]<=c&&c<=dp[1][n-1][1]);
            n--;
        }
        reverse(ans.begin(),ans.end());
        cout <<ans<<endl;
    }
}

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