| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1256232 | biank | Scales (IOI15_scales) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
using namespace std;
#define forn(i, n) for (int i = 0; i < int(n); i++)
#define forsn(i, s, n) for (int i = int(s); i < int(n); i++)
#define dforn(i, n) for (int i = int(n) - 1; i >= 0; i--)
#define dforsn(i, s, n) for (int i = int(n) - 1; i >= int(s); i--)
using vi = vector<int>;
using ll = long long;
using ii = pair<int, int>;
#define fst first
#define snd second
#define all(x) begin(x), end(x)
#define sz(x) int(x.size())
#define pb push_back
#define eb emplace_back
const int N = 6;
const int M = 720;
vi orders[M];
int simulate(int A, int B, int C, int D, int t, int orderIdx) {
const vi &order = orders[orderIdx];
vi v = {A, B, C};
sort(all(v), [&](const int &lhs, const int &rhs) {
return order[lhs] < order[rhs];
});
tie(A, B, C) = make_tuple(v[0], v[1], v[2]);
if (t == 0) return B;
if (t == 1) return A;
if (t == 2) return C;
assert(t == 3 && D != -1);
if (order[A] > order[D]) return A;
if (order[B] > order[D]) return B;
if (order[C] > order[D]) return C;
return A;
}
int doQuery(int A, int B, int C, int D, int t) {
A++, B++, C++, D++;
if (t == 0) return getMedian(A, B, C) - 1;
if (t == 1) return getLightest(A, B, C) - 1;
if (t == 2) return getHeaviest(A, B, C) - 1;
return getNextLightest(A, B, C, D) - 1;
}
int pot[N + 1];
map<pair<vi, int>, bool> memo;
vector<tuple<int, int, int, int, int>> all_moves;
vector<vi> division(int A, int B, int C, int D, int t, vi &possibilities) {
vector<vi> ret(3);
for (auto p : possibilities) {
int r = simulate(A, B, C, D, t, p);
int id = r == C ? 2 : r == B;
ret[id].pb(p);
}
return ret;
}
bool solve(vi &possibilities, int moves) {
pair<vi, int> state = {possibilities, moves};
if (memo.count(state)) return memo[state];
if (sz(possibilities) <= 1) {
return memo[state] = true;
}
if (sz(possibilities) > pot[6 - moves]) return false;
vector<pair<vector<vi>, int>> options;
int idx = 0;
for (auto [A, B, C, D, t] : all_moves) {
vector<vi> groups = division(A, B, C, D, t, possibilities);
if (sz(groups[0]) == sz(possibilities) ||
sz(groups[1]) == sz(possibilities) ||
sz(groups[2]) == sz(possibilities)) {
continue;
}
options.eb(groups, idx);
idx++;
}
sort(all(options), [&](const auto &A, const auto &B) {
auto &lhs = A.fst, &rhs = B.fst;
return max({sz(lhs[0]), sz(lhs[1]), sz(lhs[2])}) < max({sz(rhs[0]), sz(rhs[1]), sz(rhs[2])});
});
for (auto [groups, i] : options) {
if (solve(groups[0], moves + 1) &&
solve(groups[1], moves + 1) &&
solve(groups[2], moves + 1)) {
return memo[state] = true;
}
}
return memo[state] = false;
}
int first_move = 75;
int second_move = 18;
void init(int /*T*/) {
pot[0] = 1;
forn(i, N) pot[i + 1] = pot[i] * 3;
vi order(N);
iota(all(order), 0);
int i = 0;
do orders[i++] = order;
while (next_permutation(all(order)));
forn(A, N) forn(B, A) forn(C, B) forn(t, 3) all_moves.eb(A, B, C, -1, t);
forn(D, N) forn(A, N) forn(B, A) forn(C, B) {
if (A != D && B != D && C != D) {
all_moves.eb(A, B, C, D, 3);
}
}
vi possibilities(M);
iota(all(possibilities), 0);
auto [A, B, C, D, t] = all_moves[first_move];
vector<vi> groups = division(A, B, C, D, t, possibilities);
forn(i, 3) {
tie(A, B, C, D, t) = all_moves[second_move];
vector<vi> other_groups = division(A, B, C, D, t, groups[i]);
forn(j, 3) solve(other_groups[j], 2);
}
}
void doMove(vi &possibilities, int moves) {
int idx = 0;
for (auto [A, B, C, D, t] : all_moves) {
vector<vi> groups = division(A, B, C, D, t, possibilities);
if (sz(groups[0]) == sz(possibilities) ||
sz(groups[1]) == sz(possibilities) ||
sz(groups[2]) == sz(possibilities)) {
continue;
}
if (memo[{groups[0], moves + 1}] &&
memo[{groups[1], moves + 1}] &&
memo[{groups[2], moves + 1}]) {
int r = doQuery(A, B, C, D, t);
int id = r == C ? 2 : r == B;
possibilities = groups[id];
return;
}
idx++;
}
assert(false);
}
void orderCoins() {
vi possibilities(M);
iota(all(possibilities), 0);
for (auto i : {first_move, second_move}) {
auto [A, B, C, D, t] = all_moves[i];
vector<vi> groups = division(A, B, C, D, t, possibilities);
int r = doQuery(A, B, C, D, t);
int id = r == C ? 2 : r == B;
possibilities = groups[id];
}
int moves = 2;
while (sz(possibilities) > 1) {
pair<vi, int> state = {possibilities, moves};
assert(memo[state]);
doMove(possibilities, moves);
moves++;
}
assert(sz(possibilities) == 1);
assert(moves <= 6);
vi ans = orders[possibilities.back()];
int ret[N];
forn(i, N) ret[ans[i]] = i + 1;
answer(ret);
}