제출 #707359

#제출 시각아이디문제언어결과실행 시간메모리
707359urosk건물 4 (JOI20_building4)C++14
100 / 100
276 ms67788 KiB
#define here cerr<<"===========================================\n" #define dbg(x) cerr<<#x<<": "<<x<<endl; #include "bits/stdc++.h" //#include <ext/pb_ds/tree_policy.hpp> //#include <ext/pb_ds/assoc_container.hpp> #define ld double #define ll long long #define llinf 100000000000000000LL // 10^17 #define pb push_back #define popb pop_back #define fi first #define sc second #define endl '\n' #define pll pair<ll,ll> #define pld pair<ld,ld> #define all(a) a.begin(),a.end() #define ceri(a,l,r) {cerr<<#a<<": ";for(ll i_ = l;i_<=r;i_++) cerr<<a[i_]<< " ";cerr<<endl;} #define cer(a) {cerr<<#a<<": ";for(ll x_ : a) cerr<<x_<< " ";cerr<<endl;} #define daj_mi_malo_vremena ios_base::sync_with_stdio(false);cerr.tie(0);cout.tie(0);cin.tie(0); using namespace std; //using namespace __gnu_pbds; /* ll add(ll x,ll y){ x+=y; if(x<0){ x%=mod; x+=mod; }else{ if(x>=mod) x%=mod; } return x; } ll mul(ll a,ll b){ ll ans = (a*b)%mod; if(ans<0) ans+=mod; return ans; } typedef tree<int,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update> ordered_set; typedef tree<int,null_type,less_equal<ll>,rb_tree_tag,tree_order_statistics_node_update> ordered_multiset; mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count()); ll rnd(ll l,ll r){ return uniform_int_distribution<ll>(l,r)(rng); } */ #define maxn 1000005 ll n; ll a[maxn],b[maxn]; pll dpa[maxn],dpb[maxn]; void tc(){ cin >> n; n*=2; for(ll i = 1;i<=n;i++) cin >> a[i]; for(ll i = 1;i<=n;i++) cin >> b[i]; dpa[n] = {1,1}; dpb[n] = {0,0}; for(ll i = n-1;i>=1;i--){ dpa[i] = dpb[i] = {n,-n}; if(a[i]<=a[i+1]){ dpa[i].fi = min(dpa[i].fi,dpa[i+1].fi+1); dpa[i].sc = max(dpa[i].sc,dpa[i+1].sc+1); } if(a[i]<=b[i+1]){ dpa[i].fi = min(dpa[i].fi,dpb[i+1].fi+1); dpa[i].sc = max(dpa[i].sc,dpb[i+1].sc+1); } if(b[i]<=a[i+1]){ dpb[i].fi = min(dpb[i].fi,dpa[i+1].fi); dpb[i].sc = max(dpb[i].sc,dpa[i+1].sc); } if(b[i]<=b[i+1]){ dpb[i].fi = min(dpb[i].fi,dpb[i+1].fi); dpb[i].sc = max(dpb[i].sc,dpb[i+1].sc); } } bool oka = 1,okb = 1; if(dpa[1].fi>n/2||dpa[1].sc<n/2) oka = 0; if(dpb[1].fi>n/2||dpb[1].sc<n/2) okb = 0; if(!oka&&!okb){cout<<-1<<endl;return;} ll x = 0,cnt = n/2; for(ll i = 1;i<=n;i++){ if(x<=a[i]&&dpa[i].fi<=cnt&&dpa[i].sc>=cnt){ cout<<'A'; x = a[i]; cnt--; }else{ cout<<'B'; x = b[i]; } } cout<<endl; } int main(){ daj_mi_malo_vremena int t; t = 1; while(t--){ tc(); } return 0; } /** 3 2 5 4 9 15 11 6 7 6 8 12 14 **/
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...