Submission #216273

#	Time	Username	Problem	Language	Result	Execution time	Memory
216273		dantoh000	Building 4 (JOI20_building4)	C++14	100 / 100	495 ms	78712 KiB

building4

#include <bits/stdc++.h>
using namespace std;
const int N = 500005;
const int INF = 1000000000;
typedef pair<int,int> ii;
int n;
int a[2*N][2];
int p[2*N][2];
int q[2*N][2];
ii P[2*N][2];
ii Q[2*N][2];
int ans[2*N];
bool test(){
    for (int i = 1; i <= 2*n; i++){
        for (int j = 0; j < 2; j++){
            p[i][j] = INF;
            if (a[i][j] >= a[i-1][0]){
                if (p[i-1][0] < p[i][j]){
                    p[i][j] = p[i-1][0];
                    P[i][j] = {i-1,0};
                }
            }
            if (a[i][j] >= a[i-1][1]){
                if (p[i-1][1] < p[i][j]){
                    p[i][j] = p[i-1][1];
                    P[i][j] = {i-1,1};
                }
            }
        }
        p[i][1]++;
    }
    for (int i = 2*n; i >= 1; i--){
        for (int j = 0; j < 2; j++){
            q[i][j] = INF;
            if (i == 2*n || a[i][j] <= a[i+1][0]){
                if (q[i+1][0] < q[i][j]){
                    q[i][j] = q[i+1][0];
                    Q[i][j] = {i+1,0};
                }
            }
            if (i == 2*n || a[i][j] <= a[i+1][1]){
                if (q[i+1][1] < q[i][j]){
                    q[i][j] = q[i+1][1];
                    Q[i][j] = {i+1,1};
                }
            }
        }
        q[i][0]++;
    }

    for (int i = 1; i <= 2*n; i++){
        for (int j = 0; j < 2; j++){
            if (p[i][j] >= INF || q[i][j] >= INF) continue;
            int num = p[i][j] + (2*n - i + 1) - q[i][j] - (j == 1);
            //printf("%d %d -> %d\n",i,j,num);
            if (num == n){
                //printf("FOUND!");
                ii cur = {i,j};
                while (cur.first >= 1){
                    ans[cur.first] = cur.second;
                    cur = P[cur.first][cur.second];
                }
                cur = Q[i][j];
                while (cur.first <= 2*n){
                    ans[cur.first] = cur.second;
                    cur = Q[cur.first][cur.second];
                }
                return true;
            }
        }
    }
    return false;
}
int main(){
    scanf("%d",&n);
    for (int i = 1; i <= 2*n; i++){
        scanf("%d",&a[i][0]);
    }
    for (int i = 1; i <= 2*n; i++){
        scanf("%d",&a[i][1]);
    }
    if (test()){
        for (int i = 1; i <= 2*n; i++){
            printf("%c",ans[i]?'B':'A');
        }
        return 0;
    }
    for (int i = 1; i <= 2*n; i++){
        a[i][0] ^= a[i][1];
        a[i][1] ^= a[i][0];
        a[i][0] ^= a[i][1];
    }
    if (test()){
        for (int i = 1; i <= 2*n; i++){
            printf("%c",ans[i]?'A':'B');
        }
        return 0;
    }
    printf("-1\n");
}

Compilation message (stderr)

building4.cpp: In function 'int main()':
building4.cpp:75:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&n);
     ~~~~~^~~~~~~~~
building4.cpp:77:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d",&a[i][0]);
         ~~~~~^~~~~~~~~~~~~~~
building4.cpp:80:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d",&a[i][1]);
         ~~~~~^~~~~~~~~~~~~~~

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