Submission #1174933

#	Time	Username	Problem	Language	Result	Execution time	Memory
1174933		Clan328	Arranging Shoes (IOI19_shoes)	C++17	50 / 100	1104 ms	1114112 KiB

shoes

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

using namespace std;

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

	// Compress
	set<int> visited;
	for (int i = 0; i < 2*n; i++) {
		visited.insert(abs(s[i]));
	}
	map<int, int> mapper;
	int idx = 1;
	for (auto x : visited) {
		mapper[x] = idx++;
	}

	for (int i = 0; i < 2*n; i++) {
		if (s[i] > 0) s[i] = mapper[s[i]];
		else s[i] = -mapper[-s[i]];
	}

	vector<vector<int>> left(n+1), right(n+1);
	for (int i = 0; i < 2*n; i++) {
		if (s[i] < 0) left[abs(s[i])].push_back(i);
		else right[abs(s[i])].push_back(i);
	}

	int curr = -1, calc = 1e7;
	for (int i = 1; i <= n; i++) {
		if (left[i].size() == 0) continue;
		int tmp = left[i][0]+right[i][0]-((left[i][0] < right[i][0])? 1 : 0);
		if (tmp < calc) {
			curr = i;
			calc = tmp;
		}
	}
	
	assert(curr != -1);

	vector<int> newS;
	for (int i = 0; i < 2*n; i++) {
		if (i == left[curr][0]) continue;
		if (i == right[curr][0]) continue;

		newS.push_back(s[i]);
	}

	return calc + count_swaps(newS);
}

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