Submission #1077780

#	Time	Username	Problem	Language	Result	Execution time	Memory
1077780		Boas	Arranging Shoes (IOI19_shoes)	C++17	50 / 100	1097 ms	25292 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;

int count_swaps(vi32 s)
{
	int n = sz(s);
	vb vis(n);
	vi freeSpaces(n);
	map<int, vi> ixs;
	rev(n, i)
	{
		ixs[s[i]].pb(i);
	}
	auto rSum = [&](int l, int r) -> int
	{
		int res = 0;
		for (int i = l; i <= r; i++)
			res += freeSpaces[i];
		return res;
	};
	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 - rSum(i + 1, nxt - 1));
			if (vl > 0)
				res++;
			vis[nxt] = 1;
			freeSpaces[nxt] = 1;
			ixs[vl].pop_back();
		}
	}
	return res;
}

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