제출 #237176

#제출 시각아이디문제언어결과실행 시간메모리
237176hackermub건물 4 (JOI20_building4)C++17
11 / 100
117 ms40184 KiB
#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; } } ara[0][N]=INF; 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=0; 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; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...