Submission #295828

#	Time	Username	Problem	Language	Result	Execution time	Memory
295828		fire_cloud	Arranging Shoes (IOI19_shoes)	C++14	0 / 100	8 ms	10752 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<ll>negativos;
vector<ll>positivos;
vector< pair<ll,ll> >segmentos; // siempre va a mantener los indices originales


long long caso(vector<int>s){
	
	ll j,n = 0, p = 0,ans = 0;
	ll buscar = (abs(s[0])) * -1; // declarar arreglo s
	ll negativo = buscar;
	ll positivo = negativo * -1;
	for(ll i = 0; i < 2*n; i++){
		if(s[i] == 0) continue;
		if(buscar == s[i]){
			if(s[i]>0) p++;
			else n++;
			buscar*=-1;
			continue;
		}
		if(buscar == negativo){
		
			j = negativos[n];
			s[j] = 0;
			ans+=j-i;
			n++;
			p++;
		
		}
		else{
			j = positivos[p];
			s[j] = 0;
			ans+=j-i;
			n++;
			p++;
			
		}
	}
	return ans;
}

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) {
	
	bool casoo = true;
	ll n = s.size()/2;

	ll x,y,variable = -1;
	ll swaps = 0;
	bool ok = true;
	for(ll i = 0; i < 2*n ; i++){
		if(variable == -1){variable = abs(s[i]);}
		else{
			if(variable != abs(s[i])) casoo = false;
		}
		if(s[i] < 0){
			negativos.push_back(i);
			if(i>n-1) ok =false;
			izq[s[i]*-1].insert(i);
		}
		else{
			positivos.push_back(i);
			if(i<=n-1) ok = false;
			der[s[i]].insert(i);
		}
	}	
	if(casoo) return caso(s);
	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 caso(std::vector<int>)':
shoes.cpp:20:5: warning: unused variable 'positivo' [-Wunused-variable]
   20 |  ll positivo = negativo * -1;
      |     ^~~~~~~~
shoes.cpp: In function 'long long int verdadero_indice(long long int)':
shoes.cpp:52: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]
   52 |  for(ll i = 0;i<segmentos.size();i++){
      |               ~^~~~~~~~~~~~~~~~~

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