Submission #237174

#	Time	Username	Problem	Language	Result	Execution time	Memory
237174		hackermub	Building 4 (JOI20_building4)	C++17	0 / 100	6 ms	512 KiB

building4

#include<bits/stdc++.h>
using namespace std;

#define int long long
#define pii pair<int,int>
#define INF (int)1e18
#define all(v) v.begin(), v.end()

const int MAXN =5e5+7;
int n;
int dp[MAXN][2][2]; // min and max A if ith bit=j
int ara[2][MAXN];

void min_self(int &x,int y){
    x=min(x,y);
}

void max_self(int &x,int y){
    x=max(x,y);
}

int32_t main(){
    ios_base::sync_with_stdio(false),cin.tie(),cout.tie();
    // If you hack my code, you are gay
    cin>>n;
    int N=2*n;
    for(auto x:{0,1}){
        for(int i=0;i<N;i++){
             cin>>ara[x][i];
             dp[i][x][0]=INF;
             dp[i][x][1]=0;
        }
    }

    dp[0][0][0]=dp[0][0][1]=1;
    dp[0][1][0]=dp[0][1][1]=0;
    for(int i=1;i<N;i++){
        for(auto x:{0,1}){
            if(ara[x][i-1]<=ara[0][i]){
                min_self(dp[i][0][0],dp[i-1][x][0]+1);
                max_self(dp[i][0][1],dp[i-1][x][1]+1);
            }
            if(ara[x][i-1]<=ara[1][i]){
                min_self(dp[i][1][0],dp[i-1][x][0]);
                max_self(dp[i][1][1],dp[i-1][x][1]);
            }
        }
    }
    string ans;
    int rem=n;
    int last;
    for(int i=N-1;i>=0;i--){
        char ch='A';
        if(dp[i][0][0]<=rem && rem<=dp[i][0][1] && (i==N-1 || ara[0][i]<=ara[last][i+1])){
            rem--;
            last=0;
        }else if(dp[i][1][0]<=rem && rem<=dp[i][1][1] && (i==N-1) || ara[1][i]<=ara[last][i+1]){
            last=1;
            ch='B';
        }else{
            cout<<-1;
            return 0;
        }
        ans.push_back(ch);
    }
    reverse(all(ans));
    cout<<ans;
    return 0;
}

Compilation message (stderr)

building4.cpp: In function 'int32_t main()':
building4.cpp:57:55: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
         }else if(dp[i][1][0]<=rem && rem<=dp[i][1][1] && (i==N-1) || ara[1][i]<=ara[last][i+1]){
                  ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~
building4.cpp:51:9: warning: 'last' may be used uninitialized in this function [-Wmaybe-uninitialized]
     int last;
         ^~~~

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