Submission #226764

#	Time	Username	Problem	Language	Result	Execution time	Memory
226764		MKopchev	Building 4 (JOI20_building4)	C++14	11 / 100	2095 ms	16512 KiB

building4

#include<bits/stdc++.h>
using namespace std;
const int nmax=2e3+42;
bool been[2*nmax][2][nmax];

int n;
int a[2*nmax],b[2*nmax];

string current;

pair<int,int> dp[2*nmax][2];

void go(int pos,bool side,int a_taken)
{
    if(side==0)current.push_back('A');
    else current.push_back('B');

    if(been[pos][side][a_taken])
    {
        current.pop_back();
        return;
    }

    been[pos][side][a_taken]=1;

    //cout<<"go "<<a_taken<<" "<<b_taken<<" "<<side<<endl;

    if(a_taken==n&&pos==2*n)
    {
        for(int i=1;i<=2*n;i++)printf("%c",current[i]);
        printf("\n");
        exit(0);
    }


    int lst=(side==0?a[pos]:b[pos]);

    int b_taken=pos-a_taken;

    //use a
    if(a_taken<n&&lst<=a[pos+1])go(pos+1,0,a_taken+1);
    //use b
    if(b_taken<n&&lst<=b[pos+1])go(pos+1,1,a_taken);

    current.pop_back();
}

int main()
{
    scanf("%i",&n);

    for(int i=1;i<=2*n;i++)scanf("%i",&a[i]);
    for(int i=1;i<=2*n;i++)scanf("%i",&b[i]);

    go(0,0,0);

    printf("-1\n");
    return 0;
}

Compilation message (stderr)

building4.cpp: In function 'int main()':
building4.cpp:50:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%i",&n);
     ~~~~~^~~~~~~~~
building4.cpp:52:33: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(int i=1;i<=2*n;i++)scanf("%i",&a[i]);
                            ~~~~~^~~~~~~~~~~~
building4.cpp:53:33: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(int i=1;i<=2*n;i++)scanf("%i",&b[i]);
                            ~~~~~^~~~~~~~~~~~

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