Submission #1210959

#	Time	Username	Problem	Language	Result	Execution time	Memory
1210959		madamadam3	Arranging Shoes (IOI19_shoes)	C++20	100 / 100	449 ms	30944 KiB

shoes

#include "shoes.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int n;

struct Fenw {
	int n; vector<int> bit;

	Fenw(int N) {
		n = N;
		bit.assign(n, 0);
	}

	int g(int i) {
		return i & (i+1);
	}

	int h(int j) {
		return j | (j+1);
	}

	int query(int idx) {
		int res = 0;

		while (idx >= 0) {
			res += bit[idx];
			idx = g(idx) - 1;
		}

		return res;
	}

	void update(int idx, int delta) {
		while (idx < n) {
			bit[idx] += delta;
			idx = h(idx);
		}
	}

	void update(int l, int r, int delta) {
		update(l, delta);
		update(r+1, -delta);
	}
};

ll count_swaps(vector<int> s) {
	n = s.size() / 2;
	ll minimum = 0;

	auto fenw = Fenw(2*n);
	map<int, set<int>> shoes;
	set<int> used;

	for (int i = 0; i < 2*n; i++) {
		shoes[s[i]].insert(i);
	}

	for (int i = 0; i < 2*n; i++) {
		if (used.count(i)) continue;

		int size = s[i];
		int partner = *shoes[-size].begin();

		used.insert(i); used.insert(partner);
		shoes[size].erase(i); shoes[-size].erase(partner);

		int dist = (fenw.query(partner) + partner) - (fenw.query(i) + i) - 1;
		if (size > 0) dist++;
		minimum += dist;

		fenw.update(i, partner, 1);
	}

	return minimum;
}

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