Submission #784133

#	Time	Username	Problem	Language	Result	Execution time	Memory
784133		Alfraganus	Arranging Shoes (IOI19_shoes)	C++14	10 / 100	1 ms	300 KiB

shoes

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

long long count_swaps(vector<int> a) {
	long long n = a.size() / 2;
	if(n == 1)return a[0] > 0;
	vector<vector<int>> pos(2 * n + 1);
	for(int i = 2 * n - 1; i >= 0; i --)
		pos[a[i] + n].push_back(i);
	long long ans = 0;
	for(int i = 0; i < 2 * n; i ++){
		if(a[i] != 0){
			ans += pos[-a[i] + n].back() - i;
			if(a[i] < 0)ans --;
			a[pos[-a[i] + n].back()] = 0;
			pos[-a[i] + n].pop_back();
			pos[a[i] + n].pop_back();
			a[i] = 0;
		}
	}
	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