Submission #587101

#	Time	Username	Problem	Language	Result	Execution time	Memory
587101		Zanite	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	250 ms	278356 KiB

shoes

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

using ll	= long long;
using pii	= pair<int, int>;
using pll	= pair<ll, ll>;

#define fi	first
#define se	second

struct FenwickTree {
	ll sz;
	vector<ll> BIT;

	FenwickTree(ll sz) : sz(sz) {
		BIT.assign(sz + 1, 0);
	}

	void update(ll idx, ll val) {
		for (; idx <= sz; idx += (idx & -idx)) {
			BIT[idx] += val;
		}
	}

	ll sum(ll idx) {
		ll ret = 0;
		for (; idx > 0; idx -= (idx & -idx)) {
			ret += BIT[idx];
		}
		return ret;
	}
};

ll count_swaps(vector<int> s) {
	int n = s.size();

	vector<int> rel(n);
	vector<deque<int>> occ(n, deque<int>(0));
	vector<pii> leftShoes;
	vector<pair<int, pii>> ordered;

	for (int i = 0; i < n; i++) {
		if (s[i] < 0) leftShoes.push_back({i, -s[i]});
		else occ[s[i]].push_back(i);
	}

	vector<deque<int>> tocc = occ;

	for (auto &[idx, typ] : leftShoes) {
		int right = tocc[typ].front();
		tocc[typ].pop_front();

		int d = right + idx - (int)(right < idx);
		ordered.push_back({d, {idx, typ}});
	}
	sort(ordered.begin(), ordered.end());

	int placed = 0;
	for (auto &[d, p] : ordered) {
		int idx, typ;
		tie(idx, typ) = p;

		rel[placed++] = idx + 1;
		rel[placed++] = occ[typ].front() + 1;
		occ[typ].pop_front();
	}

	ll ans = 0;
	FenwickTree F(n);
	reverse(rel.begin(), rel.end());
	for (auto i : rel) {
		F.update(i, 1);
		ans += F.sum(i-1);
	}

	return ans;
}

// Grader

#ifdef Zanite

int main() {
	int n;
	assert(1 == scanf("%d", &n));
	vector<int> S(2 * n);
	for (int i = 0; i < 2 * n; i++)
		assert(1 == scanf("%d", &S[i]));
	fclose(stdin);

	long long result = count_swaps(S);

	printf("%lld\n", result);
	fclose(stdout);
	return 0;
}

#endif

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