Submission #227423

#	Time	Username	Problem	Language	Result	Execution time	Memory
227423		anonymous	Building 4 (JOI20_building4)	C++14	100 / 100	484 ms	44024 KiB

building4

#include <iostream>
#define MAXN 1000005
using namespace std;
int N, A[MAXN][2];
int dp[MAXN][2][2], Num;
bool res[MAXN], b;
bool can(int i, int j, int v) {return(v >= dp[i][j][0] && v <= dp[i][j][1]);}
int main() {
    //freopen("b4in.txt","r",stdin);
    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]);
    }
    dp[1][1][0] = dp[1][1][1] = 1;
    for (int i=2; i<=2*N; i++) {
        for (int j=0; j<=1; j++) {
            dp[i][j][0] = 1<<30, dp[i][j][1]=-1<<30;
            if (A[i][j] >= A[i-1][0]) {
                dp[i][j][0] = min(dp[i][j][0], dp[i-1][0][0]+(j > 0));
                dp[i][j][1] = max(dp[i][j][1], dp[i-1][0][1]+(j > 0));
            }
            if (A[i][j] >= A[i-1][1]) {
                dp[i][j][0] = min(dp[i][j][0], dp[i-1][1][0]+(j > 0));
                dp[i][j][1] = max(dp[i][j][1], dp[i-1][1][1]+(j > 0));
            }
        }
    }
    if (!can(2*N, 0, N) && !can(2*N, 1, N)) {
        printf("-1");
    } else {
        b = can(2*N, 1, N), Num = N;
        for (int i=2*N; i>=1; i--) {
            res[i] = b;
            Num -= b;
            b = (A[i-1][1] <= A[i][b]) && can(i-1, 1, Num);
        }
        for (int i=1; i<=2*N; i++) {
            printf("%c", res[i] ? 'B' : 'A');
        }
    }
}

Compilation message (stderr)

building4.cpp: In function 'int main()':
building4.cpp:10:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&N);
     ~~~~~^~~~~~~~~
building4.cpp:12: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:15: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