| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 420441 | QCFium | Arranging Shoes (IOI19_shoes) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
int ri() {
int n;
scanf("%d", &n);
return n;
}
long long count_swaps(std::vector<int> a) {
assert(n <= 1000);
int n = a.size();
int res = 0;
while (a.size()) {
int t = std::find(a.begin(), a.end(), -a[0]) - a.begin();
res += t - 1;
if (a[0] > 0) res++;
a.erase(a.begin() + t);
a.erase(a.begin());
}
return res;
}
long long count_swaps_gu(std::vector<int> a) {
int n = a.size();
std::map<std::vector<int>, int> dist;
{
auto b = a;
std::sort(b.begin(), b.end());
do {
dist[b] = 1000000000;
} while (std::next_permutation(b.begin(), b.end()));
}
std::queue<std::vector<int> > que;
dist[a] = 0;
que.push(a);
while (que.size()) {
auto i = que.front();
que.pop();
for (int j = 0; j + 1 < n; j++) {
auto next = i;
std::swap(next[j], next[j + 1]);
if (dist[next] > dist[i] + 1) {
dist[next] = dist[i] + 1;
que.push(next);
}
}
}
int res = 1000000000;
for (auto i : dist) {
bool ok = true;
for (int j = 0; j < n; j += 2) {
if (i.first[j] > 0) ok = false;
if (i.first[j + 1] < 0) ok = false;
if (-i.first[j] != i.first[j + 1]) ok = false;
}
if (ok) res = std::min(res, i.second);
}
return res;
}
std::random_device rnd_dev;
std::mt19937 rnd(rnd_dev() ^ clock());
int rnd_int(int l, int r) { return std::uniform_int_distribution<>(l, r)(rnd); }
bool check() {
int n = rnd_int(1, 5);
std::vector<int> a;
for (int i = 0; i < n; i++) a.push_back(rnd_int(1, n));
for (int i = 0; i < n; i++) a.push_back(-a[i]);
std::shuffle(a.begin(), a.end(), rnd);
auto r0 = count_swaps(a);
auto r1 = count_swaps_gu(a);
if (r0 != r1) {
std::cerr << "!!! FAILED !!!" << std::endl;
for (auto i : a) std::cerr << i << " ";
std::cerr << std::endl;
std::cerr << "fast : " << r0 << std::endl;
std::cerr << "gu : " << r1 << std::endl;
return false;
}
std::cerr << "ok : ";
for (auto i : a) std::cerr << i << " ";
std::cerr << std::endl;
return true;
}
/*
int main() {
for (int i = 0; i < 100000; i++) if (!check()) {
std::cerr << "failed at " << i << std::endl;
return 0;
}
return 0;
}*/