Submission #240846

#	Time	Username	Problem	Language	Result	Execution time	Memory
240846		ikura355	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	311 ms	274924 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 fen[maxn];

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);
}

void update(int x, int val) {
	x++;
	while(x > 0) {
		fen[x] += val;
		x -= x&-x;
	}
}

int sum(int x) {
	x++;
	int sum = 0;
	while(x <= n) {
		sum += fen[x];
		x += x&-x;
	}
	return sum;
}
 
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++) {
		int x = cost[i].second.first, y = cost[i].second.second;
		// 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 + sum(x) + sum(y) - 4 * i;
		update(x, 1); update(y, 1);
	}
 
	return ans;
}

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