Submission #1025429

#	Time	Username	Problem	Language	Result	Execution time	Memory
1025429		Luvidi	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	63 ms	14968 KiB

shoes

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

long long count_swaps(std::vector<int> s) {
	int n=s.size()/2;
	vector<int> v[2*n+1];
	for(int i=2*n-1;i>-1;i--)v[s[i]+n].push_back(i+1);
	int bit[2*n+1];
	memset(bit,0,sizeof(bit));
	auto upd=[&](int l,int r){
		int i=l;
		while(i<=2*n){
			bit[i]++;
			i+=i&(-i);
		}
		if(r==2*n)return;
		i=r+1;
		while(i<=2*n){
			bit[i]--;
			i+=i&(-i);
		}
	};
	auto sum=[&](int i){
		int s=0;
		while(i){
			s+=bit[i];
			i-=i&(-i);
		}
		return s;
	};
	long long ans=0;
	for(int i=1;i<=2*n;i+=2){
		int l=1,r=2*n;
		while(l<r){
			int m=(l+r)/2;
			if(sum(m)+m>=i)r=m;
			else l=m+1;
		}
		int x=s[l-1];
		int idx=v[-x+n].back();
		v[-x+n].pop_back();
		v[x+n].pop_back();
		ans+=(long long)(sum(idx)+idx-1-i+(x>0));
		upd(1,idx-1);
	}
	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