Submission #240834

#	Time	Username	Problem	Language	Result	Execution time	Memory
240834		ikura355	Arranging Shoes (IOI19_shoes)	C++14	50 / 100	1121 ms	272892 KiB

shoes

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

#define ll long long
#define pii pair<int,int>
#define X first
#define Y second

const int maxn = 2e5 + 5;

int n, m;
queue<int> pos[maxn][2];
pii a[maxn];
int pick[maxn], cost[maxn];

int getcost(pii x) {
	if(x.first < x.second) return x.first + x.second - 1;
	return x.first + x.second;
}

long long count_swaps(std::vector<int> s) {
	n = s.size(); m = 0;
	for(int i = 0; i < n; i++) {
		int x = abs(s[i]);
		pos[x][s[i] < 0].push(i);

		// printf("%d: %d\n",x,s[i]<0);

		if(!pos[x][0].empty() && !pos[x][1].empty()) {
			a[++m] = {pos[x][1].front(), pos[x][0].front()};
			// printf("{%d, %d}\n",a[m].first,a[m].second);
			pos[x][0].pop(); pos[x][1].pop();
		}
	}

	ll ans = 0;
	for(int i = 1; i <= m; i++) {
		pick[i] = 0;
		cost[i] = getcost(a[i]);
	}
	for(int cur = 1; cur <= m; cur++) {
		int best = 0;
		for(int i = 1; i <= m; i++) {
			if(pick[i]) continue;
			if(!best || cost[i] < cost[best]) best = i;
		}
		// printf("pick %d %d\n",a[best].first,a[best].second);
		ans += cost[best];
		pick[best] = 1;
		for(int i = 1; i <= m; i++) {
			if(pick[i]) continue;
			cost[i] += (a[best].first > a[i].first) + (a[best].second > a[i].first) - 2;
			cost[i] += (a[best].first > a[i].second) + (a[best].second > a[i].second) - 2;
		}
	}

	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