Submission #568441

#	Time	Username	Problem	Language	Result	Execution time	Memory
568441		d4xn	Arranging Shoes (IOI19_shoes)	C++17	10 / 100	1 ms	296 KiB

shoes

#include "shoes.h"

#include <bits/stdc++.h>
using namespace std; 

#define vi vector<int>
#define ll long long

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

	map<int, int> last; // ultima aparicion de zapatilla con sz x
	vi next(n); // idx de la pareja mas cercana de la zapatilla i
	vi nextSame(n); // idx de la zapatilla mas cercana de la misma sz
	for (int i = n-1; i >= 0; i--) {
		last[s[i]] = i;
		next[i] = last[-s[i]];
		nextSame[i] = last[s[i]];
		//next[i] = (last.count(-s[i]) ? last[-s[i]] : -1);
	}

	vi vis(n, 0);
	map<int, int> newNext; // nueva pareja mas cercana para zapatilla de sz x
	for (int i = 0; i < n; i++) {
		if (vis[i]) continue;

		if (newNext.count(s[i])) {
			if (newNext[s[i]] < next[i]) {
				newNext.erase(s[i]);
			}
			else {
				next[i] = newNext[s[i]];
			}
		}
		
		if (s[i] < 0) {
			// buscar zapatilla derecha de sz abs(s[i]) mas cercana
			// y ponerla a la derecha
			int idx = next[i];
			swaps += idx - i - 1;
			newNext[s[i]] = nextSame[idx];
			vis[idx] = 1;
		}
		else {
			// buscar zapatilla izquierda de sz abs(s[i]) mas cercana
			// y ponerla a la izquierda
			int idx = next[i];
			swaps += idx - i;
			newNext[s[i]] = nextSame[idx];
			vis[idx] = 1;
		}
	}

	return swaps;
}

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