Submission #760187

#	Time	Username	Problem	Language	Result	Execution time	Memory
760187		thinknoexit	Arranging Shoes (IOI19_shoes)	C++17	45 / 100	102 ms	71268 KiB

shoes

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int fw[200200];
void update(int v, int w) {
    for (int i = v + 1;i <= 200000;i += i & -i) fw[i] += w;
}
int query(int v) {
    int ans = 0;
    for (int i = v + 1;i > 0;i -= i & -i) ans += fw[i];
    return ans;
}
ll count_swaps(vector<int> v) {
    ll ans = 0;
    int n = (int)v.size();
    queue<int> pos[100100];
    queue<pair<int, int>> q;
    for (int i = 0;i < n;i++) {
        if (v[i] < 0) {
            q.push({ -v[i],i });
        }
        else {
            pos[v[i]].push(i);
        }
    }
    int cnt = 0;
    while (!q.empty()) {
        auto x = q.front();
        q.pop();
        int val = x.first, i = x.second;
        int j = pos[val].front();
        if (i < j) {
            ans += query(i) + i - cnt;
            update(1, 1), update(i + 1, -1);
            ans += query(j) + j - (cnt + 1);
            update(1, 1), update(j + 1, -1);
        }
        else {
            ans += query(j) + j - cnt;
            update(1, 1), update(j + 1, -1);
            ans += query(i) + i - cnt;
            update(1, 1), update(i + 1, -1);
        }
        pos[val].pop();
        cnt += 2;
    }
    return ans;
}

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