Submission #1021163

#	Time	Username	Problem	Language	Result	Execution time	Memory
1021163		vjudge1	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	130 ms	142896 KiB

shoes

#include "shoes.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vll = vector <ll>;
using vi = vector <int>;

const ll MAXN = 1E5+16;

struct Fenwick {
    vll tree;
    ll n;

    Fenwick (ll n): tree(n, 0), n(n) {}

    void update (ll id, ll val) {
        for (; id < n; id |= id+1) tree[id] += val;
    }

    ll query (ll ql, ll qr) { return query(qr) - query(ql-1); }
    ll query (ll id) {
        ll ans = 0;
        for (; id >= 0; id &= id+1, id--) ans += tree[id];
        return ans;
    }
};

queue <ll> whP[MAXN];
queue <ll> whN[MAXN];
ll count_swaps (vi A) {
    vll ve(A.begin(), A.end());
    ll n = ve.size();
    for (ll i = 0; i < n; i++) {
        if (ve[i] > 0) whP[ve[i]].push(i);
        else whN[-ve[i]].push(i);
    }
    ll ans = 0;
    vector <char> used(n, true);
    Fenwick ft(n);
    for (ll i = 0; i < n; i++) ft.update(i, 1);
    for (ll i = 0; i < n; i++) {
        if (!ft.query(i, i)) continue;
        ll x = -ve[i];
        ans += x < 0;
        ll j = (ve[i] > 0 ? whN[ve[i]].front() : whP[-ve[i]].front());
        assert((ve[i] > 0 ? whP[ve[i]] : whN[-ve[i]]).front() == i);
        // cerr << i << ' ' << j << '\n';
        whN[abs(ve[i])].pop();
        whP[abs(ve[i])].pop();
        assert(ve[i]+ve[j] == 0);
        ft.update(i, -1);
        ft.update(j, -1);
        ans += ft.query(i, j);
    }
    return ans;
}

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