| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 590922 | lorenzoferrari | 저울 (IOI15_scales) | C++17 | 1098 ms | 340 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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]; }
};
ostream& operator<<(ostream& os, const op& o) {
os << "(" << int(o.type) << ", {" << int(o[0]) << "," << int(o[1]) << "," << int(o[2]);
if (o.type == 3) os << "," << int(o[3]);
os << "})";
return os;
}
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) {
// cerr << "asked: " << o << "\n";
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]) {
// cerr << ans << "\n";
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()));
}
struct record {
op operation;
int worst_case;
record() {}
record(const op o, const int wc) : operation(o), worst_case(wc) {}
};
record run_simulation(const vector<perm>& cur, int depth) {
record ans;
ans.worst_case = 1e9;
ans.operation = op(-1, {-1,-1,-1,-1});
if (depth == 0 || int(cur.size()) <= 1) {
ans.worst_case = cur.size();
} else {
for (int a = 0; a < 6; ++a) for (int b = a+1; b < 6; ++b) for (int c = b+1; c < 6; ++c) {
array<op, 3> operators;
operators[0] = op(0, {a, b, c});
operators[1] = op(1, {a, b, c});
operators[2] = op(2, {a, b, c});
for (int i = 0; i < 3; ++i) {
auto s = simulate(cur, operators[i]);
int cur_worst_case = 0;
for (int j = 0; j < 3; ++j) {
cur_worst_case = max(cur_worst_case, run_simulation(s[j], depth - 1).worst_case);
}
if (cur_worst_case < ans.worst_case) {
ans.worst_case = cur_worst_case;
ans.operation = operators[i];
}
}
for (int d = 0; d < 6; ++d) {
if (d == a || d == b || d == c) continue;
op o3(3, {a, b, c, d});
auto s = simulate(cur, o3);
int cur_worst_case = 0;
for (int j = 0; j < 3; ++j) {
cur_worst_case = max(cur_worst_case, run_simulation(s[j], depth - 1).worst_case);
}
if (cur_worst_case < ans.worst_case) {
ans.worst_case = cur_worst_case;
ans.operation = o3;
}
}
}
}
return ans;
}
void orderCoins() {
vector<perm> cur = perms;
actually_ask(cur, op(0, {0, 1, 2}));
actually_ask(cur, op(0, {3, 4, 5}));
while (cur.size() != 1) {
record r;
int steps = 0;
while ((r = run_simulation(cur, steps)).worst_case > 1 && steps < 2) {
r = run_simulation(cur, steps);
// cerr << " > r.op = " << r.operation << "\n";
// cerr << " > steps = " << steps << "\n";
if (r.worst_case > 1 )
++steps;
}
// cerr << "cur.size(): " << cur.size() << "\n";
// cerr << "worst_case: " << r.worst_case << "\n";
actually_ask(cur, r.operation);
}
int w[6];
for (int i = 0; i < 6; ++i) {
w[cur[0][i]] = i+1;
}
answer(w);
}
컴파일 시 표준 에러 (stderr) 메시지
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| Fetching results... | ||||