Submission #1077793

#	Time	Username	Problem	Language	Result	Execution time	Memory
1077793		Boas	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	287 ms	27988 KiB

shoes

#include "shoes.h"

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define sz(x) (int)x.size()
#define pb push_back
#define loop(x, i) for (int i = 0; i < x; i++)
#define rev(x, i) for (int i = (int)x - 1; i >= 0; i--)
#define ALL(x) begin(x), end(x)
typedef signed i32;
typedef vector<i32> vi32;
typedef vector<int> vi;
typedef vector<bool> vb;
typedef vector<vi> vvi;
typedef vector<vb> vvb;

vi tree;
int treeN = 1;

int query(int i, int l, int r, int ql, int qr, int v)
{
	if (qr < l || r < ql)
		return 0;
	if (ql <= l && r <= qr)
	{
		if (v == 1)
			tree[i] = 1;
		return tree[i];
	}
	int m = (l + r) / 2;
	int res = query(2 * i, l, m, ql, qr, v) +
			  query(2 * i + 1, m + 1, r, ql, qr, v);
	tree[i] = tree[2 * i] + tree[2 * i + 1];
	return res;
}

int count_swaps(vi32 s)
{
	int n = sz(s);
	while (treeN < n)
		treeN *= 2;
	tree = vi(treeN * 2);
	vb vis(n);
	map<int, vi> ixs;
	rev(n, i)
	{
		ixs[s[i]].pb(i);
	}
	int res = 0;
	loop(n, i)
	{
		if (!vis[i])
		{
			int vl = s[i];
			int nxt = ixs[-vl].back();
			ixs[-vl].pop_back();
			res += (nxt - i - 1 - query(1, 0, treeN - 1, i + 1, nxt, 0));
			if (vl > 0)
				res++;
			vis[nxt] = 1;
			query(1, 0, treeN - 1, nxt, nxt, 1);
			ixs[vl].pop_back();
		}
	}
	return res;
}

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