| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 590927 | lorenzoferrari | Scales (IOI15_scales) | C++17 | 91 ms | 340 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;
#define sz size
using perm = array<int8_t, 6>;
struct op {
int8_t type;
array<int8_t, 4> args;
op() : type(-1) {}
op(int8_t w, array<int, 4> a) : type(w) {
args[0] = a[0];
args[1] = a[1];
args[2] = a[2];
args[3] = a[3];
}
int8_t get_type() const { return type; }
int8_t operator[](const int i) const { return args[i]; }
};
struct query {
op o;
int8_t ans;
query() : ans(-1) {}
query(const op& o, const int8_t a) : o(o), ans(a) {}
int8_t type() const { return o.get_type(); }
int8_t operator[](const int i) const { return o[i]; }
};
bool works(const perm& p, const query& q) {
if (q.type() != 3) {
int cnt = 0;
for (int i = 0; i < 3; ++i) {
cnt += (p[q[i]] > p[q[q.ans]]);
}
return cnt == q.type();
} else {
int cnt = 0;
for (int i = 0; i < 3; ++i) cnt += (p[q[i]] > p[q[3]]);
int tans = -1;
if (cnt == 0) {
if (p[q[0]] < p[q[tans]] || tans == -1) tans = 0;
if (p[q[1]] < p[q[tans]] || tans == -1) tans = 1;
if (p[q[2]] < p[q[tans]] || tans == -1) tans = 2;
} else {
if (p[q[0]] > p[q[3]] && (tans == -1 || p[q[0]] < p[q[tans]])) tans = 0;
if (p[q[1]] > p[q[3]] && (tans == -1 || p[q[1]] < p[q[tans]])) tans = 1;
if (p[q[2]] > p[q[3]] && (tans == -1 || p[q[2]] < p[q[tans]])) tans = 2;
}
return q.ans == tans;
}
}
array<vector<perm>, 3> simulate(const vector<perm>& cur, const op& o) {
array<vector<perm>, 3> ans;
for (const perm& p : cur) {
for (int i = 0; i < 3; ++i) {
if (works(p, query(o, i))) ans[i].push_back(p);
}
}
return ans;
}
void answer(int w[]);
int getHeaviest(int A, int B, int C); // type 0
int getMedian(int A, int B, int C); // type 1
int getLightest(int A, int B, int C); // type 2
int getNextLightest(int A, int B, int C, int D); // type 3
void actually_ask(vector<perm>& cur, const op& o) {
auto s = simulate(cur, o);
int ans = -1;
switch (o.type) {
case 0:
ans = getHeaviest(o[0]+1, o[1]+1, o[2]+1);
break;
case 1:
ans = getMedian(o[0]+1, o[1]+1, o[2]+1);
break;
case 2:
ans = getLightest(o[0]+1, o[1]+1, o[2]+1);
break;
case 3:
ans = getNextLightest(o[0]+1, o[1]+1, o[2]+1, o[3]+1);
break;
}
for (int i = 0; i < 4; ++i) {
if (ans-1 == o[i]) {
cur = s[i];
break;
}
}
}
int T;
vector<perm> perms;
void init(int T) {
::T = T;
perms.reserve(720);
perm p{0,1,2,3,4,5};
do {
perms.push_back(p);
} while (next_permutation(p.begin(), p.end()));
}
void orderCoins() {
vector<perm> cur = perms;
while (cur.size() != 1) {
int best_worst_case = 1e9;
op best_op;
for (int a = 0; a < 6; ++a) for (int b = a+1; b < 6; ++b) for (int c = b+1; c < 6; ++c) {
op o0(0, {a, b, c});
op o1(1, {a, b, c});
op o2(2, {a, b, c});
auto s0 = simulate(cur, o0);
auto s1 = simulate(cur, o1);
auto s2 = simulate(cur, o2);
if (int(max({s0[0].sz(), s0[1].sz(), s0[2].sz()})) < best_worst_case) {
best_op = o0;
best_worst_case = int(max({s0[0].sz(), s0[1].sz(), s0[2].sz()}));
}
if (int(max({s1[0].sz(), s1[1].sz(), s1[2].sz()})) < best_worst_case) {
best_op = o1;
best_worst_case = int(max({s1[0].sz(), s1[1].sz(), s1[2].sz()}));
}
if (int(max({s2[0].sz(), s2[1].sz(), s2[2].sz()})) < best_worst_case) {
best_op = o2;
best_worst_case = int(max({s2[0].sz(), s2[1].sz(), s2[2].sz()}));
}
for (int d = 0; d < 6; ++d) {
if (d == a || d == b || d == c) continue;
op o3(3, {a, b, c, d});
auto s3 = simulate(cur, o3);
if (int(max({s3[0].sz(), s3[1].sz(), s3[2].sz()})) < best_worst_case) {
best_op = o3;
best_worst_case = int(max({s3[0].sz(), s3[1].sz(), s3[2].sz()}));
}
}
}
actually_ask(cur, best_op);
}
int w[6];
for (int i = 0; i < 6; ++i) {
w[cur[0][i]] = i+1;
}
answer(w);
}
Compilation message (stderr)
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| Fetching results... | ||||