Submission #295746

#	Time	Username	Problem	Language	Result	Execution time	Memory
295746		fire_cloud	Arranging Shoes (IOI19_shoes)	C++14	65 / 100	1093 ms	23032 KiB

shoes

#include "shoes.h"
#include <bits/stdc++.h>
#define ll long long int
#define maxn 110000
using namespace std;

bool visited[maxn];
set<ll>izq[maxn]; // siempre van a mantener los indices originales
set<ll>der[maxn]; // siempre van a mantener los indices originales

vector< pair<ll,ll> >segmentos; // siempre va a mantener los indices originales

ll verdadero_indice(ll x){
	ll suma = 0;
	for(ll i = 0;i<segmentos.size();i++){
		if(x>= segmentos[i].first  &&  x<= segmentos[i].second){
			suma++;
		}
	}
	return suma + x;
}

long long count_swaps(std::vector<int> s) {
	
	
	ll n = s.size()/2;

	ll x,y;
	ll swaps = 0;
	bool ok = true;
	for(ll i = 0; i < 2*n ; i++){
		if(s[i] < 0){
			if(i>n-1) ok =false;
			izq[s[i]*-1].insert(i);
		}
		else{
			if(i<=n-1) ok = false;
			der[s[i]].insert(i);
		}
	}	
	
	if(ok){
		for(ll i = 0; i<=n-1;i++){
			if(abs(s[i]) != abs(s[i+ n] )) ok =false;
		}
		if(ok){
			ll aux = n-1;
			return (aux*(aux+1))/2;
		}	
	}
	memset(visited, false,sizeof visited);
	// NUNCA vas a editar las posiciones del verdadero arreglo 
	for(ll i = 0; i < 2*n; ){
		if(visited[i]) {i++; continue;}   // si ya procesaste este numero
		visited[i] = true;
		if(s[i] > 0){
			swaps++;
			y = *izq[s[i]].begin();
			visited[y] = true;
			y = verdadero_indice(y);
			x = verdadero_indice(i);
			swaps += (y - x) - 1;
			segmentos.push_back( make_pair (i,*izq[s[i]].begin()) );
			izq[s[i]].erase( izq[s[i]].begin() );  
			der[s[i]].erase( i ); //der[s[i]].erase( der[s[i]].find(i) ); 
		}
		else{
			// s[i] = -2 (negativo)
			y = *der[s[i]*-1].begin();
			visited[y] = true;
			y = verdadero_indice(y);
			x = verdadero_indice(i);
			swaps+=(y - x)-1;
			segmentos.push_back(make_pair( i,*der[s[i]*-1].begin()) );
			izq[s[i]*-1].erase(i);
			der[s[i]*-1].erase(der[s[i]*-1].begin());
		}
		
		i++;	
	}

 return swaps;
}

Compilation message (stderr)

shoes.cpp: In function 'long long int verdadero_indice(long long int)':
shoes.cpp:15:16: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   15 |  for(ll i = 0;i<segmentos.size();i++){
      |               ~^~~~~~~~~~~~~~~~~

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