Submission #828993

#	Time	Username	Problem	Language	Result	Execution time	Memory
828993		PurpleCrayon	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	57 ms	15768 KiB

shoes

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

#define sz(v) int(v.size())
#define ar array
typedef long long ll;

struct FT {
	vector<int> bit;
	FT(int n): bit(n) {}

	void upd(int i, int x) {
		for (; i < sz(bit); i |= i+1) bit[i] += x;
	}
	
	int qry(int i) {
		int ans = 0;
		for (++i; i > 0; i &= i-1) ans += bit[i-1];
		return ans;
	}

	int qry(int l, int r) {
		return qry(r) - qry(l-1);
	}
};

long long count_swaps(vector<int> s) {
	int n = sz(s) / 2;
	vector<vector<int>> left(n), right(n);
	for (int i = 0; i < 2 * n; i++) {
		int c = abs(s[i]) - 1;
		if (s[i] < 0) {
			left[c].push_back(i);
		} else {
			right[c].push_back(i);
		}
	}

	vector<ar<int, 2>> a;
	for (int c = 0; c < n; c++) {
		for (int i = 0; i < sz(left[c]); i++) {
			a.push_back({left[c][i], right[c][i]});
		}
	}

	ll ans = 0;
	for (int i = 0; i < n; i++) {
		if (a[i][0] > a[i][1]) {
			ans++;
			swap(a[i][0], a[i][1]);
		}
	}
	
	sort(a.begin(), a.end());
	// cout << "here" << endl;
	FT bit(2 * n);
	for (int i = 0; i < n; i++) {
		for (int x : a[i]) {
			// cout << x << endl;
			ans += bit.qry(x + 1, 2 * n - 1);
			bit.upd(x, +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