Submission #527334

#TimeUsernameProblemLanguageResultExecution timeMemory
527334rumen_mBuilding 4 (JOI20_building4)C++17
100 / 100
264 ms59920 KiB
# include <bits/stdc++.h> using namespace std; int n; const int maxn = 1e6+5; pair <int,int> dp[maxn][2]; int a[maxn][2]; void output(int k, int type, int left) { if(k==0)return ; left-=type; if(dp[k-1][0].first<=left && dp[k-1][0].second >= left && a[k-1][0] <= a[k][type])output(k-1,0,left); else output(k-1,1,left); cout<<(type ? "B" : "A"); } void mergeit(pair <int,int> &a, pair <int,int> b) { if(a==make_pair(1,0))a = b; else if(b==make_pair(1,0))a = a; else a = {min(a.first,b.first),max(a.second,b.second)}; } int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int i,j; cin>>n; for(i = 1;i<=2*n;i++) cin>>a[i][0]; for(i=1;i<=2*n;i++) cin>>a[i][1]; dp[1][0] = {0,0}; dp[1][1] = {1,1}; for(i=2;i<=2*n;i++) { for(j = 0; j <= 1; j++) { pair <int,int> ans; ans = {1,0}; if(a[i-1][0]<=a[i][j])mergeit(ans,dp[i-1][0]); if(a[i-1][1]<=a[i][j])mergeit(ans,dp[i-1][1]); if(j) { ans.first++; ans.second++; } dp[i][j] = ans; // cout<<i << " "<< j<<" "<<ans.first<<" "<<ans.second<<endl; } } if (dp[2*n][0].first<=n && dp[2*n][0].second >= n)output(2*n,0,n); else if(dp[2*n][1].first<=n && dp[2*n][1].second >= n)output(2*n,1,n); else cout<<-1; cout<<endl; return 0; }

Compilation message (stderr)

building4.cpp: In function 'int main()':
building4.cpp:56:7: warning: this 'else' clause does not guard... [-Wmisleading-indentation]
   56 |       else
      |       ^~~~
building4.cpp:58:9: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'else'
   58 |         cout<<endl;
      |         ^~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...