Submission #1210957

#	Time	Username	Problem	Language	Result	Execution time	Memory
1210957		madamadam3	Arranging Shoes (IOI19_shoes)	C++20	50 / 100	1096 ms	30788 KiB

shoes

#include "shoes.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int n;

ll count_swaps(vector<int> s) {
	n = s.size() / 2;
	ll minimum = 0;

	vector<int> current_location(2*n, 0);
	map<int, set<int>> shoes;
	set<int> used;

	for (int i = 0; i < 2*n; i++) {
		shoes[s[i]].insert(i);
	}

	for (int i = 0; i < 2*n; i++) {
		if (used.count(i)) continue;

		int size = s[i];
		int partner = *shoes[-size].begin();

		used.insert(i); used.insert(partner);
		shoes[size].erase(i); shoes[-size].erase(partner);

		int dist = (current_location[partner] + partner) - (current_location[i] + i) - 1;
		if (size > 0) dist++;
		minimum += dist;

		for (int k = i; k < 2*n; k++) current_location[k]++;
		for (int k = partner; k < 2*n; k++) current_location[k]--;
	}

	return minimum;
}

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