Submission #822002

#	Time	Username	Problem	Language	Result	Execution time	Memory
822002		oscar1f	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	82 ms	18924 KiB

shoes

#include<bits/stdc++.h>
#include "shoes.h"

using namespace std;
using ll=long long;

const ll MAX_PAIRES=100*1000+5,DECA=(1<<18);
ll nbPaires,rep;
vector<ll> listePos[MAX_PAIRES][2];
vector<pair<ll,ll>> listePaire;
ll cumu[2*DECA];

void ajout(ll pos) {
	pos+=DECA;
	cumu[pos]=1;
	while (pos>1) {
		pos/=2;
		cumu[pos]=cumu[2*pos]+cumu[2*pos+1];
	}
}

ll somme(ll deb,ll fin) {
	if (deb==fin) {
		return cumu[deb];
	}
	if (deb%2==1) {
		return cumu[deb]+somme(deb+1,fin);
	}
	if (fin%2==0) {
		return cumu[fin]+somme(deb,fin-1);
	}
	return somme(deb/2,fin/2);
}

ll count_swaps(vector<int> s) {
	nbPaires=s.size()/2;
	for (ll i=0;i<2*nbPaires;i++) {
		if (s[i]>0) {
			listePos[s[i]][0].push_back(i);
		}
		else {
			listePos[-s[i]][1].push_back(i);
		}
	}
	for (ll i=0;i<MAX_PAIRES;i++) {
		for (ll j=0;j<(ll)listePos[i][0].size();j++) {
			listePaire.push_back({listePos[i][0][j],listePos[i][1][j]});
		}
	}
	sort(listePaire.begin(),listePaire.end(),[&](pair<ll,ll> a,pair<ll,ll> b) {
		return min(a.first,a.second)<min(b.first,b.second);
	});
	for (auto nouv:listePaire) {
		//cout<<nouv.first<<" "<<nouv.second<<endl;
		if (nouv.first>nouv.second) {
			rep--;
			swap(nouv.first,nouv.second);
		}
		rep+=nouv.second-nouv.first-somme(DECA+nouv.first,DECA+nouv.second);
		ajout(nouv.first);
		ajout(nouv.second);
	}
	return rep;
}

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