Submission #1032293

#	Time	Username	Problem	Language	Result	Execution time	Memory
1032293		shmax	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	598 ms	160004 KiB

shoes

#include "shoes.h"
#include <bits/stdc++.h>

using namespace std;
using i32 = int;
#define int long long
#define len(x) (int)(x.size())
#define inf 1000'000'000'000'000'000LL
#define all(x) x.begin(), x.end()
#define low_bit(x) (x & (-x))

template<typename T>
using vec = vector<T>;

template<typename T>
struct fenvik {
private:
    vec<T> fen;

    T _get(int x) {
        T res = 0;
        for (int i = x; i > 0; i -= low_bit(i)) {
            res += fen[i];
        }
        return res;
    }

    void _add(int x, T val) {
        for (int i = x; i < len(fen); i += low_bit(i)) {
            fen[i] += val;
        }
    }

public:
    void init(int x) {
        fen.clear();
        fen.resize(x + 1);
    }

    void inc(int i, T x) {
        i++;
        _add(i, x);
    }

    T get(int l, int r) {
        if (l > r) return 0;
        if (l == 0) return _get(r + 1);
        return _get(r + 1) - _get(l);
    }

    T get(int i) {
        return get(i, i);
    }

    void set(int i, T x) {
        inc(i, x - get(i));
    }
};


int count_swaps(vec<i32> s) {
    int n = len(s);
    map<int, deque<int>> pos;
    set<int> unpaired;
    for (int i = 0; i < len(s); i++) {
        pos[s[i]].push_back(i);
        unpaired.insert(i);
    }
    int ans = 0;
    vec<int> pair(n, -1);
    for (int i = 0; i < n; i++) {
        if (!unpaired.count(i)) continue;
        if (s[i] > 0) ans++;
        int ps = pos[-s[i]].front();
        pos[-s[i]].pop_front();
        pos[s[i]].pop_front();
        s[i] = abs(s[i]);
        s[ps] = abs(s[ps]);
        pair[i] = ps;
        pair[ps] = i;
        unpaired.erase(i);
        unpaired.erase(ps);
    }
    fenvik<int> exist;
    exist.init(n);
    for (int i = 0; i < n; i++) {
        exist.set(i, 1);
    }
    for (int i = 0; i < n; i++) {
        if (exist.get(i) == 0) continue;
        exist.set(pair[i], 0);
        ans += exist.get(i + 1, pair[i]);
    }
    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