| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 551628 | hoanghq2004 | Scales (IOI15_scales) | C++14 | 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 <bits/stdc++.h>
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include "scales.h"
using namespace __gnu_pbds;
using namespace std;
template <typename T>
using ordered_set = tree <T, null_type, less <T>, rb_tree_tag, tree_order_statistics_node_update>;
mt19937 gen(std :: chrono :: system_clock :: now().time_since_epoch().count());
//
//int getHeaviest() {
//
//}
//int getLightest() {
//
//}
//int getMedian() {
//
//}
//int getNextLightest() {
//
//}
set <vector <int> > cands;
void init(int T) {
srand(time(nullptr));
vector <int> p;
for (int i = 0; i < 6; ++i) p.push_back(i);
do {
cands.insert(p);
} while (next_permutation(p.begin(), p.end()));
}
struct query {
int a, b, c, d, type;
};
vector <query> Q;
#define max(a, b, c) max({a, b, c})
#define min(a, b, c) min({a, b, c})
void orderCoins() {
while (1) {
if (cands.size() == 1) {
int W[6];
for (int i = 0; i < 6; ++i) W[i] = (*cands.begin())[i] + 1;
answer(W);
}
Q.clear();
int cur = 1e9;
for (int a = 0; a < 6; ++a)
for (int b = a + 1; b < 6; ++b)
for (int c = b + 1; c < 6; ++c) {
// type 0
int cnt_a = 0, cnt_b = 0, cnt_c = 0;
for (auto p: cands) {
if (max(p[a], p[b], p[c]) == p[a]) ++cnt_a;
if (max(p[a], p[b], p[c]) == p[b]) ++cnt_b;
if (max(p[a], p[b], p[c]) == p[c]) ++cnt_c;
}
if (max(cnt_a, cnt_b, cnt_c) < cur) {
cur = max(cnt_a, cnt_b, cnt_c);
Q = {{a, b, c, 0, 0}};
} else if (max(cnt_a, cnt_b, cnt_c) == cur) Q.push_back({a, b, c, 0, 0});
// type 1
int cnt_a = 0, cnt_b = 0, cnt_c = 0;
for (auto p: cands) {
if (min(p[a], p[b], p[c]) == p[a]) ++cnt_a;
if (min(p[a], p[b], p[c]) == p[b]) ++cnt_b;
if (min(p[a], p[b], p[c]) == p[c]) ++cnt_c;
}
if (max(cnt_a, cnt_b, cnt_c) < cur) {
cur = max(cnt_a, cnt_b, cnt_c);
Q = {{a, b, c, 0, 1}};
} else if (max(cnt_a, cnt_b, cnt_c) == cur) Q.push_back({a, b, c, 0, 1});
// type 2
int cnt_a = 0, cnt_b = 0, cnt_c = 0;
for (auto p: cands) {
if (min(p[a], p[b], p[c]) != p[a] && max(p[a], p[b], p[c]) != p[a]) ++cnt_a;
if (min(p[a], p[b], p[c]) != p[b] && max(p[a], p[b], p[c]) != p[b]) ++cnt_b;
if (min(p[a], p[b], p[c]) != p[c] && max(p[a], p[b], p[c]) != p[c]) ++cnt_c;
}
if (max(cnt_a, cnt_b, cnt_c) < cur) {
cur = max(cnt_a, cnt_b, cnt_c);
Q = {{a, b, c, 0, 2}};
} else if (max(cnt_a, cnt_b, cnt_c) == cur) Q.push_back({a, b, c, 0, 2});
// type 3
for (int d = 0; d < 6; ++d) {
if (d == a || d == b || d == c) continue;
for (auto p: cands) {
int x = -1;
if (p[a] > p[d] && (x == -1 || p[a] < p[x])) x = a;
if (p[b] > p[d] && (x == -1 || p[b] < p[x])) x = b;
if (p[c] > p[d] && (x == -1 || p[c] < p[x])) x = c;
if (x == -1) {
x = a;
if (p[b] < p[x]) x = b;
if (p[c] < p[x]) x = c;
}
if (x == a) ++cnt_a;
if (x == b) ++cnt_b;
if (x == c) ++cnt_c;
}
}
if (max(cnt_a, cnt_b, cnt_c) < cur) {
cur = max(cnt_a, cnt_b, cnt_c);
Q = {{a, b, c, d, 3}};
} else if (max(cnt_a, cnt_b, cnt_c) == cur) Q.push_back({a, b, c, d, 3});
}
query [a, b, c, d, type] = Q[rand() % Q.size()];
set <vector <int> > ncands;
if (type == 0) {
int x = getHeaviest(a, b, c);
for (auto p: cands)
if (max(p[a], p[b], p[c]) == p[x]) ncands.insert(p);
} else if (type == 1) {
int x = getLightest(a, b, c);
for (auto p: cands)
if (min(p[a], p[b], p[c]) == p[x]) ncands.insert(p);
} else if (type == 2) {
int x = getMedian(a, b, c);
for (auto p: cands)
if (max(p[a], p[b], p[c]) != p[x] && min(p[a], p[b], p[c]) != p[x]) ncands.insert(p);
} else {
int x = getNextLightest(a, b, c, d);
for (auto p: cands) {
int y = -1;
if (p[a] > p[d] && (y == -1 || p[a] < p[y])) y = a;
if (p[b] > p[d] && (y == -1 || p[b] < p[y])) y = b;
if (p[c] > p[d] && (y == -1 || p[c] < p[y])) y = c;
if (y == -1) {
y = a;
if (p[b] < p[y]) y = b;
if (p[c] < p[y]) y = c;
}
if (y == a) ++cnt_a;
if (y == b) ++cnt_b;
if (y == c) ++cnt_c;
if (x == y) ncands.insert(p);
}
}
swap(cands, ncands);
}
}
//int main() {
// ios :: sync_with_stdio(0); cin.tie(0);
//
//}