Submission #439049

#	Time	Username	Problem	Language	Result	Execution time	Memory
439049		sean617	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	218 ms	139728 KiB

shoes

#include "shoes.h"
#define N 200005
#include <cstdio>
#include <iostream>
#include <queue>

using namespace std;

typedef long long ll;

ll n, t, ans = 0, pa[N], s[N];
queue<ll> qu[N];
ll f_num(int p) {
	if (p < 0) return (n / 2 - p);
	else return p;
}

ll f(ll p) {
	ll re =0;
	while (p >= 1) {
		re += s[p];
		p -= (p & -p);
	}
	return re;
}

void g(ll p) {
	while (p <= n) {
		s[p]++;
		p += (p & -p);
	}
}

long long count_swaps(std::vector<int> a) {
    ll i, t, rt, tt, mi;
	n = a.size();
	for (i = 1; i <= n; i++) {
		t = f_num(a[i - 1]);
		rt = f_num(-a[i - 1]);
		if (qu[rt].empty()) {
			qu[t].push(i);
		} else {
			tt = qu[rt].front(); qu[rt].pop();
			pa[tt] = i;
			pa[i] = tt;
		}
	}
	for (i = 1; i <= n; i++) {
		if (i < pa[i]) {
			mi = f(pa[i]) - f(i);
			ans += (pa[i] - i - 1 - mi);
			if (a[i - 1] > 0) ans++;
			g(pa[i]);
		}
	}
	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