Submission #521739

#	Time	Username	Problem	Language	Result	Execution time	Memory
521739		tabr	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	76 ms	19992 KiB

shoes

#include <bits/stdc++.h>
using namespace std;
#ifdef tabr
#include "library/debug.cpp"
#else
#define debug(...)
#endif

template <typename T>
struct fenwick {
    int n;
    vector<T> node;

    fenwick(int _n) : n(_n) {
        node.resize(n);
    }

    void add(int x, T v) {
        while (x < n) {
            node[x] += v;
            x |= (x + 1);
        }
    }

    T get(int x) {  // [0, x]
        T v = 0;
        while (x >= 0) {
            v += node[x];
            x = (x & (x + 1)) - 1;
        }
        return v;
    }

    T get(int x, int y) {  // [x, y]
        return (get(y) - (x ? get(x - 1) : 0));
    }

    int lower_bound(T v) {
        int x = 0;
        int h = 1;
        while (n >= (h << 1)) {
            h <<= 1;
        }
        for (int k = h; k > 0; k >>= 1) {
            if (x + k <= n && node[x + k - 1] < v) {
                v -= node[x + k - 1];
                x += k;
            }
        }
        return x;
    }
};

long long count_swaps(vector<int> s) {
    int n = (int) s.size();
    vector<int> pos(n / 2);
    long long ans = 0;
    vector<vector<int>> cnt(2 * n + 1);
    for (int i = 0; i < n; i++) {
        cnt[s[i] + n].emplace_back(i);
    }
    int c = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < (int) cnt[n + i].size(); j++) {
            s[cnt[n + i][j]] = c;
            s[cnt[n - i][j]] = c;
            pos[c] = max(cnt[n + i][j], cnt[n - i][j]);
            if (cnt[n + i][j] < cnt[n - i][j]) {
                ans++;
            }
            c++;
        }
    }
    debug(ans, s);
    fenwick<int> f(n);
    for (int i = 0; i < n; i++) {
        f.add(i, 1);
    }
    for (int i = 0; i < n; i++) {
        if (!f.get(i, i)) {
            continue;
        }
        f.add(i, -1);
        f.add(pos[s[i]], -1);
        ans += f.get(i, pos[s[i]]);
    }
    return ans;
}

#ifdef tabr
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout << count_swaps({2, 1, -1, -2}) << '\n';
    cout << count_swaps({-2, 2, 2, -2, -2, 2}) << '\n';
    cout << count_swaps({-1, 2, 1, 1, -2, -1}) << '\n';
    return 0;
}
#endif

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