Submission #572506

#	Time	Username	Problem	Language	Result	Execution time	Memory
572506		Lucpp	건물 4 (JOI20_building4)	C++17	100 / 100	344 ms	48260 KiB

building4

#include <bits/stdc++.h>
using namespace std;

const int INF = 1e7;

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
    vector<vector<int>> v(2, vector<int>(2*n));
    for(int b = 0; b < 2; ++b) for(int i = 0; i < 2*n; ++i) cin >> v[1-b][i];
    vector<vector<int>> mi(2, vector<int>(2*n, INF)), ma(2, vector<int>(2*n, -INF));
    mi[0][2*n-1] = ma[0][2*n-1] = 0;
    mi[1][2*n-1] = ma[1][2*n-1] = 1;
    for(int i = 2*n-2; i >= 0; --i){
        for(int j = 0; j < 2; ++j){
            for(int k = 0; k < 2; ++k){
                if(v[j][i] <= v[k][i+1]){
                    mi[j][i] = min(mi[j][i], mi[k][i+1]+j);
                    ma[j][i] = max(ma[j][i], ma[k][i+1]+j);
                }
            }
        }
    }
    string ans;
    if(mi[0][0] <= n && n <= ma[0][0]) ans += 'B';
    else if(mi[1][0] <= n && n <= ma[1][0]) ans += 'A';
    if(ans.empty()) cout << "-1\n";
    else{
        int j = (ans=="A");
        int cnt = n-j;
        for(int i = 1; i < 2*n; ++i){
            for(int k = 0; k < 2; ++k){
                if(v[j][i-1] <= v[k][i]){
                    if(mi[k][i] <= cnt && cnt <= ma[k][i]){
                        cnt -= k;
                        j = k;
                        ans += 'A'+(1-k);
                        break;
                    }
                }
            }
        }
        cout << ans << "\n";
    }
}

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