Submission #1013735

#TimeUsernameProblemLanguageResultExecution timeMemory
1013735ReLiceBuilding 4 (JOI20_building4)C++17
0 / 100
1 ms468 KiB
#include <bits/stdc++.h> #define ll long long #define str string #define ins insert #define ld long double #define pb push_back #define pf push_front #define pof pop_front() #define pob pop_back() #define lb lower_bound #define ub upper_bound #define endl "\n" #define fr first #define sc second #define all(x) x.begin(),x.end() #define rall(x) x.rbegin(),x.rend() #define sz size() #define vll vector<ll> #define bc back() #define arr array #define pll vector<pair<ll,ll>> using namespace std;/* #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace __gnu_pbds; #define ordered_set tree<ll, null_type,less_equal<ll>, rb_tree_tag,tree_order_statistics_node_update>*/ template<class S,class T> bool chmin(S &a,const T &b) { return a>b?(a=b)==b:false; } template<class S,class T> bool chmax(S &a,const T &b) { return a<b?(a=b)==b:false; } //void fre(string s){freopen((s+".in").c_str(),"r",stdin);freopen((s+".out").c_str(),"w",stdout);} void start(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); } const ll inf=1e18; const ll mod=998244353; const ll N=3e3+7; const ld eps=1e-9; ll dp[N][N][2]; void solve(){ ll i,j; ll n; cin>>n; ll a[n*2],b[n*2]; for(i=0;i<n*2;i++)cin>>a[i]; for(i=0;i<n*2;i++)cin>>b[i]; dp[1][0][0]=1; dp[0][1][1]=1; for(ll len=1;len<2*n;len++){ for(i=max(0ll,len-n);i<=min(n,len);i++){ j=len-i; ll x=i+j-1; if(a[x]<a[x+1])dp[i+1][j][0]+=dp[i][j][0]; if(a[x]<b[x+1])dp[i][j+1][1]+=dp[i][j][0]; if(b[x]<a[x+1])dp[i+1][j][0]+=dp[i][j][1]; if(b[x]<b[x+1])dp[i][j+1][1]+=dp[i][j][1]; } } if(!dp[n][n][0] && !dp[n][n][1]) { cout<<-1<<endl;return; } ll A=n,B=n,c,x=n*2-1; if(dp[n][n][0])c=0; else c=1; str ans; while(x){ if(c==0){ ans+='A'; if(A && a[x]>a[x-1] && dp[A-1][B][0]){ A--; }else{ A--; c=1; } x--; }else{ ans+='B'; if(A && b[x]>a[x-1] && dp[A][B-1][0]){ B--; c=0; }else{ B--; } x--; } } if(A) ans+='A'; else ans+='B'; reverse(all(ans)); cout<<ans<<endl; } signed main(){ start(); ll t=1; //cin>>t; while(t--) solve(); return 0; } /* */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...