Submission #501521

#	Time	Username	Problem	Language	Result	Execution time	Memory
501521		fusabile	Arranging Shoes (IOI19_shoes)	C++17	50 / 100	1064 ms	147212 KiB

shoes

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

#ifdef LOCAL
#include "dbg.h"
#else
#define dbg(...)
#endif
#define sz(s) (int)(s).size()
#define all(x) (x).begin(), (x).end()

typedef long long ll;
const int inf = INT_MAX;
const int dx[] = {1, -1, 0, 0};
const int dy[] = {0, 0, 1, -1};

ll count_swaps(vector<int> S)
{
	int n = sz(S);
	ll ans = 0;
	unordered_map<int, queue<int>> mp;
	for (int i = 0; i < n; i++)
		mp[S[i]].push(i);
	vector<pair<int, int>> v;
	v.reserve(n);
	for (int i = 0; i < n;)
	{
		if (S[i] == inf) 
		{
			i++;
			continue;
		}
		vector<array<int, 3>> best; // best[i] = {left_index, right_index, swap_count}
		int j = mp[-S[i]].front();
		assert(j < n);
		auto get_offset = [&](int index) {
			int l = -1, r = sz(v);
			while (l + 1 < r)
			{
				int m = l + (r-l)/2;
				if (v[m].first > index)
					r = m;
				else
					l = m;
			}
			r--;
			int offset = 0;
			while (r >= 0)
			{
				offset += index >= v[r].first && index <= v[r].second;
				r--;
			}
			return offset;
		};
		if (S[i] < 0)
			best.push_back({i, j, j - i - 1});
		else
			best.push_back({j, i, j - i});
		i++;
		if (abs(S[i]) != abs(S[i-1]))
		{
			if (S[i] < 0)
				best.push_back({i, j, j - i + 1});
			else
				best.push_back({j, i, j - i + 2});
		}
		i--;
		sort(best.begin(), best.end(), [](auto &x, auto &y) { return x[2] < y[2]; });
		auto [x, y, z] = best[0];
		ans += z - get_offset(i) + get_offset(j);
		if (min(x, y) == i + 1)
		{
			v.push_back({i, i});
			v.push_back({i, i});
		}
		if (i + 1 <= j - 1)
			v.push_back({i + 1, j - 1});
		mp[S[x]].pop();
		mp[S[y]].pop();
		S[x] = inf;
		S[y] = inf;
	}
	return ans;	
}

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