Submission #527334

#	Time	Username	Problem	Language	Result	Execution time	Memory
527334		rumen_m	Building 4 (JOI20_building4)	C++17	100 / 100	264 ms	59920 KiB

building4

# 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;
      |         ^~~~

• Subtask 1: 11 / 11
• Subtask 2: 89 / 89