# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
975600 | attky | Arranging Shoes (IOI19_shoes) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
struct Pair {
int gauche, droite, nb;
void nbDeplacement() {
nb = gauche + droite;
}
bool operator< (Pair other) {
return nb < other.nb;
}
};
int segtree[524288], tailleIntervalle[524288][2];
void define() {
for(int loop = 0; loop < 262144; ++loop) {
tailleIntervalle[loop+262144][0] = loop+1;
tailleIntervalle[loop+262144][1] = loop+1;
}
for(int loop = 262143; loop >= 1; --loop) {
tailleIntervalle[loop][0] = tailleIntervalle[loop*2][0];
tailleIntervalle[loop][1] = tailleIntervalle[loop*2+1][1];
}
for(int loop = 1; loop < 524288; ++loop) {
segtree[loop] = 0;
}
}
void add(int debut, int pos) {
if(tailleIntervalle[pos][0] >= debut) {
segtree[pos]++;
}
else {
int gauche = 2*pos, droite = 2*pos+1;
if(tailleIntervalle[gauche][1] >= debut) {
add(debut, gauche);
}
if(tailleIntervalle[droite][1] >= debut) {
add(debut, droite);
}
}
}
int number(int pos) {
int nombre = segtree[pos];
if(pos > 1) {
nombre += number(pos/2);
}
return nombre;
}
int64_t count_swap(vector<int> S) {
int n = S.size()/2;
vector<vector<int>> shoeLeft(n);
vector<vector<int>> shoeRight(n);
for(int loop = 0; loop < S.size(); ++loop) {
if(S[loop] > 0) {
shoeRight[S[loop]-1].push_back(loop);
}
else {
shoeLeft[-(S[loop])-1].push_back(loop);
}
}
vector<Pair> pair;
for(int loop = 0; loop < n; ++loop) {
for(int looping = 0; looping < shoeLeft[loop].size(); ++looping) {
pair.push_back({shoeLeft[loop][looping], shoeRight[loop][looping]});
}
}
for(int loop = 0; loop < n; ++loop) {
pair[loop].nbDeplacement();
}
sort(pair.begin(), pair.end());
long long int nbDeplacement = 0;
for(int loop = 0; loop < n; ++loop) {
int g = pair[loop].gauche, d = pair[loop].droite;
int change = -1;
if(d < g) {
change++;
}
int ng = max(0, g-number(g+262144));
int nd = max(0, d-number(d+262144));
add(g+1, 1);
add(d+1, 1);
nbDeplacement += ng + nd + change;
}
return nbDeplacement;
}