| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 237987 | rama_pang | Scales (IOI15_scales) | C++14 | 727 ms | 508 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 "scales.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 720;
using state = bitset<N>;
vector<vector<int>> combinations; // take 4 coins' ids
vector<vector<int>> permutations; // weights of each coin
function<int(int, int, int, int, int)> Lightest = [&](int P, int A, int B, int C, int D) {
if (P == -1) {
return getLightest(A + 1, B + 1, C + 1) - 1;
} else {
const vector<int> &cur = permutations[P];
vector<array<int, 2>> weights = {{cur[A], A}, {cur[B], B}, {cur[C], C}};
sort(begin(weights), end(weights));
return weights[0][1];
}
};
function<int(int, int, int, int, int)> Median = [&](int P, int A, int B, int C, int D) {
if (P == -1) {
return getMedian(A + 1, B + 1, C + 1) - 1;
} else {
const vector<int> &cur = permutations[P];
vector<array<int, 2>> weights = {{cur[A], A}, {cur[B], B}, {cur[C], C}};
sort(begin(weights), end(weights));
return weights[1][1];
}
};
function<int(int, int, int, int, int)> Heaviest = [&](int P, int A, int B, int C, int D) {
if (P == -1) {
return getHeaviest(A + 1, B + 1, C + 1) - 1;
} else {
const vector<int> &cur = permutations[P];
vector<array<int, 2>> weights = {{cur[A], A}, {cur[B], B}, {cur[C], C}};
sort(begin(weights), end(weights));
return weights[2][1];
}
};
function<int(int, int, int, int, int)> NextLightest = [&](int P, int A, int B, int C, int D) {
if (P == -1) {
return getNextLightest(A + 1, B + 1, C + 1, D + 1) - 1;
} else {
const vector<int> &cur = permutations[P];
vector<array<int, 2>> weights = {{cur[A], A}, {cur[B], B}, {cur[C], C}};
sort(begin(weights), end(weights));
if (cur[D] < weights[0][0]) return weights[0][1];
if (cur[D] < weights[1][0]) return weights[1][1];
if (cur[D] < weights[2][0]) return weights[2][1];
return weights[0][1];
}
};
void init(int T) {
for (int mask = 0; mask < (1 << 6); mask++) {
if (__builtin_popcount(mask) == 4) {
vector<int> active;
for (int i = 0; i < 6; i++) {
if (mask & (1 << i)) {
active.emplace_back(i);
}
}
do {
combinations.emplace_back(active);
} while (next_permutation(begin(active), end(active)));
}
}
vector<int> p = {0, 1, 2, 3, 4, 5};
do {
permutations.emplace_back(p);
} while (next_permutation(begin(p), end(p)));
}
bool Solve(const state &candidates, int depth);
bool Try(const state &perms, const function<int(int, int, int, int, int)> &f, int depth) {
for (auto &comb : combinations) {
int mx = 0;
for (int ans = 0; ans < 4; ans++) {
int can = 0;
for (int p = 0; p < N; p++) if (perms[p]) {
if (f(p, comb[0], comb[1], comb[2], comb[3]) == comb[ans]) {
can++;
}
}
mx = max(mx, can);
}
int cnt = perms.count();
bool transition = false;
if (243 < cnt && cnt <= 720) transition |= mx <= 240;
if (81 < cnt && cnt <= 243) transition |= mx <= 81;
if (27 < cnt && cnt <= 81) transition |= mx <= 27;
if (9 < cnt && cnt <= 27) transition |= mx <= 9;
if (3 < cnt && cnt <= 9) transition |= mx <= 3;
if (0 < cnt && cnt <= 3) transition |= mx <= 1;
if (transition) {
int ans = f(-1, comb[0], comb[1], comb[2], comb[3]);
state can = 0;
for (int p = 0; p < N; p++) if (perms[p]) {
if (f(p, comb[0], comb[1], comb[2], comb[3]) == ans) {
can[p] = 1;
}
}
return Solve(can, depth + 1);
}
}
return false;
}
bool Solve(const state &candidates, int depth = 0) {
if (candidates.count() == 1) {
int pid = candidates._Find_first();
vector<int> order(6);
for (int i = 0; i < 6; i++) {
order[permutations[pid][i]] = i + 1;
}
answer(order.data());
return true;
} else if (depth % 4 == 0) {
return Try(candidates, Lightest, depth) || Try(candidates, Median, depth) ||
Try(candidates, Heaviest, depth) || Try(candidates, NextLightest, depth);
} else if (depth % 4 == 1) {
return Try(candidates, Median, depth) || Try(candidates, Heaviest, depth) ||
Try(candidates, NextLightest, depth) || Try(candidates, Lightest, depth);
} else if (depth % 4 == 2) {
return Try(candidates, Heaviest, depth) || Try(candidates, NextLightest, depth) ||
Try(candidates, Lightest, depth) || Try(candidates, Median, depth);
} else if (depth % 4 == 3) {
return Try(candidates, NextLightest, depth) || Try(candidates, Lightest, depth) ||
Try(candidates, Median, depth) || Try(candidates, Heaviest, depth);
}
}
void orderCoins() {
state candidates;
for (int i = 0; i < N; i++) candidates[i] = 1;
assert(Solve(candidates));
}
Compilation message (stderr)
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| Fetching results... | ||||