Submission #1098677

#	Time	Username	Problem	Language	Result	Execution time	Memory
1098677		Noname_1900	Arranging Shoes (IOI19_shoes)	C++17	45 / 100	95 ms	26704 KiB

shoes

#include "shoes.h"
#include<bits/stdc++.h>
using namespace std;
const int NMAX = 100000;

vector<long long> posDroites[NMAX+1];
long long posGauche[NMAX];
long long arbre[NMAX*3*2];
long long push[NMAX*3*2];
pair<long long, long long> debFin[NMAX*3*2];
long long iPosDroite[NMAX];
void init(long long noeud, long long deb, long long fin)
{
	debFin[noeud] = {deb, fin};
	if(deb == fin-1)	return;
	long long mil = (deb+fin)/2;
	init(noeud*2, deb, mil);
	init(noeud*2+1, mil, fin);
}
long long trouver(long long noeud, long long deb, long long fin)
{
	arbre[noeud] += push[noeud];
	if(debFin[noeud].first != debFin[noeud].second-1)
	{
		push[noeud*2] += push[noeud];
		push[noeud*2+1] += push[noeud];
	}
	push[noeud] = 0;
	if((debFin[noeud].first >= fin) || (debFin[noeud].second <= deb))	return 0;
	if((debFin[noeud].first >= deb) && (debFin[noeud].second <= fin))	return arbre[noeud];
	return trouver(noeud*2,deb, fin)+trouver(noeud*2+1, deb, fin);
}
long long chang(long long noeud, long long deb, long long fin)
{
	arbre[noeud] += push[noeud];
	if(debFin[noeud].first < debFin[noeud].second-1)
	{
		push[noeud*2] += push[noeud];
		push[noeud*2+1] += push[noeud];
	}
	push[noeud] = 0;
	if((debFin[noeud].first >= fin) || (debFin[noeud].second <= deb))	return arbre[noeud];
	if((debFin[noeud].first >= deb) && (debFin[noeud].second <= fin))	
	{
		push[noeud]++;
		return arbre[noeud]+1;
	}
	return arbre[noeud] = chang(noeud*2,deb, fin)+chang(noeud*2+1, deb, fin);
}
long long count_swaps(std::vector<int> s) {
	long long nbVal = s.size()/2;
	long long nbG = 0;
	for(long long a = 0; a < s.size(); a++)
	{
		long long i = s[a];
		if(i > 0)
		{
			posDroites[i].push_back(a);
		}
		else
		{
			posGauche[nbG] = a;	
			nbG++;
		}
	}
	//cout << "okmj" << endl;
	long long somme = 0;
	//long long decalage = 0;
	init(1, 0, s.size());
	for(long long iPair = 0; iPair < nbVal; iPair++)
	{
		long long pos1 = posGauche[iPair]+trouver(1, posGauche[iPair], posGauche[iPair]+1);
		//cout << posGauche[iPair] << endl;
	//	cout << pos1 << " ";
		somme += (pos1-iPair*2);
		long long type = abs(s[posGauche[iPair]]);
		//cout << posDroites[type].front()+trouver(1, posDroites[type].front(), posDroites[type].front()+1) << endl;
		
		
		chang(1, 0, posGauche[iPair]);
		
		long long pos2 = posDroites[type][iPosDroite[type]]+trouver(1, posDroites[type][iPosDroite[type]], posDroites[type][iPosDroite[type]]+1);
		somme += (pos2-(iPair*2+1));
	//	cout << pos2 << endl;
	//	cout << trouver(1, posDroites[type][iPosDroite[type]], posDroites[type][iPosDroite[type]]+1) << endl;
		chang(1, 0, posDroites[type][iPosDroite[type]]);
		iPosDroite[type]++;
		//somme += (pos2-pos1)-1;
		//cout << "res : " << ((pos1-iPair*2)) << " " << (pos2-(iPair*2+1)) << " " << somme << endl;
	}
	return somme;
}

Compilation message (stderr)

shoes.cpp: In function 'long long int count_swaps(std::vector<int>)':
shoes.cpp:53:25: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |  for(long long a = 0; a < s.size(); a++)
      |                       ~~^~~~~~~~~~

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