| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 424548 | KoD | Teams (IOI15_teams) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#include "scales.h"
template <int N, int... SZ> struct ArrayImpl { using type = std::array<typename ArrayImpl<SZ...>::type, N>; };
template <int N> struct ArrayImpl<N> { using type = std::array<int, N>; };
template <int... SZ> using Array = typename ArrayImpl<SZ...>::type;
template <class T> using Vec = std::vector<T>;
Array<720, 6> perm;
Array<20, 3> query;
Array<60, 4> special;
Array<3, 20, 720> query_rsp;
Array<60, 720> special_rsp;
void init(int) {
{
Array<6> ord;
std::iota(ord.begin(), ord.end(), 1);
for (int i = 0; i < 720; ++i) {
perm[i] = ord;
std::next_permutation(ord.begin(), ord.end());
}
}
int idx_q = 0, idx_s = 0;
for (int i = 0; i < 6; ++i) {
for (int j = i + 1; j < 6; ++j) {
for (int k = j + 1; k < 6; ++k) {
query[idx_q++] = {i, j, k};
for (int l = 0; l < 6; ++l) {
if (l != i and l != j and l != k) {
special[idx_s++] = {i, j, k, l};
}
}
}
}
}
for (int i = 0; i < 20; ++i) {
Array<3> ord = query[i];
for (int p = 0; p < 720; ++p) {
std::sort(ord.begin(), ord.end(), [&](const int x, const int y) {
return perm[p][x] < perm[p][y];
});
for (int k = 0; k < 3; ++k) {
query_rsp[k][i][p] = ord[k];
}
}
}
for (int i = 0; i < 60; ++i) {
Array<4> ord = special[i];
for (int p = 0; p < 720; ++p) {
std::sort(ord.begin(), ord.begin() + 3, [&](const int x, const int y) {
return perm[p][x] < perm[p][y];
});
int idx = 0;
while (idx < 3 and perm[p][ord[idx]] < perm[p][ord[3]]) {
idx += 1;
}
if (idx == 3) {
special_rsp[i][p] = ord[0];
} else {
special_rsp[i][p] = ord[idx];
}
}
}
}
void orderCoins() {
Vec<int> cand(720);
std::iota(cand.begin(), cand.end(), 0);
while (cand.size() > 1) {
int sk = -1, si = -1, max = -1;
for (int k = 0; k < 3; ++k) {
for (int i = 0; i < 20; ++i) {
std::map<int, int> cnt;
for (const int p : cand) {
cnt[query_rsp[k][i][p]] += 1;
}
int tmp = 0;
for (const auto& p : cnt) {
tmp = std::max(tmp, p.second);
}
if (max == -1 or tmp < max) {
sk = k;
si = i;
max = tmp;
}
}
}
for (int i = 0; i < 60; ++i) {
std::map<int, int> cnt;
for (const int p : cand) {
cnt[special_rsp[i][p]] += 1;
}
int tmp = 0;
for (const auto& p : cnt) {
tmp = std::max(tmp, p.second);
}
if (max == -1 or tmp < max) {
sk = 3;
si = i;
max = tmp;
}
}
if (sk == 0) {
const auto [a, b, c] = query[si];
const int d = getLightest(a + 1, b + 1, c + 1) - 1;
std::cerr << "l " << a << ' ' << b << ' ' << c << ' ' << d << '\n';
Vec<int> next;
for (const int p : cand) {
if (query_rsp[sk][si][p] == d) {
next.push_back(p);
}
}
cand = std::move(next);
} else if (sk == 1) {
const auto [a, b, c] = query[si];
const int d = getMedian(a + 1, b + 1, c + 1) - 1;
std::cerr << "m " << a << ' ' << b << ' ' << c << ' ' << d << '\n';
Vec<int> next;
for (const int p : cand) {
if (query_rsp[sk][si][p] == d) {
next.push_back(p);
}
}
cand = std::move(next);
} else if (sk == 2) {
const auto [a, b, c] = query[si];
const int d = getHeaviest(a + 1, b + 1, c + 1) - 1;
std::cerr << "h " << a << ' ' << b << ' ' << c << ' ' << d << '\n';
Vec<int> next;
for (const int p : cand) {
if (query_rsp[sk][si][p] == d) {
next.push_back(p);
}
}
cand = std::move(next);
} else {
const auto [a, b, c, d] = special[si];
const int e = getNextLightest(a + 1, b + 1, c + 1, d + 1) - 1;
std::cerr << "n " << a << ' ' << b << ' ' << c << ' ' << d << ' ' << e << '\n';
Vec<int> next;
for (const int p : cand) {
if (special_rsp[si][p] == e) {
next.push_back(p);
}
}
cand = std::move(next);
}
}
const int p = cand[0];
int W[6];
std::iota(W, W + 6, 0);
std::sort(W, W + 6, [&](const int x, const int y) {
return perm[p][x] < perm[p][y];
});
for (auto& x : W) {
x += 1;
}
answer(W);
}