oj.uz

답안 #810221

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
810221 2023-08-06T06:51:23 Z ZHIRDILBILDIZ 건물 4 (JOI20_building4) C++14
11 / 100
 371 ms 196888 KB 
#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)
    {
//        if(now == n / 2)
//        {
            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)) ;
    }
    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.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 23 ms 47268 KB Output is correct
2 Correct 23 ms 47316 KB Output is correct
3 Correct 22 ms 47324 KB Output is correct
4 Correct 23 ms 47316 KB Output is correct
5 Correct 57 ms 74032 KB Output is correct
6 Correct 55 ms 72748 KB Output is correct
7 Correct 48 ms 67304 KB Output is correct
8 Correct 51 ms 70512 KB Output is correct
9 Correct 55 ms 71600 KB Output is correct
10 Correct 52 ms 66656 KB Output is correct
11 Correct 61 ms 74948 KB Output is correct
12 Correct 62 ms 78748 KB Output is correct
13 Correct 71 ms 78756 KB Output is correct
14 Correct 75 ms 78740 KB Output is correct
15 Correct 62 ms 78712 KB Output is correct
16 Correct 59 ms 78744 KB Output is correct
17 Correct 63 ms 78684 KB Output is correct
18 Correct 66 ms 78676 KB Output is correct
19 Correct 62 ms 78744 KB Output is correct
20 Correct 60 ms 78648 KB Output is correct
21 Correct 61 ms 78700 KB Output is correct
22 Correct 63 ms 78624 KB Output is correct
23 Correct 68 ms 78704 KB Output is correct
24 Correct 56 ms 78664 KB Output is correct
25 Correct 56 ms 78352 KB Output is correct
26 Correct 56 ms 78696 KB Output is correct
27 Correct 64 ms 78664 KB Output is correct
28 Correct 53 ms 72424 KB Output is correct
29 Correct 58 ms 78592 KB Output is correct
30 Correct 52 ms 72592 KB Output is correct
31 Correct 61 ms 78588 KB Output is correct
32 Correct 48 ms 69324 KB Output is correct
33 Correct 60 ms 78704 KB Output is correct

Subtask #2
0 / 89.0

# 결과 실행 시간 메모리 Grader output
1 Correct 23 ms 47268 KB Output is correct
2 Correct 23 ms 47316 KB Output is correct
3 Correct 22 ms 47324 KB Output is correct
4 Correct 23 ms 47316 KB Output is correct
5 Correct 57 ms 74032 KB Output is correct
6 Correct 55 ms 72748 KB Output is correct
7 Correct 48 ms 67304 KB Output is correct
8 Correct 51 ms 70512 KB Output is correct
9 Correct 55 ms 71600 KB Output is correct
10 Correct 52 ms 66656 KB Output is correct
11 Correct 61 ms 74948 KB Output is correct
12 Correct 62 ms 78748 KB Output is correct
13 Correct 71 ms 78756 KB Output is correct
14 Correct 75 ms 78740 KB Output is correct
15 Correct 62 ms 78712 KB Output is correct
16 Correct 59 ms 78744 KB Output is correct
17 Correct 63 ms 78684 KB Output is correct
18 Correct 66 ms 78676 KB Output is correct
19 Correct 62 ms 78744 KB Output is correct
20 Correct 60 ms 78648 KB Output is correct
21 Correct 61 ms 78700 KB Output is correct
22 Correct 63 ms 78624 KB Output is correct
23 Correct 68 ms 78704 KB Output is correct
24 Correct 56 ms 78664 KB Output is correct
25 Correct 56 ms 78352 KB Output is correct
26 Correct 56 ms 78696 KB Output is correct
27 Correct 64 ms 78664 KB Output is correct
28 Correct 53 ms 72424 KB Output is correct
29 Correct 58 ms 78592 KB Output is correct
30 Correct 52 ms 72592 KB Output is correct
31 Correct 61 ms 78588 KB Output is correct
32 Correct 48 ms 69324 KB Output is correct
33 Correct 60 ms 78704 KB Output is correct
34 Correct 259 ms 98316 KB Output is correct
35 Correct 351 ms 186864 KB Output is correct
36 Correct 328 ms 184392 KB Output is correct
37 Correct 349 ms 187184 KB Output is correct
38 Correct 371 ms 196888 KB Output is correct
39 Incorrect 355 ms 195296 KB Output isn't correct
40 Halted 0 ms 0 KB -