Submission #260175

#	Time	Username	Problem	Language	Result	Execution time	Memory
260175		doowey	Building 4 (JOI20_building4)	C++14	100 / 100	413 ms	48436 KiB

building4

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

#define fi first
#define se second
#define mp make_pair
#define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

const int N = (int)1e6 + 100;
int A[2][N];

int low[N][2];
int high[N][2];

int main(){
    fastIO;
    int n;
    cin >> n;
    int m = 2 * n;
    for(int j = 1; j <= m ; j ++ ){
        for(int k = 0 ; k < 2; k ++ ){
            low[j][k]=(int)1e9;
            high[j][k]=0;
        }
    }
    low[1][0] = 1;
    high[1][0] = 1;

    low[1][1] = 0;
    high[1][1] = 0;
    for(int i = 0 ; i < 2; i ++ ){
        for(int j = 1; j <= m ; j ++ )
            cin >> A[i][j];
    }
    int ni;
    for(int j = 2; j <= m ; j ++ ){
        for(int c = 0; c < 2; c ++ ){
            for(int p = 0 ; p < 2; p ++ ){
                if(A[p][j - 1] <= A[c][j]){
                    ni = low[j - 1][p] + (!c);
                    low[j][c] = min(low[j][c], ni);
                    ni = high[j - 1][p] + (!c);
                    high[j][c] = max(high[j][c], ni);
                }
            }
        }
    }
    int cc = -1;
    if(low[m][0] <= n && n <= high[m][0]){
        cc = 0;
    }
    else if(low[m][1] <= n && n <= high[m][1]){
        cc = 1;
    }
    else{
        cout << "-1\n";
        return 0;
    }
    int cval = n;
    int nval;
    vector<int> sol;

    sol.push_back(cc);
    bool broke;
    for(int j = m ; j > 1; j -- ){
        cval -= !cc;
        broke = false;
        for(int pv = 0 ; pv < 2; pv ++ ){
            if(low[j - 1][pv] <= cval && cval <= high[j - 1][pv] && A[pv][j-1] <= A[cc][j]){
                cc = pv;
                sol.push_back(cc);
                broke = true;
                break;
            }
        }
    }
    reverse(sol.begin(), sol.end());
    for(auto x : sol){
        cout << char('A' + x);
    }
    return 0;
}

Compilation message (stderr)

building4.cpp: In function 'int main()':
building4.cpp:64:9: warning: unused variable 'nval' [-Wunused-variable]
     int nval;
         ^~~~
building4.cpp:68:10: warning: variable 'broke' set but not used [-Wunused-but-set-variable]
     bool broke;
          ^~~~~

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