Submission #830170

#	Time	Username	Problem	Language	Result	Execution time	Memory
830170		GusterGoose27	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	108 ms	139552 KiB

shoes

#include "shoes.h"

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 2e5+5;

typedef long long ll;

int bit[MAXN];
int nxt[MAXN];
int n;

void upd(int p, int v) {
	for (; p < n; p |= (p+1)) bit[p] += v;
}

int sum(int p) {
	int s = 0;
	for (p++; p > 0; p &= (p-1)) s += bit[p-1];
	return s;
}

queue<int> occ[MAXN];
bool matched[MAXN];

int _abs(int x) {
	return x < 0 ? -x : x;
}

ll count_swaps(vector<int> s) {
	n = s.size();
	for (int i = 0; i < n; i++) {
		int x = _abs(s[i]);
		if (occ[x].size() && s[occ[x].front()] != s[i]) {
			nxt[occ[x].front()] = i;
			occ[x].pop();
		}
		else occ[x].push(i);
	}
	for (int i = 1; i <= n/2; i++) assert(occ[i].empty());
	ll ans = 0;
	for (int i = 0; i < n; i++) {
		if (matched[i]) continue;
		int dist = nxt[i]+sum(nxt[i])-(s[i] < 0);
		ans += dist;
		upd(i, -1);
		upd(nxt[i], -1);
		matched[i] = matched[nxt[i]] = 1;
	}
	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