| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 736979 | tvladm2009 | Arranging Shoes (IOI19_shoes) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#include "shoes.h"
using namespace std;
typedef long long ll;
const int N_MAX = 100000;
int A[2 * N_MAX + 2];
deque <int> Minus[N_MAX + 2], Plus[N_MAX + 2];
int nxt[2 * N_MAX + 2];
bool used[N_MAX + 2];
int BIT[2 * N_MAX + 2];
void update(int pos, int val) {
for (int i = pos; i <= 2 * N_MAX; i += i & -i) {
BIT[i] += val;
}
}
int query(int pos) {
int answer = 0;
for (int i = pos; i >= 1; i -= i & -i) {
answer += BIT[i];
}
return answer;
}
int count_swaps(int S[]) {
int N = sizeof(S) / sizeof(int);
N /= 2;
for (int i = 1; i <= 2 * N; i++) {
A[i] = S[i - 1];
}
for (int i = 1; i <= 2 * N; i++) {
if (A[i] < 0) {
Minus[A[i] * -1].push_back(i);
} else {
Plus[A[i]].push_back(i);
}
}
for (int i = 1; i <= 2 * N; i++) {
if (A[i] < 0) {
if (Plus[A[i] * -1].empty() == false) {
nxt[i] = Plus[A[i] * -1].front();
}
Minus[A[i] * -1].pop_front();
} else {
if (Minus[A[i]].empty() == false) {
nxt[i] = Minus[A[i]].front();
}
Plus[A[i]].pop_front();
}
}
ll answer = 0;
for (int i = 1; i <= 2 * N; i++) {
if (used[i] == false) {
int j = nxt[i];
int between = query(j - 1) - query(i);
int swaps = (j - i - 1) - between;
if (A[i] > 0) {
swaps++;
}
answer += swaps;
used[i] = true;
used[j] = true;
update(i, +1);
update(j, +1);
}
}
return answer;
}