Submission #1047884

#	Time	Username	Problem	Language	Result	Execution time	Memory
1047884		clementine	Arranging Shoes (IOI19_shoes)	C++17	50 / 100	266 ms	555724 KiB

shoes

#include "shoes.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int st[400000];

void update(int cur, int lo, int hi, int l, int r, int val)
{
	if ((r < lo) || (l > hi))
	{
		return;
	}
	if(( lo >= l ) && ( hi <= r))
	{
		st[cur] +=val;
		return;
	}
	int mid = (lo + hi) / 2;
	update(2 * cur, lo, mid, l , r, val);
	update(2 * cur + 1, mid + 1, hi, l, r, val);
}

int query(int cur, int lo, int hi, int idx)
{
	if (lo == hi)
	{
		return st[cur];
	}
	int mid = (lo + hi) / 2;

	if( idx <= mid)
	{
		return st[cur] + query( 2 * cur, lo, mid, idx);
	}
	else
	{
		return st[cur] + query( 2 * cur + 1, mid + 1, hi, idx);
	}
}

long long count_swaps(vector<int> s) {

	int n = s.size();
	vector<deque<int>> szidx( 2 * n + 1);
	vector<bool> there(n + 1, 1);
	for(int i = 1; i <= n; i ++)
	{
		int val = s[i-1];
		szidx[val + n].push_back(i);
	}
	/*
	for(auto sz: szidx)
	{
		for (auto a : sz)
		{
			cout << a << " ";
		}
		cout << '\n';
	}
	cout << '\n';
	*/
	ll ans = 0;
	vector<int> sorted;
	for(int i = 1; i <=n; i ++)
	{
		if(there[i])
		{
			int pair = szidx[(0-s[i-1]) + n].front();
			szidx[(0-s[i-1]) + n].pop_front();
			szidx[s[i-1] + n].pop_front();
			ans += pair + (query(1,1,n,pair)) - (i + query(1,1,n,i)) - 1;
			//cout <<  i << " " << pair << " : " <<pair + (query(1,1,n,pair)) - (i + query(1,1,n,i)) - 1 << '\n';
			there[pair] = false;
			sorted.push_back(s[i-1]);
			sorted.push_back(s[pair-1]);
			update(1,1,n, i, pair, 1 );
		}
		
	}
	for(int i = 0; i < n; i +=2)
	{
		if(sorted[i] > 0)
		{
			ans +=1;
		}
	}
	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