제출 #1196396

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1196396		stdfloat	Arranging Shoes (IOI19_shoes)	C++20	100 / 100	435 ms	146764 KiB

shoes

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

using ll = long long;

ll count_swaps(vector<int> s) {
	int n = (int)s.size();
	s.insert(s.begin(), 0);

	map<int, queue<int>> m;
	for (int i = 1; i <= n; i++)
		m[s[i]].push(i);

	vector<int> fn(n + 1);
	auto upd = [&](int x) {
		for (int i = x; i <= n; i += i & -i)
			fn[i]++;
	};
	auto fnd = [&](int x) {
		int res = 0;
		for (int i = x; i > 0; i -= i & -i)
			res += fn[i];

		return res;
	};

	ll cnt = 0;
	for (int i = 1; i <= n; i++) {
		if (i != m[s[i]].front()) continue;

		m[s[i]].pop();

		int j = m[-s[i]].front(); m[-s[i]].pop();

		cnt += j - i - (fnd(j) - fnd(i)) - (s[i] < 0);

		upd(j);
	}

	return cnt;
}

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