Submission #1015303

#	Time	Username	Problem	Language	Result	Execution time	Memory
1015303		inesfi	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	188 ms	275708 KiB

shoes

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

#define ll long long
const int TAILLEMAXI=2*100*1000+2,DECALAGE=(1<<18);
int dejavu[TAILLEMAXI];
ll rep,autre;
deque<int> parpointures[TAILLEMAXI][2];
int arbresomme[DECALAGE*2];

int somme(int deb,int fin){
	if (deb==fin){
		return arbresomme[deb];
	}
	if (deb%2==1){
		return arbresomme[deb]+somme(deb+1,fin);
	}
	if (fin%2==0){
		return arbresomme[fin]+somme(deb,fin-1);
	}
	return somme(deb/2,fin/2);
}
void remonter(int endroit){
	if (endroit==0){
		return ;
	}
	arbresomme[endroit]=arbresomme[endroit*2]+arbresomme[endroit*2+1];
	remonter(endroit/2);
}

ll count_swaps(vector<int> chaussures) {
	for (int i=0;i<(int)chaussures.size();i++){
		if (chaussures[i]<0){
			parpointures[-chaussures[i]][0].push_back(i);
		}
		else {
			parpointures[chaussures[i]][1].push_back(i);
		}
	}
	for (int i=0;i<(int)chaussures.size();i++){
		if (dejavu[i]==0){
			if (chaussures[i]>0){
				autre=parpointures[chaussures[i]][0].front();
				rep+=autre-i-somme(i+DECALAGE,autre+DECALAGE);
				arbresomme[autre+DECALAGE]++;
				remonter((autre+DECALAGE)/2);
				dejavu[autre]=1;
			}
			else {
				autre=parpointures[-chaussures[i]][1].front();
				rep+=autre-i-1-somme(i+DECALAGE,autre+DECALAGE);
				arbresomme[autre+DECALAGE]++;
				remonter((autre+DECALAGE)/2);
				dejavu[autre]=1;
			}
			parpointures[abs(chaussures[i])][0].pop_front();
			parpointures[abs(chaussures[i])][1].pop_front();
		}
	}
	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