제출 #420391

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
420391		KoD	Arranging Shoes (IOI19_shoes)	C++17	30 / 100	51 ms	7092 KiB

shoes

#include <bits/stdc++.h>
#include "shoes.h"

using ll = long long;
template <class T> using Vec = std::vector<T>;

struct Fenwick {
	Vec<int> data;
	Fenwick(const int n): data(n + 1) {}
	void add(int i, const int x) {
		for (i += 1; i < (int) data.size(); i += i & -i) {
			data[i] += x;
		}
	}
	int get(int i) const {
		int x = 0;
		for (; i > 0; i -= i & -i) {
			x += data[i];
		}
		return x;
	}
	int fold(const int l, const int r) const {
		return get(r) - get(l);
	}
};

ll inversion(const Vec<int>& p) {
	const int n = (int) p.size();
	Fenwick fen(n);
	ll ret = 0;
	for (int i = 0; i < n; ++i) {
		ret += fen.fold(p[i] + 1, n);
		fen.add(p[i], 1);
	}
	return ret;
}

ll count_swaps(Vec<int> s) {
	const int n = (int) s.size();
	std::map<int, Vec<std::pair<int, bool>>> map;
	for (int i = 0; i < n; ++i) {
		if (s[i] > 0) {
			map[s[i]].emplace_back(i, true);
		} else {
			map[-s[i]].emplace_back(i, false);
		}
	}
	ll ret = 0;
	Fenwick fen(n);
	for (const auto& [x, vec] : map) {
		const int m = (int) vec.size();
		int pos = 0, neg = 0;
		Vec<int> assign(m);
		for (int i = 0; i < m; ++i) {
			const auto [j, f] = vec[i];
			fen.add(j, 1);
			if (f) {
				assign[2 * pos + 1] = i;
				pos += 1;
			} else {
				assign[2 * neg] = i;
				neg += 1;
			}
		}
		ret += inversion(assign);
		for (int i = 0; i < m / 2; ++i) {
			const auto [l, r] = std::minmax(vec[assign[2 * i]].first, vec[assign[2 * i + 1]].first);
			ret += r - l;
			ret -= fen.fold(l, r);
		}
		for (int i = 0; i < m; ++i) {
			fen.add(vec[i].first, -1);
		}
	}
	return ret;
}

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