Submission #1152438

#	Time	Username	Problem	Language	Result	Execution time	Memory
1152438		Esgeer	Arranging Shoes (IOI19_shoes)	C++20	100 / 100	108 ms	31752 KiB

shoes

#include "shoes.h"
#include <bits/stdc++.h>
#define int long long
#define rint int32_t
#define vr vector<rint>
#pragma GCC optimize("O3")
#define vi vector<int>
#define vb vector<bool>
#define F(i, s, e) for(int i = s; i < e; i++)
#define sp <<' '<<
#define pii pair<int, int>
#define fi first
#define se second
#define pb push_back
#define vvi vector<vi>
#define vpi vector<pii>
#define vvpi vector<vpi>
#define endl '\n'

using namespace std;

const int N = 2e5+5;
int t[N];

void update(int idx, int val) {
	idx++;
	while(idx > 0 && idx < N) {
		t[idx] += val;
		idx += (idx & -idx);
	}
}

int query(int idx) {
	idx++;
	int res = 0;
	while(idx > 0 && idx < N) {
		res += t[idx];
		idx -= (idx & -idx);
	}
	return res;
}

int query(int l, int r) {
	if(l > r) return 0;
	return query(r) - query(l-1);
}

long long count_swaps(vr a) {
	// find the leftest shoe that was not paired yet -> shoe x
	// find the closest unpaired possible-pair for x
	// add the distance between to ans
	// mark both paired

	int n = a.size();
	vector<bool> paired(n, 0);
	set<int> lefts[n+1];
	set<int> rights[n+1];

	F(i, 0, n) {
		update(i, 1);
		if(a[i] < 0) lefts[-a[i]].insert(i);
		else rights[a[i]].insert(i);
	}

	int ans = 0;
	F(i, 0, n) {
		if(paired[i]) continue;
		int sz = abs(a[i]);
		if(a[i] < 0) {
			int per = *rights[sz].begin();
			//cout << i sp per << endl;

			ans += query(i+1, per-1);

			paired[i] = 1;
			paired[per] = 1;

			rights[sz].erase(per);
			lefts[sz].erase(i);

			update(per, -1);
			update(i, -1);
		} else {
			int per = *lefts[sz].begin();
			//cout << i sp per << endl;

			ans += query(i, per-1);

			paired[i] = 1;
			paired[per] = 1;

			lefts[sz].erase(per);
			rights[sz].erase(i);

			update(per, -1);
			update(i, -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