Submission #810614

#	Time	Username	Problem	Language	Result	Execution time	Memory
810614		vjudge1	Building 4 (JOI20_building4)	C++14	100 / 100	272 ms	31584 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] ;
pair<int, int> dp[2 * N + 1][2] ;
vector<char> ans ;
pair<int, int> mrg(pair<int, int> p1, pair<int, int> p2)
{
    if(p1.fi >= 1e9)
        return p2 ;
    if(p2.fi >= 1e9)
        return p1 ;
    return {min(p1.fi, p2.fi), max(p1.se, p2.se)} ;
}
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] ;
    for(int i = 1 ; i <= n ; i++)
        dp[i][0] = dp[i][1] = {1e9, 1e9} ;
    dp[0][0] = {0, 0} ;
    dp[1][0] = {0, 0} ;
    dp[1][1] = {1, 1} ;
    for(int i = 2 ; i <= n ; i++)
    {
        if(a[i - 1] <= b[i])
            dp[i][1] = {dp[i - 1][0].fi + 1, dp[i - 1][0].se + 1} ;
        if(b[i - 1] <= b[i])
            dp[i][1] = mrg({dp[i - 1][1].fi + 1, dp[i - 1][1].se + 1}, dp[i][1]) ;
        if(a[i - 1] <= a[i])
            dp[i][0] = {dp[i - 1][0].fi, dp[i - 1][0].se} ;
        if(b[i - 1] <= a[i])
            dp[i][0] = mrg(dp[i - 1][1], dp[i][0]) ;
    }
//    for(int i = 1 ; i <= n ; i++)
//    {
//        cout << dp[i][0].fi << ' ' << dp[i][0].se << '\n' ;
//        cout << dp[i][1].fi << ' ' << dp[i][1].se << '\n' ;
//    }
//    cout << "\n" ;
    if((dp[n][0].fi > n / 2 || n / 2 > dp[n][0].se) && (dp[n][1].fi > n / 2 || dp[n][1].se < n / 2))
    {
        cout << "-1\n" ;
        return 0 ;
    }
    pair<int, bool> now = {n / 2, 0} ;
    if(dp[n][1].fi <= n / 2 && n / 2 <= dp[n][1].se)
        now = {n / 2, 1} ;
    for(int i = n - 1 ; i >= 0 ; i--)
        if(!now.se)
        {
            ans.push_back('A') ;
            if(a[i] <= a[i + 1] && dp[i][0].fi <= now.fi && now.fi <= dp[i][0].se)
            {
                now = {now.fi, 0} ;
                continue ;
            }
            if(b[i] <= a[i + 1] && dp[i][1].fi <= now.fi && now.fi <= dp[i][1].se)
            {
                now = {now.fi, 1} ;
                continue ;
            }
        }
        else
        {
            ans.push_back('B') ;
            if(a[i] <= b[i + 1] && dp[i][0].fi <= now.fi - 1 && now.fi - 1 <= dp[i][0].se)
            {
                now = {now.fi - 1, 0} ;
                continue ;
            }
            if(b[i] <= b[i + 1] && dp[i][1].fi <= now.fi - 1 && now.fi - 1 <= dp[i][1].se)
            {
                now = {now.fi - 1, 1} ;
                continue ;
            }
        }
    reverse(ans.begin(), ans.end()) ;
    for(char i : ans)
        cout << i ;
    return 0 ;
}

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