Submission #237947

#	Time	Username	Problem	Language	Result	Execution time	Memory
237947		egekabas	Building 4 (JOI20_building4)	C++14	0 / 100	6 ms	640 KiB

building4

#include <bits/stdc++.h>
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef pair<ull, ull> pull;
typedef pair<int, int> pii;
typedef pair<ld, ld> pld;
pii a[500009][2];
int n;
const int inf = 1e9;
char ans[500009];
void change(int l, int r){
    for(int i = 0; i <= l; ++i){
        if(ans[i] == 'A')
            ans[i] = 'B';
        else
            ans[i] = 'A';
    }
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    //freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);

    cin >> n;
    n *= 2;
    for(int i = 0; i < n; ++i){
        cin >> a[i][0].ff;
        a[i][0].ss = 1;
    }
    for(int i = 0; i < n; ++i){
        cin >> a[i][1].ff;
        a[i][1].ss = -1;
        if(a[i][1].ff > a[i][0].ff){
            swap(a[i][1], a[i][0]);
        }
    }
    vector<pair<vector<int>, vector<int>>> fv;
    int val[2] = {-inf, -inf};
    vector<int> cur[2];
    for(int i = 0; i < n; ++i){
        if(a[i][0].ff < val[1]){
            cout << "-1\n";
            return 0;
        }
        else if(a[i][1].ff >= val[0] && val[0] != -1e9){
            val[0] = -1e9;
            val[1] = -1e9;
            fv.pb({cur[0], cur[1]});
            cur[0].clear();
            cur[1].clear();
            --i;
        }
        else if(a[i][1].ff >= val[1] && val[0] > a[i][1].ff && val[0] > a[i][0].ff){
            cur[0] = cur[1];
            cur[1].clear();
            val[0] = -1e9;
            val[1] = -1e9;
            fv.pb({cur[0], cur[1]});
            cur[0].clear();
            --i;
        }
        else if(a[i][0].ff >= val[1] && val[0] > a[i][1].ff && val[0] > a[i][0].ff){
            a[i][1] = a[i][0];
            --i;
        }
        else{
            val[0] = a[i][0].ff;
            val[1] = a[i][1].ff;
            cur[0].pb(a[i][0].ss);
            cur[1].pb(a[i][1].ss);
        }
    }
    if(!cur[0].empty()){
        fv.pb({cur[0], cur[1]});
    }
    int curid = 0;
    int curbal = 0;
    for(auto v : fv){
        for(int i = 0; i < v.ff.size(); ++i){
            curbal += v.ff[i];
            if(v.ff[i] == 1)
                ans[curid+i] = 'A';
            else
                ans[curid+i] = 'B';
        }
        curid += v.ff.size();
    }
    curid = 0;
    for(auto v : fv){
        int curval = 0;
        pii mini = {1e9, 1e9};
        pii maxi = {-1e9, -1e9};
        for(int i = 0; i < v.ss.size(); ++i){
            curval += v.ss[i] - v.ff[i];
            if(curval == -curbal){
                change(curid, curid+i);
                curbal = 0;
                break;
            }
            mini = min(mini, {curval, i});
            maxi = max(maxi, {curval, i});
        }
        if(curbal == 0)
            break;
        else if(curbal > 0 && mini.ff < 0){
            curbal += mini.ff;
            change(curid, mini.ss+curid);
        }
        else if(curbal < 0 && maxi.ff > 0){
            curbal += maxi.ff;
            change(curid, maxi.ss+curid);
        }
        curid += v.ff.size();
    }
    if(curbal != 0){
        cout << "-1\n";
        return 0;
    }
    for(int i = 0; i < n; ++i)
        cout << ans[i];
}

Compilation message (stderr)

building4.cpp: In function 'int main()':
building4.cpp:88:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i = 0; i < v.ff.size(); ++i){
                        ~~^~~~~~~~~~~~~
building4.cpp:102:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i = 0; i < v.ss.size(); ++i){
                        ~~^~~~~~~~~~~~~

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