Submission #1138854

#	Time	Username	Problem	Language	Result	Execution time	Memory
1138854		anmattroi	Arranging Shoes (IOI19_shoes)	C++20	45 / 100	54 ms	9664 KiB

shoes

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

int n, m;
int tmp[maxn];
vector<int> P[maxn];
vector<int> 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++) {
        if (s[i] < 0) R.emplace_back(i);
        else P[s[i]].emplace_back(i);
    }
    reverse(R.begin(), R.end());
    for (int i = 1; i <= m; i++) reverse(P[i].begin(), P[i].end());

    for (int i = 1; i <= 2*n; i += 2) {
        int H = R.back(); R.pop_back();
        a[H] = i;
        int spr = -s[H];
        a[P[spr].back()] = i+1;
        P[spr].pop_back();
    }

    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: 0 / 20
• Subtask 3: 20 / 20
• Subtask 4: 15 / 15
• Subtask 5: 0 / 20
• Subtask 6: 0 / 15