Submission #308582

#	Time	Username	Problem	Language	Result	Execution time	Memory
308582		tjdgus4384	건물 4 (JOI20_building4)	C++14	0 / 100	2 ms	512 KiB

building4

#include<bits/stdc++.h>
using namespace std;
int N, A[500010], B[500010], cntA, cntB;
int dpA[500010][2], dpB[500010][2];
bool chk[500010], ret[500010];

int main(){
    scanf("%d", &N);
    for(int i = 0;i < 2*N;i++){
        scanf("%d", &A[i]);
    }
    for(int i = 0;i < 2*N;i++){
        scanf("%d", &B[i]);
    }
    dpA[0][0] = dpB[0][1] = 1;
    dpA[0][1] = dpB[0][0] = 0;
    int prev = min(A[0], B[0]);
    for(int i = 1;i < 2*N;i++){
        if(A[i] >= A[i - 1]) dpA[i][0] = dpA[i - 1][0] + 1;
        if(A[i] >= B[i - 1]) dpA[i][0] = max(dpA[i][0], dpA[i - 1][1] + 1);
        if(B[i] >= A[i - 1]) dpA[i][1] = dpA[i - 1][0];
        if(B[i] >= B[i - 1]) dpA[i][1] = max(dpA[i][1], dpA[i - 1][1]);
        if(B[i] >= A[i - 1]) dpB[i][1] = dpB[i - 1][0] + 1;
        if(B[i] >= B[i - 1]) dpB[i][1] = max(dpB[i][1], dpB[i - 1][1] + 1);
        if(A[i] >= A[i - 1]) dpB[i][0] = dpB[i - 1][0];
        if(A[i] >= B[i - 1]) dpB[i][0] = max(dpB[i][0], dpB[i - 1][1]);
        if(A[i] <= B[i]){
            if(A[i] >= prev) prev = A[i];
            else if(B[i] >= prev) prev = B[i];
            else{
                printf("-1");
                return 0;
            }
        }
        else{
            if(B[i] >= prev) prev = B[i];
            else if(A[i] >= prev) prev = A[i];
            else{
                printf("-1");
                return 0;
            }
        }
    }
    if(max(dpA[2*N-1][0], dpA[2*N-1][1]) < N || max(dpB[2*N-1][0], dpB[2*N-1][1]) < N){
        printf("-1");
        return 0;
    }
    prev = 0;
    for(int i = 0;i < 2*N;i++){
        if(A[i] <= B[i]){
            if(A[i] >= prev) {
                ret[i] = true;
                chk[i] = false;
                prev = A[i];
                cntA++;
            }
            else if(B[i] >= prev) {
                ret[i] = false;
                chk[i] = true;
                prev = B[i];
                cntB++;
            }
        }
        else{
            if(B[i] >= prev) {
                ret[i] = true;
                chk[i] = true;
                prev = B[i];
                cntB++;
            }
            else if(A[i] >= prev) {
                ret[i] = false;
                chk[i] = false;
                prev = A[i];
                cntA++;
            }
        }
    }
    vector<int> v;
    for(int i = 0;i < 2*N-1;i++){
        if(max(A[i], B[i]) <= min(A[i+1], B[i+1]) && ret[i]) v.push_back(i);
    }
    if(ret[2*N-1]) v.push_back(2*N-1);
    for(int i = 0;i < v.size();i++){
        if(cntA == cntB) break;
        if(cntA < cntB){
            int cnt, maxcnt = 0, maxi = v[i] + 1;
            if(chk[v[i]]) {maxcnt = cnt = 1; maxi = v[i];}
            else cnt = -1;
            if(cntA + cnt == cntB - cnt){              
                cntA += cnt, cntB -= cnt;
                chk[v[i]] = false;
                goto print;
            }
            for(int j = v[i] - 1;j >= 0;j--){
                if(!ret[j]) break;
                if(max(A[j], B[j]) <= min(A[j+1], B[j+1])) break;
                if(max(A[j], B[j]) <= max(A[j+1], B[j+1])){
                    if(chk[j]) cnt++;
                    else cnt--;
                    if(cntA + cnt == cntB - cnt){
                        cntA += cnt, cntB -= cnt;
                        for(int k = v[i];k >= j;k--){
                            if(chk[k]) chk[k] = false;
                            else chk[k] = true;
                        }
                        goto print;
                    }
                    if(cnt > maxcnt){
                        maxcnt = cnt;
                        maxi = j;
                    }
                }
                else break;
            }
            for(int j = v[i];j >= maxi;j--){
                if(chk[j]) chk[j] = false;
                else chk[j] = true;
            }
            cntA += maxcnt, cntB -= maxcnt;
        }
        else{
            int cnt, maxcnt = 0, maxi = v[i] + 1;
            if(!chk[v[i]]) {maxcnt = cnt = 1; maxi = v[i];}
            else cnt = -1;
            if(cntB + cnt == cntA - cnt){
                cntB += cnt, cntA -= cnt;
                chk[v[i]] = true;
                goto print;
            }
            for(int j = v[i] - 1;j >= 0;j--){
                if(!ret[j]) break;
                if(max(A[j], B[j]) <= min(A[j+1], B[j+1])) break;
                if(max(A[j], B[j]) <= max(A[j+1], B[j+1])){
                    if(!chk[j]) cnt++;
                    else cnt--;
                    if(cntB + cnt == cntA - cnt){
                        cntB += cnt, cntA -= cnt;
                        for(int k = v[i];k >= j;k--){
                            if(chk[k]) chk[k] = false;
                            else chk[k] = true;
                        }
                        goto print;
                    }
                    if(cnt > maxcnt){
                        maxcnt = cnt;
                        maxi = j;
                    }
                }
                else break;
            }
            for(int j = v[i];j >= maxi;j--){
                if(chk[j]) chk[j] = false;
                else chk[j] = true;
            }
            cntB += maxcnt, cntA -= maxcnt;
        }
    }
    print:;
    if(cntA != cntB){
        printf("-1");
        return 0;
    }
    for(int i = 0;i < 2*N;i++){
        if(chk[i]) printf("B");
        else printf("A");
    }
    return 0;
}

Compilation message (stderr)

building4.cpp: In function 'int main()':
building4.cpp:84:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   84 |     for(int i = 0;i < v.size();i++){
      |                   ~~^~~~~~~~~~
building4.cpp:8:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    8 |     scanf("%d", &N);
      |     ~~~~~^~~~~~~~~~
building4.cpp:10:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   10 |         scanf("%d", &A[i]);
      |         ~~~~~^~~~~~~~~~~~~
building4.cpp:13:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   13 |         scanf("%d", &B[i]);
      |         ~~~~~^~~~~~~~~~~~~

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