Submission #418594

#	Time	Username	Problem	Language	Result	Execution time	Memory
418594		gromperen	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	77 ms	12712 KiB

shoes

#include "shoes.h"
#include <bits/stdc++.h>
using ll = long long;

using namespace std;


const int MAXN = 2e5+5;
int n;

//vector<vector<pair<int,int>>> v(MAXN, vector<pair<int,int>>);

struct fenwick {
	int tree[MAXN];
	void update(int i, ll v) {
		for (; i < MAXN; i += (i & -i)) tree[i] += v;
	}

	ll query(int i) {
		ll s = 0;
		for (; i > 0; i -= (i & -i)) s += tree[i];
		return s;
	}
} fen;

long long count_swaps(std::vector<int> s) {
	n = (int)s.size() / 2;
	ll ans = 0;
	vector<pair<int,int>>v;
	vector<pair<int,int>> ord[MAXN];

	for (int i = 0; i < 2*n; ++i) {
		ord[abs(s[i])].emplace_back(s[i], i);
	}

	for (int i = 1; i <= n; ++i) {
		int m = ord[i].size();
		sort(ord[i].begin(), ord[i].end());
		for (int j = 0; j < m / 2; ++j) {
			int fi = ord[i][j].second;
			int se = ord[i][j + m/2].second;

			fi++; se++;
			if (fi > se) { // SHOES ARE LEFT & RIGHT SWAPPED
				swap(fi, se);
				ans++;
			}
			v.emplace_back(fi, se);
		}
	}

	for (int i = 1; i <= 2*n; ++i) fen.update(i, 1);

	sort(v.begin(),v.end());
	int m = v.size();
	for (int i = 0; i < m; ++i) {
		int f = v[i].first;
		int s = v[i].second;
		ans += fen.query(s-1) - fen.query(f);
		fen.update(f, -1);
		fen.update(s, -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