Submission #1064006

#	Time	Username	Problem	Language	Result	Execution time	Memory
1064006		jamjanek	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	87 ms	22572 KiB

shoes

#include "shoes.h"
#include<bits/stdc++.h>
using namespace std;
bool usu[200010];
set<int>zbiory[200010];
const int base = 1<<18;
int tree[2*base];
int odczyt(int x){
	x+=base;
	int res = 0;
	while(x>0){
//		printf("%d: %d\n", x, tree[x]);
		res+=tree[x];
		x/=2;
	}
	return res;
}
void odejmij(int w, int l, int p, int a, int b){
	if(p<a || b<l)return ;
	if(a<=l && p<=b){
		tree[w]--;
		return;
	}
	odejmij(w*2, l, (l+p)/2, a, b);
	odejmij(w*2+1, (l+p)/2+1, p, a, b);
}
long long count_swaps(std::vector<int> s) {
	int n = s.size()/2;
	for(int i=0;i<2*n;i++){
		zbiory[s[i]+n].insert(i);
		tree[i+base] = i;
	}
	long long wynik = 0;
	for(int start = 0; start<2*n;start++){
		if(usu[start])continue;
		int kolor = s[start];
		int pierwsza = *zbiory[n-kolor].begin();
//		printf("%d %d %d  %d\n", start, kolor, pierwsza, odczyt(pierwsza));
		if(kolor>0)wynik++;
		wynik+=odczyt(pierwsza)-1;
		odejmij(1, 0, base-1, start, base-1);
		odejmij(1, 0, base-1, pierwsza, base-1);
		zbiory[n-kolor].erase(pierwsza);
		zbiory[kolor+n].erase(start);
		usu[start] = 1;
		usu[pierwsza] = 1;
//		printf("%d\n", wynik);
	}
	return wynik;
}

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