Submission #985652

#	Time	Username	Problem	Language	Result	Execution time	Memory
985652		Zbyszek99	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	185 ms	15956 KiB

shoes

#include <bits/stdc++.h>
#include "shoes.h"
#define rep(i,n) for(int i = 0; i < n; i++)
#define ll long long
#define ss second 
#define ff first
using namespace std;

int wiel = 1024*512-1;
ll drzewo[1024*512-1];
int n;

void add_t(int akt, int p1, int p2, int s1, int s2)
{
	if(p2 < s1 || p1 > s2) return;
	if(p1 >= s1 && p2 <= s2)
	{
		drzewo[akt-1]++;
		return;
	}
	add_t(akt*2,p1,(p1+p2)/2,s1,s2);
	add_t(akt*2+1,(p1+p2)/2+1,p2,s1,s2);
}

int query_t(int akt)
{
	int wyn = drzewo[akt-1];
	if(akt != 1) wyn += query_t(akt/2);
	return wyn;
}

long long count_swaps(vector<int> s) 
{
	ll ans = 0;
	n = (int)s.size();
	set<pair<int,int>> se;
	rep(i,n)
	{
		se.insert({s[i],i});
	}
	//se.erase({s[0],0});
	rep(i,n)
	{
		if(se.find({s[i],i}) == se.end()) continue;
		//cout << i << " i\n";
		set<pair<int,int>>::iterator t_ = se.lower_bound({-s[i],-1});
		pair<int,int> t = *t_;
		//cout << t.ff << " " << t.ss << " t\n";
		se.erase(se.find({t.ff,t.ss}));
		se.erase(se.find({s[i],i}));
		ll odl1 = query_t(wiel/2+1+i);
		ll odl2 = query_t(wiel/2+1+t.ss);
		add_t(1,0,wiel/2,t.ss,wiel/2);
		//cout << odl1 << " " << odl2 << " odl\n";
		if(s[i] < 0)
		{
			ans += -(odl2-odl1) + t.ss - i -1;
		}
		else
		{
			ans +=-(odl2-odl1) + t.ss - i;
		}
		//cout << ans << "\n\n";
	}
	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