Submission #1146421

#	Time	Username	Problem	Language	Result	Execution time	Memory
1146421		KickingKun	Arranging Shoes (IOI19_shoes)	C++20	85 / 100	1093 ms	14784 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> le[n + 1], ri[n + 1];
	vector <pair <int, int>> shoes;
	for (int i = 0; i < S.size(); i++) {
		if (S[i] < 0) le[-S[i]].emplace_back(i);
		else ri[S[i]].emplace_back(i);
	}
	
	for (int val = 1; val <= n; val++)
		for (int i = 0; i < le[val].size(); i++)
			shoes.emplace_back(le[val][i], ri[val][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 sub5(vector <int> S) {
	int n = S.size() / 2;
	vector <int> le[n + 1], ri[n + 1];
	vector <pair <int, int>> shoes;
	for (int i = 0; i < S.size(); i++) {
		if (S[i] < 0) le[-S[i]].emplace_back(i);
		else ri[S[i]].emplace_back(i);
	}
	
	for (int val = 1; val <= n; val++)
		for (int i = 0; i < le[val].size(); i++)
			shoes.emplace_back(le[val][i], ri[val][i]);
	
	sort (shoes.begin(), shoes.end(), [&] (pair <int, int> u, pair <int, int> v) {
		return min(u.first, u.second) < min(v.first, v.second);
	});
	
	ll cost = 0; vector <bool> mark(S.size());
	for (int pos = 0; pos < S.size(); pos++) {
		int sh = (pos & 1) ? shoes[pos >> 1].second : shoes[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);
	}
	return cost;
}

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

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

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