| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 295704 | fire_cloud | Arranging Shoes (IOI19_shoes) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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.length()/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(i+1 < 2*n){ // si el programa falla quitar esto
if(abs(s[i]) == abs(s[i+1]) && s[i] < 0 && s[i] > 0){ // si ya estan ordenados ejemplo -2 2
i+=2;
continue;
}
}
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;
}