Submission #501629

#	Time	Username	Problem	Language	Result	Execution time	Memory
501629		fusabile	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	201 ms	30288 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};

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;

struct Treap{ /// hash = 96814
    int len;
    const int ADD = 1000010;
    const int MAXVAL = 1000000010;
    unordered_map <long long, int> mp; /// Change to int if only int in treap
    tree<long long, null_type, less<long long>, rb_tree_tag, tree_order_statistics_node_update> T;

    Treap(){
        len = 0;
        T.clear(), mp.clear();
    }

    inline void clear(){
        len = 0;
        T.clear(), mp.clear();
    }

    inline void insert(long long x){
        len++, x += MAXVAL;
        int c = mp[x]++;
        T.insert((x * ADD) + c);
    }

    inline void erase(long long x){
        x += MAXVAL;
        int c = mp[x];
        if (c){
            c--, mp[x]--, len--;
            T.erase((x * ADD) + c);
        }
    }

    /// 1-based index, returns the K'th element in the treap, -1 if none exists
    inline long long kth(int k){
        if (k < 1 || k > len) return -1;
        auto it = T.find_by_order(--k);
        return ((*it) / ADD) - MAXVAL;
    }

    /// Count of value < x in treap
    inline int count(long long x){
        x += MAXVAL;
        int c = mp[--x];
        return (T.order_of_key((x * ADD) + c));
    }

    /// Number of elements in treap
    inline int size(){
        return len;
    }
};
vector<int> mp[200042];
inline int fix(int x)
{
	return x + (x<0)*(100000 - 2*x);
}
ll count_swaps(vector<int> S)
{
	int n = sz(S);
	ll ans = 0;
	//unordered_map<int, queue<int>> mp;
	for (int i = n-1; i >= 0; i--)
	{
		mp[fix(S[i])].push_back(i);
	}
	vector<int> offset(n);
	Treap update;
	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[fix(-S[i])].back();
		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];
		auto get_offset = [&](int m) {
			int result = update.size() - update.count(m);
			return result;
		};
		ans += z - offset[i] - get_offset(i) + get_offset(j);
		if (min(x, y) == i + 1)
			offset[i] += 2;
		if (i + 1 <= j - 1)
			update.insert(j-1);
		mp[fix(S[x])].pop_back();
		mp[fix(S[y])].pop_back();
		S[x] = inf;
		S[y] = inf;
	}
	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