Submission #950838

#	Time	Username	Problem	Language	Result	Execution time	Memory
950838		efishel	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	82 ms	76112 KiB

shoes

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

struct Fenwick { // 0-indexed
    vll tree;
    ll n;

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

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

    void update (ll at, ll val) { // 0-indexed
        for (; at < n; at |= at+1) tree[at] += val;
    }
};

ll count_swaps (vector <int> vei) {
    vll ve(vei.size());
    ll n = ve.size()/2;
    for (ll i = 0; i < 2*n; i++) ve[i] = vei[i];
    Fenwick ft(2*n); // ft[i] means that there are now ft[i] shoes in position i
    ll ans = 0;
    for (ll i = 0; i < 2*n; i++) {
        ft.update(i, 1);
    }
    vll next(2*n, -15);
    {vector <queue <ll> > nextqs(n+1);
    for (ll i = 2*n-1; i >= 0; i--) {
        queue <ll> &q = nextqs[abs(ve[i])];
        if (!q.size() || ve[q.front()] == ve[i]) { // not complement
            q.push(i);
        } else { // complements
            next[i] = q.front();
            q.pop();
        }
    }}
    for (ll i = 0; i < 2*n; i++) {
        ll j = next[i];
        if (j < 0) continue;
        ans += ft.query(i+1, j-1) + (ve[i] > 0); // extra flip
        ft.update(j, -1); // makes it 0
        ft.update(i, 1); // irrelevant but, still, two shoes are now here
    }
    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