제출 #810222

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
810222		ZHIRDILBILDIZ	건물 4 (JOI20_building4)	C++14	11 / 100	374 ms	211260 KiB

building4

#include<bits/stdc++.h>
#define fi first
#define se second
#define ll long long
using namespace std ;
const int N = 5e5 ;
int n, a[2 * N + 1], b[2 * N + 1], dp[4 * N + 1] ;
vector<char> ans ;
bool us[4 * N + 1] ;
vector<int> v[4 * N + 1] ;
void dfs(int city)
{
    int mx = 0 ;
    us[city] = 1 ;
    if(city > n)
        dp[city]++ ;
    for(int i : v[city])
    {
        if(us[i])
        {
            mx = max(mx, dp[i]) ;
            continue ;
        }
        dfs(i) ;
        mx = max(mx, dp[i]) ;
    }
    dp[city] += mx ;
}
void get_ans(int city, int now)
{
    if(city <= n)
        ans.push_back('A') ;
    else
        ans.push_back('B') ;
    us[city] = 1 ;
    if(city % n == 0)
    {
        for(char i : ans)
            cout << i ;
        exit(0) ;
        return ;
    }
    for(int i : v[city])
    {
        if(us[i] || now + dp[i] < n / 2)
            continue ;
        get_ans(i, now + (i > n)) ;
    }
    us[city] = 0 ;
    ans.pop_back() ;
}
void ultra_clear()
{
    for(int i = 1 ; i <= 4 * N ; i++)
        us[i] &= 0 ;
}
signed main()
{
    ios_base::sync_with_stdio( 0 ) ;
    cin.tie( 0 ) ;
    cout.tie( 0 ) ;
    cin >> n ;
    n *= 2 ;
    for(int i = 1 ; i <= n ; i++)
        cin >> a[i] ;
    for(int i = 1 ; i <= n ; i++)
        cin >> b[i] ;
    if(n <= 4000)
    {
        bool gr[n + 1][n + 1][2] = {} ;
        gr[1][0][0] = 1 ;
        gr[1][1][1] = 1 ;
        gr[0][0][0] = 1 ;
        for(int i = 2 ; i <= n ; i++)
            for(int j = 0 ; j <= n ; j++)
            {
                if(a[i] >= a[i - 1])
                    gr[i][j][0] |= gr[i - 1][j][0] ;
                if(a[i] >= b[i - 1])
                    gr[i][j][0] |= gr[i - 1][j][1] ;
                if(j)
                {
                    if(b[i] >= a[i - 1])
                        gr[i][j][1] |= gr[i - 1][j - 1][0] ;
                    if(b[i] >= b[i - 1])
                        gr[i][j][1] |= gr[i - 1][j - 1][1] ;
                }
            }
        if(gr[n][n / 2][0] || gr[n][n / 2][1])
        {
            pair<pair<int, int>, bool> last = {{n, n / 2}, 0} ;
            if(gr[n][n / 2][1])last.se = 1 ;
            for(int i = n - 1 ; i >= 0 ; i--)
                if(!last.se)
                {
                    ans.push_back('A') ;
                    if(a[i] <= a[i + 1] && gr[i][last.fi.se][0])
                    {
                        last = {{i, last.fi.se}, 0} ;
                        continue ;
                    }
                    if(b[i] <= a[i + 1] && gr[i][last.fi.se][1])
                    {
                        last = {{i, last.fi.se}, 1} ;
                        continue ;
                    }
                }
                else
                {
                    if(!last.fi.se)
                        continue ;
                    ans.push_back('B') ;
                    if(a[i] <= b[i + 1] && gr[i][last.fi.se - 1][0])
                    {
                        last = {{i, last.fi.se - 1}, 0} ;
                        continue ;
                    }
                    if(b[i] <= b[i + 1] && gr[i][last.fi.se - 1][1])
                    {
                        last = {{i, last.fi.se - 1}, 1} ;
                        continue ;
                    }
                }
            reverse(ans.begin(), ans.end()) ;
            for(char i : ans)
                cout << i ;
        }
        else
            cout << "-1\n" ;
        return 0 ;
    }
    for(int i = 1 ; i < n ; i++)
    {
        if(a[i] <= a[i + 1])
            v[i].push_back(i + 1) ;
        if(a[i] <= b[i + 1])
            v[i].push_back(n + i + 1) ;
        if(b[i] <= a[i + 1])
            v[n + i].push_back(i + 1) ;
        if(b[i] <= b[i + 1])
            v[n + i].push_back(n + i + 1) ;
    }
    dfs(1) ;
    dfs(n + 1) ;
    ultra_clear() ;
    get_ans(1, 0) ;
    ultra_clear() ;
    get_ans(n + 1, 1) ;
    cout << "-1\n" ;
    return 0 ;
}

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