Submission #292113

#	Time	Username	Problem	Language	Result	Execution time	Memory
292113		PeppaPig	Arranging Shoes (IOI19_shoes)	C++14	50 / 100	1098 ms	12568 KiB

shoes

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

#define long long long
#define pii pair<int, int>
#define x first
#define y second

using namespace std;

const int N = 2e5 + 5;

int n;
map<int, int> mp[2];

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

	long ans = 0;
	for(int i = 0; i < n; i += 2) {
		if(s[i] == -s[i + 1]) {
			if(s[i] > 0) swap(s[i], s[i + 1]), ++ans;	
			continue;
		}
		mp[0].clear(), mp[1].clear();
		for(int j = n - 1; j >= i; j--) {
			if(s[j] < 0) mp[0][abs(s[j])] = j;
			else mp[1][abs(s[j])] = j;
		}
		
		int id = -1, cnt = 1e9;
		for(pii p : mp[0]) {
			int a = p.y, b = mp[1][p.x];
			if(a - i + b - i - 1 + (a > b) < cnt) {
				cnt = a - i + b - i - 1 + (a > b);
				id = p.x;
			}
		}
		ans += cnt;
		int l = mp[0][id], r = mp[1][id];

		if(l > r) ++r;
		while(l != i) swap(s[l - 1], s[l]), --l;
		while(r != i + 1) swap(s[r - 1], s[r]), --r;
	}
	return ans;
}

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