Submission #240842

#	Time	Username	Problem	Language	Result	Execution time	Memory
240842		ikura355	Arranging Shoes (IOI19_shoes)	C++14	50 / 100	1111 ms	274156 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];
vector<pair<ll, pair<int,int>>> cost;

int calc(pair<int,int> x, pair<int,int> y) {
	return (x.first > y.first) + (x.first > y.second) + (x.second > y.first) + (x.second > y.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();
		}
	}

	for(int i=1;i<=m;i++) {
		int x = a[i].first, y = a[i].second;
		cost.push_back({x + y - (x < y), {x, y}});
	}
	sort(cost.begin(), cost.end());

	ll ans = 0;
	for(int i=0;i<m;i++) {
		// printf("%lld %d %d: %lld\n",cost[i].first,cost[i].second.first,cost[i].second.second,cost[i].first - 4 * i);
		ans += cost[i].first - 4 * i;
		for(int j=i+1;j<m;j++) {
			// printf("\tcalc = %d\n",calc(cost[i].second, cost[j].second));
			cost[j].first += calc(cost[i].second, cost[j].second);
		}
	}
 
	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