Submission #1170619

#	Time	Username	Problem	Language	Result	Execution time	Memory
1170619		laure	Building 4 (JOI20_building4)	C++20	0 / 100	3 ms	840 KiB

building4

#include <bits/stdc++.h>
#define int long long
using namespace std;
int n,cnt;
vector<int>a;
vector<int>b;
vector<vector<int>>dp(4005,vector<int>(4,0));
vector<char>s,ans;
void solve(int ind,int t)
{
    if(t==0||t==1){s.push_back('A');cnt++;}
    else s.push_back('B');
    if(s.size()==n&&cnt==n/2)
    {
        ans=s;
        return;
    }
    if(t==0||t==3)
    {
        if(dp[ind+1][0])solve(ind+1,0);
        if(dp[ind+1][1])solve(ind+1,1);
    }
    if(t==1||t==2)
    {
        if(dp[ind+1][2])solve(ind+1,2);
        if(dp[ind+1][3])solve(ind+1,3);
    }
    if(t==0||t==1){s.pop_back();cnt--;}
    else s.pop_back();
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n;
    n*=2;
    a.resize(n);
    b.resize(n);
    for(int i=0;i<n;i++)cin>>a[i];
    for(int i=0;i<n;i++)cin>>b[i];
    for(int i=0;i<4;i++)dp[n-1][i]=1;
    for(int i=n-2;i>=0;i--)
    {
        if(a[i]<=a[i+1]&&(dp[i+1][0]||dp[i+1][1]))dp[i][0]=1;
        if(a[i]<=b[i+1]&&(dp[i+1][3]||dp[i+1][2]))dp[i][1]=1;
        if(b[i]<=b[i+1]&&(dp[i+1][2]||dp[i+1][3]))dp[i][2]=1;
        if(b[i]<=a[i+1]&&(dp[i+1][0]||dp[i+1][1]))dp[i][3]=1;
    }
    for(int i=0;i<4;i++)
    {
        if(dp[0][i])
        {
            cnt=0;
            s.clear();
            solve(0,i);
        }
        if(!ans.empty())break;
    }
    if(ans.empty())cout<<-1;
    else for(auto u:ans)cout<<u;
}

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