Submission #143658

#	Time	Username	Problem	Language	Result	Execution time	Memory
143658		mosesmayer	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	262 ms	122920 KiB

shoes

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

const int mxsz = 1e5 + 5;
const int MX = 2e5;
int n;
deque<int> dq[mxsz];
int match[MX + 5];
bool done[MX + 5];
long long ans = 0, invcnt = 0;

struct FenwickTree{
	int ft[MX + 5];
	FenwickTree(){}
	void upd(int p, int v){
		for (; p <= MX; p += p & -p) ft[p] += v;
	}
	int get(int p){
		int ret = 0;
		for (; p > 0; p -= p & -p) ret += ft[p];
		return ret;
	}
} ft;

long long count_swaps(std::vector<int> s) {
	n = s.size(); n >>= 1;
	for (int i = 0; i < 2 * n; i++){
		int u = abs(s[i]);
		if (s[i] < 0){
			if (!dq[u].empty() && s[dq[u].back()] > 0){
				int v = dq[u].back(); dq[u].pop_back();
				match[i] = v; match[v] = i;
				invcnt++;
			} else dq[u].push_back(i);
		} else {
			if (!dq[u].empty() && s[dq[u].front()] < 0){
				int v = dq[u].front(); dq[u].pop_front();
				match[i] = v; match[v] = i;
			} else dq[u].push_front(i);
		}
	}
	for (int i = 0; i < 2 * n; i++){
		if (done[i]) continue;
		int u = match[i];
		ans += u - i - 1 - (ft.get(u+1) - ft.get(i));
		ft.upd(i + 1, 1); ft.upd(u+1, 1);
		done[u] = done[i] = 1;
	}
	return ans + invcnt;
}

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