Submission #983671

#	Time	Username	Problem	Language	Result	Execution time	Memory
983671		parsadox2	Building 4 (JOI20_building4)	C++17	100 / 100	202 ms	45388 KiB

building4

#include <bits/stdc++.h>
#define F first
#define S second
using namespace std;

const int N = 1e6 + 10;

int n , A[2][N];
pair <int , int> dp[N][2];

pair <int , int> ejtema(pair<int , int> a , pair <int , int> b , int v)
{
    b.F += v;  b.S += v;
    pair <int , int> res;
    res.F = min(a.F , b.F);
    res.S = max(a.S , b.S);
    return res;
}

string Solve(int id , int val , int ty)
{
    string res = "";
    while(true)
    {
        if(ty == 1)
            res.push_back('B');
        else
            res.push_back('A');
        val -= ty;
        if(id == 1)
            break;
        if(A[ty][id] >= A[0][id - 1] && val >= dp[id - 1][0].F && val <= dp[id - 1][0].S)
            ty = 0;
        else
            ty = 1;
        id--;
    }
    reverse(res.begin() , res.end());
    return res;
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);  cout.tie(0);
    cin >> n;
    n *= 2;
    for(int i = 1 ; i <= n ; i++)
        cin >> A[0][i];
    for(int i = 1 ; i <= n ; i++)
        cin >> A[1][i];
    dp[1][0] = make_pair(0 , 0);
    dp[1][1] = make_pair(1 , 1);
    for(int i = 2 ; i <= n ; i++)   for(int ty = 0 ; ty < 2 ; ty++)
    {
        dp[i][ty] = make_pair(N , -1);
        if(A[ty][i] >= A[0][i - 1])
            dp[i][ty] = ejtema(dp[i][ty] , dp[i - 1][0] , ty);
        if(A[ty][i] >= A[1][i - 1])
            dp[i][ty] = ejtema(dp[i][ty] , dp[i - 1][1] , ty);
    }
    int m = n / 2;
    if(m >= dp[n][0].F && m <= dp[n][0].S)
    {
        cout << Solve(n , m , 0) << '\n';
    }
    else if(m >= dp[n][1].F && m <= dp[n][1].S)
    {
        cout << Solve(n , m , 1) << '\n';
    }
    else
    {
        cout << -1 << '\n';
    }
    return 0;
}

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