Submission #1098743

#	Time	Username	Problem	Language	Result	Execution time	Memory
1098743		Noname_1900	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	102 ms	32340 KiB

shoes

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

vector<long long> posDroites[NMAX+1];
vector<long long> posGauches[NMAX+1];
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];
long long iPosGauche[NMAX];
//long long vals[NMAX];
bool vus[NMAX*2];
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
		{
			posGauches[-i].push_back(a);
		}
	}
	//cout << "okmj" << endl;
	long long somme = 0;
	//long long decalage = 0;
	init(1, 0, s.size());
	int iEmePair = 0;
	for(long long iPair = 0; iPair < s.size(); iPair++)
	{
		int val = s[iPair];
		if(vus[iPair])	continue;
		if(val < 0)
		{
			long long type = abs(val);
			iPosGauche[type]++;
			long long pos2 = posDroites[type][iPosDroite[type]]+trouver(1, posDroites[type][iPosDroite[type]], posDroites[type][iPosDroite[type]]+1);
			somme += (pos2-(iEmePair*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]]);
			vus[posDroites[type][iPosDroite[type]]] = true;
			iPosDroite[type]++;
		}
		else
		{
			long long type = abs(val);
			iPosDroite[type]++;
			long long pos1 = posGauches[type][iPosGauche[type]]+trouver(1, posGauches[type][iPosGauche[type]], posGauches[type][iPosGauche[type]]+1);
			somme += (pos1-iEmePair*2);
			chang(1, 0, posGauches[type][iPosGauche[type]]);
			vus[posGauches[type][iPosGauche[type]]] = true;
			iPosGauche[type]++;
		}
		
		//cout << posGauche[iPair] << endl;
	//	cout << pos1 << " ";
		
		
		//cout << posDroites[type].front()+trouver(1, posDroites[type].front(), posDroites[type].front()+1) << endl;
		
		
		
		
		
		//somme += (pos2-pos1)-1;
		//cout << "res : " << ((pos1-iPair*2)) << " " << (pos2-(iPair*2+1)) << " " << somme << endl;
		iEmePair++;
	}
	return somme;
}

Compilation message (stderr)

shoes.cpp: In function 'long long int count_swaps(std::vector<int>)':
shoes.cpp:56:25: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |  for(long long a = 0; a < s.size(); a++)
      |                       ~~^~~~~~~~~~
shoes.cpp:74:33: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |  for(long long iPair = 0; iPair < s.size(); iPair++)
      |                           ~~~~~~^~~~~~~~~~
shoes.cpp:54:12: warning: unused variable 'nbVal' [-Wunused-variable]
   54 |  long long nbVal = s.size()/2;
      |            ^~~~~

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