이 제출은 이전 버전의 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<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;
}
컴파일 시 표준 에러 (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++){
| ~^~~~~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |