| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 391712 | usachevd0 | 저울 (IOI15_scales) | C++14 | 149 ms | 2440 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#ifndef DEBUG
#include "scales.h"
#endif
using namespace std;
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define all(a) (a).begin(), (a).end()
using ll = long long;
using ull = unsigned long long;
using pii = pair<int, int>;
using pil = pair<int, ll>;
using pli = pair<ll, int>;
using pll = pair<ll, ll>;
using ld = long double;
template<typename T1, typename T2> bool chkmin(T1& x, T2 y) {
return y < x ? (x = y, true) : false;
}
template<typename T1, typename T2> bool chkmax(T1& x, T2 y) {
return y > x ? (x = y, true) : false;
}
void debug_out() {
cerr << endl;
}
template<typename T1, typename... T2> void debug_out(T1 A, T2... B) {
cerr << ' ' << A;
debug_out(B...);
}
template<typename T> void mdebug_out(T* a, int n) {
for (int i = 0; i < n; ++i) {
cerr << a[i] << ' ';
}
cerr << endl;
}
#ifdef DEBUG
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#define mdebug(a, n) cerr << #a << ": ", mdebug_out(a, n)
#else
#define debug(...) 1337
#define mdebug(a, n) 1337
#endif
template<typename T> ostream& operator << (ostream& stream, const vector<T>& v) {
for (auto& x : v) {
stream << x << ' ';
}
return stream;
}
template<typename T1, typename T2> ostream& operator << (ostream& stream, const pair<T1, T2>& p) {
return stream << p.first << ' ' << p.second;
}
#ifdef DEBUG
vector<int> pp;
vector<int> ip;
int getHeaviest(int x, int y, int z) {
vector<int> ord = {x, y, z};
sort(all(ord), [&](int x, int y) -> bool {
return ip[x] < ip[y];
});
return ord[2];
}
int getLightest(int x, int y, int z) {
vector<int> ord = {x, y, z};
sort(all(ord), [&](int x, int y) -> bool {
return ip[x] < ip[y];
});
return ord[0];
}
int getMedian(int x, int y, int z) {
vector<int> ord = {x, y, z};
sort(all(ord), [&](int x, int y) -> bool {
return ip[x] < ip[y];
});
return ord[1];
}
int getNextLightest(int x, int y, int z, int w) {
vector<int> ord = {x, y, z};
sort(all(ord), [&](int x, int y) -> bool {
return ip[x] < ip[y];
});
int i = 0;
while (i < 3 && ip[ord[i]] < ip[w]) ++i;
return ord[i % 3];
}
void answer(int* p) {
for (int i = 0; i < 6; ++i) {
assert(pp[i] == p[i]);
}
}
#endif
int pw3[10];
const int P = 720;
const int Q = 120;
vector<int> perm[P];
map<vector<int>, int> pid;
using Mask = array<bool, P>;
Mask fullMask;
struct Query {
int type;
vector<int> args;
Query() {}
Query(int _type, int a, int b, int c) {
type = _type;
args = {a, b, c};
}
Query(int _type, int a, int b, int c, int d) {
type = _type;
args = {a, b, c, d};
}
} query[Q];
int ans[P][Q];
void prec() {
vector<int> p(6);
iota(all(p), 0);
int ptr = 0;
do {
perm[ptr++] = vector<int>(all(p));
} while (next_permutation(all(p)));
assert(ptr == P);
ptr = 0;
for (int a = 0; a < 6; ++a) {
for (int b = a + 1; b < 6; ++b) {
for (int c = b + 1; c < 6; ++c) {
for (int type = 0; type <= 2; ++type) {
query[ptr++] = Query(type, a, b, c);
}
for (int d = 0; d < 6; ++d) {
if (d != a && d != b && d != c) {
query[ptr++] = Query(3, a, b, c, d);
}
}
}
}
}
assert(ptr == Q);
for (int pi = 0; pi < P; ++pi) {
auto& p = perm[pi];
vector<int> where(6);
for (int i = 0; i < 6; ++i) {
where[p[i]] = i;
}
for (int qi = 0; qi < Q; ++qi) {
auto& q = query[qi];
vector<pii> ord;
for (int i = 0; i < 3; ++i) {
ord.emplace_back(q.args[i], i);
}
sort(all(ord), [&](pii x, pii y) -> bool {
return where[x.fi] < where[y.fi];
});
switch (q.type) {
case 0:
ans[pi][qi] = ord[2].se;
break;
case 1:
ans[pi][qi] = ord[0].se;
break;
case 2:
ans[pi][qi] = ord[1].se;
break;
case 3:
int d = q.args[3];
int i = 0;
while (i < 3 && where[ord[i].fi] < where[d]) ++i;
ans[pi][qi] = ord[i % 3].se;
break;
}
}
}
pw3[0] = 1;
for (int i = 1; i < 10; ++i) pw3[i] = pw3[i - 1] * 3;
fill(all(fullMask), 1);
}
int Count(const Mask& mask) {
return count(all(mask), 1);
}
map<pair<Mask, int>, bool> mem;
map<pair<Mask, int>, int> whatq;
bool brute(Mask mask, int rem = 6) {
pair<Mask, int> key = {mask, rem};
int cnt = Count(mask);
if (cnt <= 1) {
return mem[key] = true;
}
if (mem.count(key)) {
return mem[key];
}
if (cnt > pw3[rem]) {
return mem[key] = false;
}
for (int qi = 0; qi < Q; ++qi) {
Mask nxt[3];
for (int i = 0; i < 3; ++i) {
fill(all(nxt[i]), 0);
}
for (int pi = 0; pi < P; ++pi) {
if (mask[pi]) {
nxt[ans[pi][qi]][pi] = 1;
}
}
if (max(Count(nxt[0]), max(Count(nxt[1]), Count(nxt[2]))) <= pw3[rem - 1] && brute(nxt[0], rem - 1) && brute(nxt[1], rem - 1) && brute(nxt[2], rem - 1)) {
whatq[key] = qi;
return mem[key] = true;
}
}
return mem[key] = false;
}
void init(int T) {
prec();
brute(fullMask, 6);
}
int ask(int qi) {
auto& q = query[qi];
switch (q.type) {
case 0:
return find(all(q.args), getHeaviest(q.args[0] + 1, q.args[1] + 1, q.args[2] + 1) - 1) - q.args.begin();
break;
case 1:
return find(all(q.args), getLightest(q.args[0] + 1, q.args[1] + 1, q.args[2] + 1) - 1) - q.args.begin();
break;
case 2:
return find(all(q.args), getMedian(q.args[0] + 1, q.args[1] + 1, q.args[2] + 1) - 1) - q.args.begin();
break;
case 3:
return find(all(q.args), getNextLightest(q.args[0] + 1, q.args[1] + 1, q.args[2] + 1, q.args[3] + 1) - 1) - q.args.begin();
break;
}
}
void orderCoins() {
Mask mask = fullMask;
for (int rem = 6; rem > 0; --rem) {
int qi = whatq[{mask, rem}];
int r = ask(qi);
for (int pi = 0; pi < P; ++pi) {
mask[pi] &= ans[pi][qi] == r;
}
}
int pi = 0;
while (pi < P && !mask[pi]) ++pi;
int p[6];
for (int i = 0; i < 6; ++i) {
p[i] = perm[pi][i] + 1;
}
answer(p);
}
#ifdef DEBUG
int32_t main() {
#ifdef DEBUG
freopen("in", "r", stdin);
#endif
ios::sync_with_stdio(0);
cin.tie(0);
pp.resize(6);
ip.resize(6);
iota(all(pp), 0);
init(-1);
do {
//debug(pp);
for (int i = 0; i < 6; ++i) ip[pp[i]] = i;
orderCoins();
} while (next_permutation(all(pp)));
return 0;
}
#endif
컴파일 시 표준 에러 (stderr) 메시지
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| Fetching results... | ||||