Submission #810297

#	Time	Username	Problem	Language	Result	Execution time	Memory
810297		ZHIRDILBILDIZ	Building 4 (JOI20_building4)	C++14	0 / 100	23 ms	49236 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 pz[4 * N + 1], us[4 * N + 1] ;
vector<int> v[4 * N + 1] ;
void dfs(int city)
{
    bool fl = 0 ;
    int mx = 0 ;
    us[city] = 1 ;
    for(int i : v[city])
    {
        if(us[i])
        {
            if(pz[i])
            {
                fl = 1 ;
                mx = max(mx, dp[i]) ;
            }
            continue ;
        }
        dfs(i) ;
        if(pz[i])
        {
            fl = 1 ;
            mx = max(mx, dp[i]) ;
        }
    }
    if(fl)
        pz[city] = 1 ;
    dp[city] = mx + 1 ;
}
void get_ans(int city, int now)
{
//    cout<<city << ' ' << now << '\n' ;
    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) ;
    }
    for(int i : v[city])
    {
        if(us[i] || now + dp[i] < n / 2)
            continue ;
        get_ans(i, now + (i > n)) ;
//        cout << city << '\n' ;
    }
    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 ;
//    }
    ans.clear() ;
    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) ;
    }
    pz[n] = pz[2 * n] = 1 ;
    dfs(1) ;
    dfs(n + 1) ;
//    for(int i = 1 ; i <= 2 * n ; i++)
//    {
//        cout << dp[i] << ' ' ;
//        if(i == n)cout << '\n' ;
//    }
//    cout << '\n' ;
    ultra_clear() ;
    get_ans(1, 0) ;
//    cout << "_______________________\n" ;
    ultra_clear() ;
    get_ans(n + 1, 1) ;
//    cout << "_______________________\n" ;
    cout << "-1\n" ;
    return 0 ;
}
//5
//1 2 4 8 6 1 9 2 7 2
//9 10 1 4 7 6 6 7 5 7
//3
//1 2 9 6 10 7
//5 8 8 9 5 10

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