Submission #1104683

#	Time	Username	Problem	Language	Result	Execution time	Memory
1104683		hiensumi	Building 4 (JOI20_building4)	C++14	11 / 100	152 ms	34888 KiB

building4

#include <bits/stdc++.h>
using namespace std;
#define fod(i,a,b) for(int i((int) (a)), _b(b); i <= _b; i++)
#define fok(i,a,b) for(int i((int) (a)), _b(b); i >= _b; i--)
#define ll long long
#define pb push_back
#define mp make_pair
#define pii pair<int,int>
#define fi first
#define se second
#define ve vector
#define vi ve<int>
#define vll ve<ll>
#define el '\n'
#define mask(i) (1LL<<(i))
#define BIT(msk,i) (msk>>(i)&1LL)
template<class T> bool mini(T &a, T b){ return (a > (b) ? a = (b), 1 : 0); }
template<class T> bool maxi(T &a, T b){ return (a < (b) ? a = (b), 1 : 0); }
const int base = mask(20) + 5;
#define name "building4"

const int N = 5e5;
int n;

int a[2 * N + 5], b[2 * N + 5];

pii fa[N + 5];
pii fb[N + 5];
// min imbalance and max imbalance if ends at A/B

inline void upd(pii &a, pii b, int d){
    mini(a.fi, b.fi + d);
    maxi(a.se, b.se + d);
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    if(fopen(name".inp", "r")){
        freopen(name".inp", "r", stdin);
        freopen(name".out", "w", stdout);
    }

    cin >> n; n <<= 1;
    fod(i,1,n) cin >> a[i];
    fod(i,1,n) cin >> b[i];

    fod(i,1,n) fa[i] = fb[i] = mp(1e9, -1e9);

    fa[0] = mp(0, 0);
    fb[0] = mp(0, 0);

    fod(i,1,n){
        if(a[i] >= a[i-1]) upd(fa[i], fa[i-1], -1);
        if(a[i] >= b[i-1]) upd(fa[i], fb[i-1], -1);
        if(b[i] >= a[i-1]) upd(fb[i], fa[i-1], 1);
        if(b[i] >= b[i-1]) upd(fb[i], fb[i-1], 1);
    }

//    fod(i,1,n) cout << fa[i].fi << " " << fa[i].se << el;

    int imbalance = 0, last = 1e9;

    string ans;

    fok(i,n,1){
        if(fa[i].fi <= imbalance and imbalance <= fa[i].se and a[i] <= last){
            imbalance++;
            last = a[i];
            ans.pb('A');
//            cerr << 'A' << el;
        }
        else if(fb[i].fi <= imbalance and imbalance <= fb[i].se and b[i] <= last){
            imbalance--;
            last = b[i];
            ans.pb('B');
//            cerr << 'B' << el;
        }
        else return cout << -1, 0;
    }

    if(imbalance != 0) return cout << -1, 0;

    reverse(ans.begin(), ans.end());

    cout << ans;

    return 0;
}

Compilation message (stderr)

building4.cpp: In function 'int main()':
building4.cpp:39:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   39 |         freopen(name".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
building4.cpp:40:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   40 |         freopen(name".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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