Submission #1285292

#	Time	Username	Problem	Language	Result	Execution time	Memory
1285292		Faisal_Saqib	Building 4 (JOI20_building4)	C++20	0 / 100	2 ms	576 KiB

building4

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N=1e6+100;
int a[N][2];
int dpmi[N][2]; // dp[i][0] at A [1] at B
int dpmx[N][2]; // dp[i][0] at A [1] at B
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin>>n;
    for(int i=1;i<=2*n;i++)
    {
        cin>>a[i][1];
    }
    for(int i=1;i<=2*n;i++)
    {
        cin>>a[i][0];
    }
    dpmi[1][0]=0;
    dpmi[1][1]=1;
    dpmx[1][0]=0;
    dpmx[1][1]=1;
    // B
    // A
    for(int i=2;i<=2*n;i++)
    {
        for(int k=0;k<2;k++)
        {
            dpmx[i][k]=-1e9,dpmi[i][k]=1e9;
            for(int j=0;j<2;j++)
            {
                if(a[i-1][j]<=a[i][k])
                {
                    dpmx[i][k]=max(dpmx[i][k],dpmx[i-1][j]+k);
                    dpmi[i][k]=min(dpmi[i][k],dpmi[i-1][j]+k);
                }
            }
        }
    }
    // if(n<min(dpmi[2*n][0],dpmi[2*n][1]) or max(dpmx[2*n][0],dpmx[2*n][1])<n)
    // {
    //     cout<<-1<<endl;
    // }
    // else
    // {
        if(dpmi[2*n][0]<=n and n<=dpmx[2*n][0])
        {
            // We will start at a[i][0]
            // 0 is B and 1 is A
            int p=0;
            int cnt=p;
            string ans="B";
            for(int i=2*n-1;i>=1;i--)
            {
                for(int j=0;j<2;j++)
                {
                    if(dpmi[i][j]+cnt<=n and n<=dpmx[i][j]+cnt)
                    {
                        ans+=(j?'A':'B');
                        cnt+=j;
                        break;
                    }
                }
            }
            reverse(begin(ans),end(ans));
            cout<<ans<<endl;
        }
        else if(dpmi[2*n][1]<=n and n<=dpmx[2*n][1])
        {
             int p=1;
            int cnt=p;
            string ans="A";
            for(int i=2*n-1;i>=1;i--)
            {
                for(int j=0;j<2;j++)
                {
                    if(dpmi[i][j]+cnt<=n and n<=dpmx[i][j]+cnt)
                    {
                        ans+=(j?'A':'B');
                        cnt+=j;
                        break;
                    }
                }
            }
            reverse(begin(ans),end(ans));
            cout<<ans<<endl;
        }
        else
        {
            cout<<-1<<endl;
        }
    // }
}

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