Submission #760202

#	Time	Username	Problem	Language	Result	Execution time	Memory
760202		thinknoexit	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	146 ms	139724 KiB

shoes

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll fw[200200];
queue<int> pos[100100], pos2[100100];
bool ch[200200];
void update(int v, int w) {
    for (int i = v + 1;i <= 200000;i += i & -i) fw[i] += w;
}
ll query(int v) {
    ll 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();
    for (int i = 0;i < n;i++) {
        if (v[i] < 0) {
            pos2[-v[i]].push(i);
        }
        else {
            pos[v[i]].push(i);
        }
    }
    for (int i = 0;i < n;i++) {
        if (ch[i]) continue;
        if (v[i] < 0) {
            v[i] = -v[i];
            int nowpos = i + query(i);
            int j = pos[v[i]].front();
            ch[j] = 1;
            ans += j + query(j) - nowpos - 1;
            update(1, 1), update(j + 1, -1);
        }
        else {
            int nowpos = i + query(i);
            int j = pos2[v[i]].front();
            ch[j] = 1;
            ans += j + query(j) - nowpos;
            update(1, 1), update(j + 1, -1);
        }
        pos[v[i]].pop();
        pos2[v[i]].pop();
    }
    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