| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 590934 | lorenzoferrari | 저울 (IOI15_scales) | C++17 | 105 ms | 336 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "scales.h"
#include <bits/stdc++.h>
using namespace std;
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;
}
int worst_case(const vector<perm>& cur, const op& o) {
auto s = simulate(cur, o);
return int(max(max(s[0].size(), s[1].size()), s[2].size()));
}
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 < 3; ++i) {
if (ans-1 == o[i]) {
cur = s[i];
break;
}
}
}
int T;
vector<perm> perms;
vector<op> ops;
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()));
for (int a = 0; a < 6; ++a) for (int b = a+1; b < 6; ++b) for (int c = b+1; c < 6; ++c) {
ops.push_back(op(0, {a,b,c}));
ops.push_back(op(1, {a,b,c}));
ops.push_back(op(2, {a,b,c}));
for (int d = 0; d < 6; ++d) {
if (d == a || d == b || d == c) continue;
ops.push_back(op(3, {a, b, c, d}));
}
}
}
void orderCoins() {
vector<perm> cur = perms;
while (cur.size() != 1) {
int best = 720;
op o(-1,{-1,-1,-1,-1});
for (const op& x : ops) {
if (worst_case(cur, x) <= best) {
best = worst_case(cur, x);
o = x;
}
}
actually_ask(cur, o);
}
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... | ||||