제출 #1285350

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1285350		Faisal_Saqib	건물 4 (JOI20_building4)	C++20	100 / 100	169 ms	26040 KiB

building4

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N=1e6+1;
int a[N][2];
// bool spos[N][2],ppos[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
// bool dp[2*N][2*N][2];
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    // srand(time(0));
    // int d=20;
    int n;
    cin>>n;
    for(int i=1;i<=2*n;i++)
    {
        cin>>a[i][1];
        // a[i][1]=rand()%d+(rand()%2?a[i-1][1]:a[i-1][0]);
        // a[i][0]=rand()%d+(rand()%2?a[i-1][0]:a[i-1][1]);

    }
    for(int i=1;i<=2*n;i++)
    {
        cin>>a[i][0];
    }
    // dp[1][1][1]=1;
    // dp[1][0][0]=1;
    // for(int i=2;i<=2*n;i++)
    // {
    //     for(int j=0;j<=2*n;j++)
    //     {
    //         for(int p=0;p<2;p++)
    //         {
    //             for(int q=0;q<2;q++)
    //             {
    //                 if(a[i-1][q]<=a[i][p] and j>=p)
    //                 {
    //                     dp[i][j][p]|=dp[i-1][j-p][q];
    //                 }
    //             }
    //         }
    //     }
    // }

    dpmi[1][0]=0;
    dpmx[1][0]=0;
    dpmi[1][1]=1;
    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] and  (dpmi[i-1][j]!=1e9 and dpmx[i-1][j]!=-1e9))
                {
                    dpmx[i][k]=max(dpmx[i][k],dpmx[i-1][j]+k);
                    dpmi[i][k]=min(dpmi[i][k],dpmi[i-1][j]+k);
                }
            }
        }
    }
    //     for(int i=1;i<=2*n;i++)
    // {
    //     for(int p=0;p<2;p++)
    //     {
    //         int f=-1,l=-1;
    //         for(int j=0;j<=2*n;j++)
    //         {
    //             if(dp[i][j][p])
    //             {
    //                 if(f==-1)
    //                 {
    //                     f=j;
    //                 }
    //                 l=j;
    //             }
    //             // cout<<dp[i][j][p];
    //         }
    //         // cout<<endl;
    //         if(f!=-1)
    //         {
    //             // cout<<"one"<<endl;
    //             if(dpmi[i][p]!=f or l!=dpmx[i][p])
    //             {
    //                 cout<<"MAsla "<<endl;
    //                 cout<<i<<' '<<p<<endl;
    //                 cout<<dpmi[i][p]<<' '<<f<<' '<<dpmx[i][p]<<' '<<l<<endl;
    //                 for(int i=0;i<2;i++)
    //                 {
    //                     for(int j=0;j<n;j++)
    //                     {
    //                         cout<<a[j][i]<<' ';
    //                     }
    //                 }
    //                 cout<<endl;
    //                 exit(0);
    //             }
    //         }
    //         // cout<<endl;
    //     }
    // }
    // cout<<dpmi[2*n][0]<<' '<<dpmx[2*n][0]<<endl;
    if(dpmi[2*n][0]<=n and n<=dpmx[2*n][0])
    {
        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 and a[i+1][p]>=a[i][j])
                {
                    // if(cnt==n)j=0;
                    ans+=(j?'A':'B');
                    p=j;
                    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 and a[i+1][p]>=a[i][j])
                {
                    // if(cnt==n)j=0;
                    ans+=(j?'A':'B');
                    cnt+=j;
                    p=j;
                    break;
                }
            }
        }
        reverse(begin(ans),end(ans));
        cout<<ans<<endl;
    }
    else
    {
        cout<<-1<<endl;
    }
}

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