Submission #231258

#	Time	Username	Problem	Language	Result	Execution time	Memory
231258		peijar	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	368 ms	76884 KiB

shoes

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

#define SZ(v) ((int)(v).size())
using ll = long long;

template<class T>
struct FenwickTree {
    vector<T> bit;
    int nb_elem;

    FenwickTree(int N) {
    	nb_elem = N;
    	bit.resize(nb_elem);
    	for (int i(0); i < nb_elem; ++i)
    		bit[i] = 0;
    }

    FenwickTree(vector<T> a) : FenwickTree(SZ(a)) {
        for (size_t i = 0; i < a.size(); i++)
            add(i, a[i]);
    }

    T sum(int r) {
        T ret = 0;
        for (; r >= 0; r = (r & (r + 1)) - 1)
            ret += bit[r];
        return ret;
    }

    T sum(int l, int r) {
        return sum(r) - sum(l - 1);
    }

    void add(int idx, T delta) {
        for (; idx < nb_elem; idx = idx | (idx + 1))
            bit[idx] += delta;
    }
};

ll count_swaps(vector<int> shoes)
{
	int nb_chaussures = SZ(shoes);

	FenwickTree<ll> fen = FenwickTree<ll>(nb_chaussures);
	ll nb_swaps(0);
	map<int, queue<int>> pos;
	pos[shoes[0]].push(0);
	for (int i(1); i < nb_chaussures; ++i)
	{
		if (pos.find(-shoes[i]) != pos.end() and SZ(pos[-shoes[i]]))
		{
			int where = pos[-shoes[i]].front(); pos[-shoes[i]].pop();

			nb_swaps += (i - where -1 + (shoes[i] < 0));
			nb_swaps -= fen.sum(where, i);
			fen.add(i, 1);
			fen.add(where, -1);
		}
		else
			pos[shoes[i]].push(i);
	}
	return nb_swaps;
}

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