Submission #295729

#TimeUsernameProblemLanguageResultExecution timeMemory
295729fire_cloudArranging Shoes (IOI19_shoes)C++14
50 / 100
1096 ms44024 KiB
#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; for(ll i = 0; i < 2*n ; i++){ if(s[i] < 0){ izq[s[i]*-1].insert(i); } else{ der[s[i]].insert(i); } } 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++){
      |               ~^~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...