| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 729093 | kirakaminski968 | Scales (IOI15_scales) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "scales.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5;
vector<vector<int>> allPerm;
vector<pair<int, vector<int>>> OP;
int ask[MAXN];
int nxt[MAXN][4];
int done[MAXN];
int timer = 0;
bool init(int cur, int sz, vector<int> index) {
if (index.size() <= 1) {
if (index.size() == 1) {
done[cur] = 1;
ask[cur] = index[0];
}
return 1;
}
for (int z = 0; z < OP.size(); z++) {
int op = OP[z].first;
vector<int> ques = OP[z].second;
bool ok = 1;
vector<int> ans[3];
for (int id : index) {
int a[3], b[6];
for (int i = 0; i < 3; i++) a[i] = allPerm[id][ques[i]];
sort(a, a + 3);
for (int i = 0; i < 3; i++) b[allPerm[id][ques[i]]] = i;
if (op == 0) { // min
ans[b[a[0]]].emplace_back(id);
} else if (op == 1) { // med
ans[b[a[1]]].emplace_back(id);
} else if (op == 2) { // max
ans[b[a[2]]].emplace_back(id);
} else { // spec
if (allPerm[id][ques[3]] < a[0]) {
ans[b[a[0]]].emplace_back(id);
} else if (allPerm[id][ques[3]] < a[1]) {
ans[b[a[1]]].emplace_back(id);
} else if (allPerm[id][ques[3]] < a[2]) {
ans[b[a[2]]].emplace_back(id);
} else {
ans[b[a[0]]].emplace_back(id);
}
}
}
if (ans[0].size() > sz / 3) continue;
if (ans[1].size() > sz / 3) continue;
if (ans[2].size() > sz / 3) continue;
for (int i = 0; i < 3; i++) {
nxt[cur][i] = timer++;
ok &= init(nxt[cur][i], sz / 3, ans[i]);
}
if (ok) return ask[cur] = z, 1;
}
return 0;
}
void init(int T) {
vector<int> a(6);
iota(a.begin(), a.end(), 0);
do {
allPerm.emplace_back(a);
} while (next_permutation(a.begin(), a.end()));
vector<int> index(720);
iota(index.begin(), index.end(), 0);
for (int i = 0; i < 1 << 6;++i) {
if (__builtin_popcount(i) == 3) {
vector<int> ques;
for (int j = 0;j < 6;++j){
if (i >> j & 1) ques.emplace_back(j);
}
for (int j = 0; j < 3; j++) OP.emplace_back(j, ques);
for (int j = 0; j < 6; j++) {
if (i >> j & 1 ^ 1) {
ques.emplace_back(j);
OP.emplace_back(3, ques);
ques.pop_back();
}
}
}
}
assert(init(timer++, 729, index));
}
int F(int cur) {
if (done[cur]) return ask[cur];
int op = OP[ask[cur]].first;
vector<int> ques = OP[ask[cur]].second; int answer = -1;
if(op == 0) { ans = getLightest(ques[0] + 1, ques[1] + 1, ques[2] + 1);}
else if (op == 1) {ans = getMedian(ques[0] + 1, ques[1] + 1, ques[2] + 1);}
else if (op == 2) {ans = getHeaviest(ques[0] + 1, ques[1] + 1, ques[2] + 1);}
else{answer = getNextLightest(ques[0] + 1, ques[1] + 1, ques[2] + 1, ques[3] + 1);}
for(int i = 0;i<3;++i){
if(answer == ques[i] + 1) return F(nxt[cur][i]);
}
return assert(0),-1;
}
void orderCoins() {
int id = F(0), W[6];
for (int i = 0;i < 6;++i) W[allPerm[id][i]] = i + 1;
answer(W);
}