Submission #1248589

#	Time	Username	Problem	Language	Result	Execution time	Memory
1248589		M_W_13	Arranging Shoes (IOI19_shoes)	C++20	50 / 100	1096 ms	12872 KiB

shoes

#include "shoes.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for (int i = 0; i < (n); i++)
#define st first
#define nd second
#define pb push_back

long long count_swaps(std::vector<int> s) {
	int n = ((int)s.size())/2;
	vector<ll> lewe[n + 1];
	vector<ll> prawe[n + 1];
	rep(i, 2 * n) {
		int x = abs(s[i]);
		if (s[i] < 0) {
			lewe[x].pb(i);
		}
		else {
			prawe[x].pb(i);
		}
	}
	ll ans = 0;
	rep(i, n + 1) {
		int sz = lewe[i].size();
		rep(j, sz) {
			if (lewe[i][j] < prawe[i][j]) {
				ans--;
			}
		}
	}
	for (ll k = 0; k < 2 * n; k += 2) {
		ll mini = 1e9;
		int it = 0;
		rep(i, n + 1) {
			int sz = lewe[i].size();
			if (sz > 0) {
				ll dl = lewe[i][0] + prawe[i][0] - 2 * k;
				if (dl < mini) {
					mini = dl;
					it = i;
				}
			}
		}
		int p1 = lewe[it][0];
		int p2 = prawe[it][0];
		ans += mini;
		s[p1] = 0;
		s[p2] = 0;
		int c = 0;
		for (int i = 2 * n - 1; i >= k; i--) {
			if (s[i] == 0) {
				c++;
			}
			else {
				s[i + c] = s[i];
			}
		}
		rep(i, n + 1) {
			lewe[i].clear();
			prawe[i].clear();
		}
		for (int i = k + 2; i < 2 * n; i++) {
			int x = abs(s[i]);
			if (s[i] < 0) {
				lewe[x].pb(i);
			}
			else {
				prawe[x].pb(i);
			}
		}
	}
	return ans;
}

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