| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 787066 | GusterGoose27 | 저울 (IOI15_scales) | C++17 | 43 ms | 744 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "scales.h"
#include <bits/stdc++.h>
using namespace std;
vector<vector<int>> all_strats;
typedef pair<int, int> pii;
bool vis[6];
int pow3[10];
void make_strats(vector<int> &v) {
if (v.size() == 6) {
all_strats.push_back(v);
return;
}
for (int i = 0; i < 6; i++) {
if (vis[i]) continue;
vis[i] = 1;
v.push_back(i);
make_strats(v);
v.pop_back();
vis[i] = 0;
}
}
int light(int a, int b, int c, vector<int> &v) {
int s = a;
if (v[b] < v[s]) s = b;
if (v[c] < v[s]) s = c;
return s;
}
int heavy(int a, int b, int c, vector<int> &v) {
int s = a;
if (v[b] > v[s]) s = b;
if (v[c] > v[s]) s = c;
return s;
}
int med(int a, int b, int c, vector<int> &v) {
int l = light(a, b, c, v);
int h = heavy(a, b, c, v);
return a^b^c^l^h;
// if (l == b) {
// swap(a, b);
// }
// if (l == c) swap(a, c);
// if (v[b] < v[c]) return b;
// return c;
}
int next_light(int a, int b, int c, int d, vector<int> &v) {
vector<pii> elems;
elems.push_back(pii(v[a], a));
elems.push_back(pii(v[b], b));
elems.push_back(pii(v[c], c));
elems.push_back(pii(v[d], d));
sort(elems.begin(), elems.end());
int p;
for (int i = 0; i < 4; i++) {
if (elems[i].second == d) {
p = i;
break;
}
}
if (p == 3) return elems[0].second;
return elems[p+1].second;
}
class query {
public:
vector<int> nxt_states;
int tp;
vector<int> queried;
vector<int> perm;
query(vector<int> &nxt, int t = -1, int a = -1, int b = -1, int c = -1, int d = -1) {
if (c == -1) {
tp = -1;
perm = nxt;
return;
}
nxt_states = nxt;
tp = t;
queried.push_back(a+1);
queried.push_back(b+1);
queried.push_back(c+1);
if (t == 3) queried.push_back(d+1);
}
};
vector<query> query_res;
bool find_split(vector<int> &strats, int depth = 6) {
if (depth == 0) {
assert(strats.size() <= 1);
if (strats.size() == 1) query_res.push_back(all_strats[strats[0]]);
return 1;
}
for (int a = 0; a < 4; a++) {
for (int b = a+1; b < 5; b++) {
for (int c = b+1; c < 6; c++) {
for (int tp = 0; tp <= 3; tp++) {
for (int d = 0; d < ((tp < 3) ? 1 : 6); d++) {
if (tp == 3 && (d == a || d == b || d == c)) continue;
vector<int> g1;
vector<int> g2;
vector<int> g3;
for (int cur: strats) {
int res;
if (tp == 0) res = light(a, b, c, all_strats[cur]);
if (tp == 1) res = heavy(a, b, c, all_strats[cur]);
if (tp == 2) res = med(a, b, c, all_strats[cur]);
if (tp == 3) res = next_light(a, b, c, d, all_strats[cur]);
if (res == a) g1.push_back(cur);
if (res == b) g2.push_back(cur);
if (res == c) g3.push_back(cur);
}
if (g1.size() > pow3[depth-1] || g2.size() > pow3[depth-1] || g3.size() > pow3[depth-1]) continue;
bool g = 1;
vector<int> ids;
if (!g) continue;
else {
g = find_split(g1, depth-1);
ids.push_back(query_res.size()-1);
}
if (!g) continue;
else {
g = find_split(g2, depth-1);
ids.push_back(query_res.size()-1);
}
if (!g) continue;
else {
g = find_split(g3, depth-1);
ids.push_back(query_res.size()-1);
}
if (g) {
query_res.push_back(query(ids, tp, a, b, c, d));
return 1;
}
}
}
}
}
}
return 0;
}
void init(int t) {
pow3[0] = 1;
for (int i = 1; i < 10; i++) pow3[i] = 3*pow3[i-1];
vector<int> v;
make_strats(v);
vector<int> strats(all_strats.size());
iota(strats.begin(), strats.end(), 0);
find_split(strats);
}
void orderCoins() {
int cur = query_res.size()-1;
for (int i = 0; i < 6; i++) {
int res;
int a = query_res[cur].queried[0],
b = query_res[cur].queried[1],
c = query_res[cur].queried[2],
d = (query_res[cur].tp == 3 ? query_res[cur].queried[3] : 0);
if (query_res[cur].tp == 0) res = getLightest(a, b, c);
if (query_res[cur].tp == 1) res = getHeaviest(a, b, c);
if (query_res[cur].tp == 2) res = getMedian(a, b, c);
if (query_res[cur].tp == 3) res = getNextLightest(a, b, c, d);
if (res == a) cur = query_res[cur].nxt_states[0];
if (res == b) cur = query_res[cur].nxt_states[1];
if (res == c) cur = query_res[cur].nxt_states[2];
}
int ans[6];
for (int i = 0; i < 6; i++) ans[query_res[cur].perm[i]] = i+1;
answer(ans);
}
컴파일 시 표준 에러 (stderr) 메시지
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| Fetching results... | ||||