Submission #692476

#	Time	Username	Problem	Language	Result	Execution time	Memory
692476		zeroesandones	Arranging Shoes (IOI19_shoes)	C++17	10 / 100	3 ms	304 KiB

shoes

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

using ll = long long;
using vi = vector<long long>;

#define pb emplace_back

long long count_swaps(vector<int> s) {
	int n = (s.size());

	ll ans = 0;

	int change[n] = {};

	set<int> L[n + 5], R[n + 5];
	bool done[n] = {};

	for(int i = 0; i < n; ++i) {
		if(s[i] < 0) {
			L[-s[i]].insert(i);
		} else {
			R[s[i]].insert(i);
		}
	}

	for(int i = 0; i < n; ++i) {
		if(done[i]) continue;
		if(s[i] < 0) {
			L[-s[i]].erase(L[-s[i]].begin());
			auto it = *R[-s[i]].begin();
			for(int j = i; j <= it; ++j) {
				ans += change[j];
			}
			done[it] = true;
			for(int j = i + 1; j <= it; ++j) {
				++change[j];
			}
			R[-s[i]].erase(R[-s[i]].begin());
		} else {
			++ans;
			R[s[i]].erase(R[s[i]].begin());
			auto it = *L[s[i]].begin();
			for(int j = i; j <= it; ++j) {
				ans += change[j];
			}
			done[it] = true;
			for(int j = i + 1; j <= it; ++j) {
				++change[j];
			}
			L[s[i]].erase(L[s[i]].begin());
		}
	}

	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