| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 830805 | drdilyor | 저울 (IOI15_scales) | C++17 | 24 ms | 756 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
#include "scales.h"
using namespace std;
using ll = long long;
#define sz(x) int((x).size())
ll pw3[30];
const int n = 6;
const int inf = 1e9;
using st = array<int, 6>;
using op = tuple<int,int,int,int,int>;
map<vector<st>, op> usedop;
array<vector<st>, 3> getNext(vector<st> cur, op op) {
auto [t, a, b, c, d] = op;
array<vector<st>, 3> next{{}};
if (t == 0) {
for (auto& i : cur) {
int mn = min({i[a], i[b], i[c]});
if (i[a] == mn)
next[0].push_back(i);
else if (i[b] == mn)
next[1].push_back(i);
else
next[2].push_back(i);
}
} else if (t == 1) {
for (auto& i : cur) {
int mx = max({i[a], i[b], i[c]});
if (i[a] == mx)
next[0].push_back(i);
else if (i[b] == mx)
next[1].push_back(i);
else
next[2].push_back(i);
}
} else if (t == 2) {
for (auto& i : cur) {
array cur{i[a], i[b], i[c]};
sort(cur.begin(), cur.end());
if (i[a] == cur[1])
next[0].push_back(i);
else if (i[b] == cur[1])
next[1].push_back(i);
else
next[2].push_back(i);
}
} else {
for (auto& i : cur) {
array cur{i[a], i[b], i[c]};
sort(cur.begin(), cur.end());
int ans = -1;
for (int j : cur) {
if (j > i[d]) {
ans = j;
break;
}
}
if (ans == -1) ans = cur[0];
if (i[a] == ans)
next[0].push_back(i);
else if (i[b] == ans)
next[1].push_back(i);
else
next[2].push_back(i);
}
}
return next;
}
int cost(array<vector<st>, 3> pos) {
return max({pos[0].size(), pos[1].size(), pos[2].size()});
}
int rec(vector<st> pos, int qleft) {
if (pw3[qleft] < sz(pos)) return false;
if (pos.size() <= 1) return true;
array<vector<st>, 3> best;
int bestx = inf;
op bestq;
auto tryAccept =[&](op op) {
auto next = getNext(pos, op);
int mx = max({next[0].size(), next[1].size(), next[2].size()});
if (mx < bestx) {
bestx = mx;
best = next;
bestq = op;
}
};
for (int a = 0; a < n; a++) {
for (int b = a+1; b < n; b++) {
for (int c = b+1; c < n; c++) {
tryAccept({0, a, b, c, -1});
tryAccept({1, a, b, c, -1});
tryAccept({2, a, b, c, -1});
for (int d = 0; d < n; d++) {
if (d == a || d == b || d == c) continue;
tryAccept({3, a, b, c, d});
}
}
}
}
assert(bestx != inf);
if (!rec(best[0], qleft-1)) return false;
if (!rec(best[1], qleft-1)) return false;
if (!rec(best[2], qleft-1)) return false;
usedop[pos] = bestq;
return true;
}
void init(int T) {
pw3[0] = 1;
for (int i = 1; i < 30; i++)
pw3[i] = pw3[i-1] * 3;
vector<st> pos;
st cur;
iota(cur.begin(), cur.end(), 0);
do {
pos.push_back(cur);
} while (next_permutation(cur.begin(), cur.end()));
cerr << rec(pos, 7) << endl;
// cout << rec(pos, 8) << endl;
}
void orderCoins() {
vector<st> pos;{
st cur;
iota(cur.begin(), cur.end(), 0);
do {
pos.push_back(cur);
} while (next_permutation(cur.begin(), cur.end()));}
while (pos.size() > 1) {
// cout << "pos.size()=" << pos.size() << endl;
assert(usedop.count(pos));
auto op = usedop[pos];
auto[t, a, b, c, d] = op;
auto next = getNext(pos, op);
a++;b++;c++; d++;
if (t == 0) {
int ans = getLightest(a, b, c);
if (ans == a) pos = next[0];
if (ans == b) pos = next[1];
if (ans == c) pos = next[2];
} else if (t == 1) {
int ans = getHeaviest(a, b, c);
if (ans == a) pos = next[0];
if (ans == b) pos = next[1];
if (ans == c) pos = next[2];
} else if (t == 2) {
int ans = getMedian(a, b, c);
if (ans == a) pos = next[0];
if (ans == b) pos = next[1];
if (ans == c) pos = next[2];
} else {
int ans = getNextLightest(a, b, c, d);
if (ans == a) pos = next[0];
if (ans == b) pos = next[1];
if (ans == c) pos = next[2];
}
}
assert(pos.size() == 1);
int w[6];
for (int i = 0; i < 6; i++) {
w[pos[0][i]] = i+1;
}
answer(w);
}
컴파일 시 표준 에러 (stderr) 메시지
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| Fetching results... | ||||