제출 #1242750

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1242750		haithamcoder	Arranging Shoes (IOI19_shoes)	C++20	10 / 100	0 ms	328 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 arrive = a[i] * 2;
		c += abs(wer[i + 1] - (arrive)) + abs(wer[-(i + 1)] - (arrive - 1));

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

		if (wer[-(i + 1)] > wer[i + 1]) {c--;}
		if (wer[i + 1] > arrive) {c--;}
		if (wer[-(i + 1)] > arrive) {c--;}
	}

	ans = min(ans, c);

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

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

			if (wer[-(i + 1)] < wer[i + 1]) {cur--;}
			if (wer[i + 1] > arrive) {cur--;}
			if (wer[-(i + 1)] > arrive) {cur--;}
		}

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

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