Submission #256831

#	Time	Username	Problem	Language	Result	Execution time	Memory
256831		atoiz	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	220 ms	21308 KiB

shoes

#include "shoes.h"
#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>
#include <cstring>
#include <unordered_map>

using namespace std;
using ll = long long;

#define FOR(i, a, b) for (int i = a; i <= b; ++i)
#define FORA(i, a) for (auto &i : a)
#define FORB(i, a, b) for (int i = a; i >= b; --i)

ll count_swaps(vector<int> s) {
	int n = (int) s.size();
	unordered_map<int, vector<int>> pos;
	FORB(i, n - 1, 0) pos[s[i]].push_back(i);

	vector<int> bit(n + 1, 0);
	ll ans = 0;
	FOR(i, 0, n - 1) if (pos[s[i]].back() == i) {
		pos[s[i]].pop_back();
		if (s[i] < 0) {
			int j = pos[-s[i]].back();
			pos[-s[i]].pop_back();

			ans += i;
			for (int x = i + 1; x > 0; x -= x & (-x)) ans -= bit[x];
			for (int x = i + 1; x <= n; x += x & (-x)) ++bit[x];

			ans += j;
			for (int x = j + 1; x > 0; x -= x & (-x)) ans -= bit[x];
			for (int x = j + 1; x <= n; x += x & (-x)) ++bit[x];
		} else {
			int j = pos[-s[i]].back();
			pos[-s[i]].pop_back();

			ans += j;
			for (int x = j + 1; x > 0; x -= x & (-x)) ans -= bit[x];
			for (int x = j + 1; x <= n; x += x & (-x)) ++bit[x];

			ans += i;
			for (int x = i + 1; x > 0; x -= x & (-x)) ans -= bit[x];
			for (int x = i + 1; x <= n; x += x & (-x)) ++bit[x];
		}
	}

	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