Submission #1138862

#	Time	Username	Problem	Language	Result	Execution time	Memory
1138862		anmattroi	Arranging Shoes (IOI19_shoes)	C++20	100 / 100	173 ms	32116 KiB

shoes

#include "shoes.h"
#include <bits/stdc++.h>
#define maxn 100005
using namespace std;

int n, m;
int tmp[maxn];
set<int> O[maxn], C[maxn], R;
int a[2*maxn], bit[2*maxn];

void upd(int u, int d) {
    for (int i = u; i > 0; i -= i & -i) bit[i] += d;
}

int get(int u) {
    int kq = 0;
    for (int i = u; i <= n+n; i += i & -i) kq += bit[i];
    return kq;
}

long long count_swaps(vector<int> s) {
	n = s.size()/2;
	for (int i = 0, id = 0; i < s.size(); i++)
        if (s[i] > 0) tmp[++id] = s[i];
    sort(tmp + 1, tmp + n + 1);
    m = unique(tmp + 1, tmp + n + 1) - tmp - 1;

    for (int i = 0; i < s.size(); i++) {
        int mult = (s[i] > 0 ? 1 : -1);
        s[i] = mult * (lower_bound(tmp + 1, tmp + m + 1, s[i]*mult) - tmp);
    }
    for (int i = 0; i < s.size(); i++) {
        R.insert(i);
        if (s[i] < 0) O[-s[i]].insert(i);
        else C[s[i]].insert(i);
    }
    for (int i = 1; i <= 2*n; i += 2) {
        int H = *R.begin(); R.erase(R.begin());
        int spr = s[H];
        if (spr < 0) {
            a[H] = i;
            a[*C[-spr].begin()] = i+1;
            R.erase(*C[-spr].begin());
            O[-spr].erase(O[-spr].begin());
            C[-spr].erase(C[-spr].begin());
        } else {
            a[H] = i+1;
            a[*O[spr].begin()] = i;
            R.erase(*O[spr].begin());
            O[spr].erase(O[spr].begin());
            C[spr].erase(C[spr].begin());
        }

    }

    int64_t inv = 0;
    for (int i = 0; i < 2*n; i++) {
        inv += get(a[i]+1);
        upd(a[i], 1);
    }
    return inv;

}

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