제출 #211816

#제출 시각아이디문제언어결과실행 시간메모리
211816Evirir건물 4 (JOI20_building4)C++17
0 / 100
5 ms384 KiB
#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace std; using namespace __gnu_pbds; #define watch(x) cout<<(#x)<<"="<<(x)<<'\n' #define mset(d,val) memset(d,val,sizeof(d)) #define setp(x) cout<<fixed<<setprecision(x) #define forn(i,a,b) for(int i=a;i<b;i++) #define fore(i,a,b) for(int i=a;i<=b;i++) #define pb push_back #define F first #define S second #define INF ll(1e9) #define MOD 998244353 #define pqueue priority_queue #define fbo find_by_order #define ook order_of_key typedef long long ll; typedef pair<int,int> ii; typedef vector<ll> vi; typedef vector<ii> vii; typedef long double ld; typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> pbds; #define MAXN 1000005 void amin(ii &a, ii b){ a=ii(min(a.F,b.F),min(a.S,b.S)); } string str(int x){ if(x>=INF) return "INF"; return to_string(x); } int n; int a[MAXN][2]; int dp[MAXN][2][2]; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cin>>n; n<<=1; forn(j,0,2) forn(i,0,n) cin>>a[i][j]; forn(i,0,n) forn(j,0,2) forn(k,0,2) dp[i][j][k]=INF; forn(j,0,2) forn(k,0,2){ dp[0][j][k]=(j==k); } forn(i,1,n) forn(j,0,2) forn(k,0,2) { if(a[i-1][k]<=a[i][j] && dp[i-1][k][j]<n/2){ dp[i][j][j]=min(dp[i][j][j], dp[i-1][k][j]+1); dp[i][j][j^1]=min(dp[i][j][j^1], dp[i-1][k][j^1]); } } if(min(dp[n-1][0][0],dp[n-1][1][0])>=INF){ cout<<-1<<'\n'; return 0; } /*else cout<<"OK\n"; forn(j,0,2){ forn(i,0,n) cout<<"("<<str(dp[i][j][0])<<","<<str(dp[i][j][1])<<") "; cout<<'\n'; }*/ int cnta=0,cntb=0; forn(i,0,n){ if(dp[i][0][0]>=INF) cntb++; if(dp[i][1][0]>=INF) cnta++; } forn(i,0,n){ if(dp[i][0][0]<INF && cnta<n/2){ cout<<'A'; cnta++; } else{ cout<<'B'; cntb++; } } cout<<'\n'; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...