Submission #1146391

#	Time	Username	Problem	Language	Result	Execution time	Memory
1146391		KickingKun	Arranging Shoes (IOI19_shoes)	C++20	25 / 100	15 ms	2632 KiB

shoes

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

#define ll long long

ll sub2(vector <int> S) {
	int n = S.size() / 2;
	vector <int> pre(n + 1, -1);
	vector <pair <int, int>> shoes;
	for (int i = 0; i < S.size(); i++) {
		int p = pre[abs(S[i])];
		if (p != -1) {
			shoes.emplace_back(p, i), pre[abs(S[i])] = -1;
			if (S[p] > 0) swap(shoes.back().first, shoes.back().second);
		}
		else pre[abs(S[i])] = i;
	}
	
	vector <int> permu(n); iota(permu.begin(), permu.end(), 0);
	ll res = 1e18;
	do {
		ll cost = 0; vector <bool> mark(S.size());
		for (int pos = 0; pos < S.size(); pos++) {
			int sh = (pos & 1) ? shoes[permu[pos >> 1]].second : shoes[permu[pos >> 1]].first;
			int real_sh = sh; mark[sh] = true;
			for (int i = sh + 1; i < S.size(); i++) real_sh += mark[i];
			cost += abs(real_sh - pos);
		}
		res = min(res, cost);
	} while (next_permutation(permu.begin(), permu.end()));
	return res;
}

ll sub3(vector <int> S) {
	vector <int> L;
	for (int i = 0; i < S.size(); i++)
		if (S[i] < 0) L.emplace_back(i);
	
	ll ans = 0;
	for (int i = 0; i < L.size(); i++)
		ans += abs(L[i] - i * 2);
	return ans;
}

ll sub4(vector <int> S) {
	int n = S.size() / 2; // 1 + ... + n - 1
	return 1ll * n * (n - 1) / 2;
}

ll count_swaps(vector <int> S) {
	if (S.size() == 2) return (S[0] > 0); // sub1
	if (S.size() <= 16) return sub2(S);
	bool s3 = true;
	for (int i = 1; i < S.size(); i++)
		if (abs(S[i - 1]) != abs(S[i])) s3 = false;
	if (s3) return sub3(S);
	return sub4(S);
}

#ifdef cute
int main() {
	cout << count_swaps({2, 1, -1, -2});
}
#endif

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