Submission #251904

#	Time	Username	Problem	Language	Result	Execution time	Memory
251904		akat	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	88 ms	14884 KiB

shoes

#include "shoes.h"
using namespace std;
template<typename T>
struct BIT
{
	vector<T>it;
	BIT(int n,T s)
	{
		it = vector<T>(n,s);
	}
	void comb(T &x,T &y)
	{
		x += y;
	}
	void update(int x,T u)
	{
		while(x)
		{
			comb(it[x],u);
			x -= x&(-x);
		}
	}
	T query(int x)
	{
		T ans = it[0];
		while(x < (int)it.size())
		{
			comb(ans,it[x]);
			x += x&(-x);
		}
		return ans;
	}
};
long long count_swaps(vector<int> s)
{
	int n = s.size()/2, i;
	BIT<int>T(n * 2 + 1, 0);
	vector<vector<int>>memo(n * 2 + 1);
	for(i = n * 2 - 1; i >= 0; i--)
		memo[s[i] + n].push_back(i);
	long long ans = 0;
	for(i = 0; i < n * 2; i++)
	{
		int x = s[i] + n;
		int y = -s[i] + n;
		if(memo[x].size()==0 || memo[x].back() != i)continue;
		int z = memo[y].back();
		ans += z - i - T.query(i+1) + T.query(z + 1);
		if(s[i] < 0) ans --;
		T.update(z + 1,1);
		memo[x].pop_back();
		memo[y].pop_back();
	}
	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