Submission #1283049

#	Time	Username	Problem	Language	Result	Execution time	Memory
1283049		Math4Life2020	Arranging Shoes (IOI19_shoes)	C++20	45 / 100	68 ms	21748 KiB

shoes

#include <bits/stdc++.h>
using namespace std;
using ll = long long; using pii = pair<ll,ll>;

const ll Nm = 262144; const ll E = 18;
vector<ll> st(2*Nm,0); //segtree

ll v2(ll x) {
    if (x==0) {
        return 100;
    }
    return __builtin_ctz(x);
}

void upd(ll x, ll v) {
    ll p = x+Nm;
    do {
        st[p]+=v;
        p=p/2;
    } while (p>0);
}

void init(ll N) {
    st = vector<ll>(2*Nm,0LL);
    for (ll i=0;i<(2*N);i++) {
        upd(i,1);
    }
}

ll qry(ll a, ll b) {
    if (a>b) {
        return 0;
    }
    if (v2(a)<v2(b+1)) {
        ll la = v2(a);
        return (st[(a>>la)+(1LL<<(E-la))]+qry(a+(1LL<<la),b));
    } else {
        ll lb = v2(b+1);
        return (st[(b>>lb)+(1LL<<(E-lb))]+qry(a,b-(1LL<<lb)));
    }
}

ll count_swaps(vector<int> S) {
    ll N = S.size()/2;
    init(N);
    ll ans = 0;
    set<pii> sl; //left shoe: {x,#}
    set<ll> sr[N+1]; //right shoe: # -> x
    for (ll x=0;x<(2*N);x++) {
        ll y = S[x];
        if (y<0) {
            sl.insert({x,-y});
        } else {
            sr[y].insert(x);
        }
    }
    while (!sl.empty()) {
        pii p0 = *sl.begin(); sl.erase(sl.begin());
        ans += qry(0,p0.first-1);
        upd(p0.first,-1);
        ll xf = *sr[p0.second].begin(); sr[p0.second].erase(sr[p0.second].begin());
        ans += qry(0,xf-1);
        upd(xf,-1);
    }
    return ans;
}

// int main() {
// 	ll N; cin >> N;
//     vector<int> S0;
//     for (ll i=0;i<(2*N);i++) {
//         ll t; cin >> t;
//         S0.push_back(t);
//     }
//     cout << count_swaps(S0);
// }

• Subtask 1: 10 / 10
• Subtask 2: 0 / 20
• Subtask 3: 20 / 20
• Subtask 4: 15 / 15
• Subtask 5: 0 / 20
• Subtask 6: 0 / 15