Submission #1242742

#	Time	Username	Problem	Language	Result	Execution time	Memory
1242742		haithamcoder	Arranging Shoes (IOI19_shoes)	C++20	0 / 100	0 ms	324 KiB

shoes

#include "shoes.h"
#include<bits/stdc++.h>
using namespace std;
// typedef long long ll;
#define ll int

#define db(x) cerr << #x << " = " << x << " | "
#define dbg(x) cerr << #x << " = " << x << "\n"

void pr(vector<ll> a) {
	for (auto x : a) cout << x << " ";
	cout << "\n";
}

long long count_swaps(std::vector<int> s) {
	ll n = s.size()/2;

	vector<ll> a(n);
	for (ll i = 0; i < n; i++) {
		a[i] = i + 1;
	}

	ll p = 1;
	vector<ll> pl(2 * n + 1);
	map<ll, ll> trans;
	for (ll i = 0; i < 2 * n; i++) {
		if (s[i] > 0) {
			pl[i + 1] = p;
			trans[s[i]] = p;
			p++; 
		}
	}

	for (ll i = 0; i < 2 * n; i++) {
		if (s[i] < 0) {
			pl[i + 1] = -trans[-s[i]];
		}
	}

	map<ll, ll> wer;
	for (ll i = 1; i <= 2 * n; i++) {
		wer[pl[i]] = i;
	}
	// pr(pl);

	ll ans = 1e7;
	ll c = 0;
	for (ll i = 0; i < n; i++) {
		ll num = i + 1;
		c += abs(wer[num] - (2 * a[i] - 1)) + abs(wer[-num] - (2 * a[i]));

	// db(abs(wer[num] - (2 * a[i] - 1))); db(abs(wer[-num] - (2 * a[i])));

		if (wer[-num] < wer[num]) {c--;}
		if (wer[num] > a[i] * 2 + 1) {c--;}
		if (wer[-num] > a[i] * 2 + 1) {c--;}
	}

	ans = min(ans, c);

	while (next_permutation(a.begin(), a.end())) {
		ll cur = 0;
		for (ll i = 0; i < n; i++) {
			ll num = i + 1;
			cur += abs(wer[num] - (2 * a[i] - 1)) + abs(wer[-num] - (2 * a[i]));

			// db(abs(wer[num] - (2 * a[i] - 1))); db(abs(wer[-num] - (2 * a[i])));

			if (wer[-num] < wer[num]) {cur--;}
			if (wer[num] > a[i] * 2 + 1) {cur--;}
			if (wer[-num] > a[i] * 2 + 1) {cur--;}
		}

		ans = min(ans, cur);
	}
	return ans;
}

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