Submission #330828

#	Time	Username	Problem	Language	Result	Execution time	Memory
330828		arbor	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	85 ms	12896 KiB

shoes

#include <bits/stdc++.h>
#define all(x) x.begin(), x.end()
using namespace std;
using ll = long long;
using pii = pair<int, int>;
const int MN = 2e5 + 5;
int n, b[MN];
void upd(int i, int v) {
    for (; i < MN; i += i & -i) b[i] += v;
}
int get(int i) {
    int r = 0;
    for (; i; i -= i & -i) r += b[i];
    return r;
}
vector<pii> id[MN];

ll count_swaps(vector<int> a) {
    ll ans = 0;
    n = a.size() / 2;
    for (int i = 0; i < 2 * n; i++) id[abs(a[i])].emplace_back(a[i], i + 1);
    vector<pii> v;
    for (int i = 1; i <= n; i++) {
        sort(all(id[i]));
        int h = id[i].size() / 2;
        for (int j = 0; j < h; j++) {
            int l = id[i][j].second;
            int r = id[i][j + h].second;
            if (l > r) ans++, swap(l, r);
            v.emplace_back(l, r);
        }
    }
    for (int i = 1; i <= 2 * n; i++) upd(i, 1);
    sort(all(v));
    for (pii p : v) {
        ans += get(p.second - 1) - get(p.first);
        upd(p.first, -1), upd(p.second, -1);
    }
    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