#include <bits/stdc++.h>
#include "scales.h"
using namespace std;
#define all(x) x.begin(), x.end()
#define pb push_back
#define ar array
#define nl '\n'
template <typename A, typename B>
bool chmin(A &a, const B &b) {
if(a > b) {
return a = b, true;
}
return false;
}
template <typename A, typename B>
bool chmax(A &a, const B &b) {
if(a < b) {
return a = b, true;
}
return false;
}
void init(int T) {
}
void orderCoins() {
set<vector<int>> perms;
vector<int> p(6);
iota(all(p), 1);
do {
perms.emplace(p);
} while(next_permutation(all(p)));
set<ar<int, 3>> for_min, for_med, for_max;
fill(all(p), 0);
p[3] = p[4] = p[5] = 1;
do {
vector<int> a;
for(int i = 0; i < 6; i++) {
if(p[i]) {
a.pb(i + 1);
}
}
for_min.insert({a[0], a[1], a[2]});
for_med.insert({a[0], a[1], a[2]});
for_max.insert({a[0], a[1], a[2]});
} while(next_permutation(all(p)));
set<ar<int, 4>> for_next_max;
p = vector<int>(5);
for(int x = 0; x < 6; x++) {
fill(all(p), 0);
p[2] = p[3] = p[4] = 1;
do {
vector<int> a;
for(int i = 0; i < 5; i++) {
if(p[i]) {
a.pb(i + 1 + (i >= x));
}
}
for_next_max.insert({a[0], a[1], a[2], x + 1});
} while(next_permutation(all(p)));
}
int cnta, cntb, cntc, inda, indb, indc, indd, mx, mn;
while(perms.size() > 1) {
ar<int, 6> best;
best[0] = -1e9;
for(auto &[A, B, C, D] : for_next_max) {
cnta = cntb = cntc = 0;
for(auto &perm : perms) {
for(int i = 0; i < 6; i++) {
if(perm[i] == A) inda = i;
if(perm[i] == B) indb = i;
if(perm[i] == C) indc = i;
if(perm[i] == D) indd = i;
}
vector<ar<int, 2>> a;
a.pb({inda, 0});
a.pb({indb, 1});
a.pb({indc, 2});
sort(all(a));
int i = upper_bound(all(a), ar<int, 2>{indd, -1}) - a.begin();
if(i == (int)a.size()) mn = a[0][1];
else mn = a[i][1];
if(mn != 0) cnta++;
if(mn != 1) cntb++;
if(mn != 2) cntc++;
}
mx = min({cnta, cntb, cntc});
if( chmax(best[0], mx) ) {
best[1] = 3;
best[2] = A;
best[3] = B;
best[4] = C;
best[5] = D;
}
}
for(auto &[A, B, C] : for_min) {
cnta = cntb = cntc = 0;
for(auto &perm : perms) {
for(int i = 0; i < 6; i++) {
if(perm[i] == A) inda = i;
if(perm[i] == B) indb = i;
if(perm[i] == C) indc = i;
}
if(inda > min(indb, indc)) cnta++;
if(indb > min(inda, indc)) cntb++;
if(indc > min(inda, indb)) cntc++;
}
mx = min({cnta, cntb, cntc});
if( chmax(best[0], mx) || best[0] == mx) {
best[1] = 0;
best[2] = A;
best[3] = B;
best[4] = C;
}
}
for(auto &[A, B, C] : for_max) {
cnta = cntb = cntc = 0;
for(auto &perm : perms) {
for(int i = 0; i < 6; i++) {
if(perm[i] == A) inda = i;
if(perm[i] == B) indb = i;
if(perm[i] == C) indc = i;
}
if(inda < max(indb, indc)) cnta++;
if(indb < max(inda, indc)) cntb++;
if(indc < max(inda, indb)) cntc++;
}
mx = min({cnta, cntb, cntc});
if( chmax(best[0], mx) ) {
best[1] = 2;
best[2] = A;
best[3] = B;
best[4] = C;
}
}
for(auto &[A, B, C] : for_med) {
cnta = cntb = cntc = 0;
for(auto &perm : perms) {
for(int i = 0; i < 6; i++) {
if(perm[i] == A) inda = i;
if(perm[i] == B) indb = i;
if(perm[i] == C) indc = i;
}
if( !( min(indb, indc) < inda && inda < max(indb, indc) ) ) cnta++;
if( !( min(inda, indc) < indb && indb < max(inda, indc) ) ) cntb++;
if( !( min(inda, indb) < indc && indc < max(inda, indb) ) ) cntc++;
}
mx = min({cnta, cntb, cntc});
if( chmax(best[0], mx) || best[0] == mx ) {
best[1] = 1;
best[2] = A;
best[3] = B;
best[4] = C;
}
}
// cout << "the best: ";
// for(int i = 0; i < 6; i++) cout << best[i] << ' ';
// cout << nl;
// cout << perms.size() << nl;
vector<vector<int>> for_del;
int A = best[2], B = best[3], C = best[4];
if( best[1] == 0 ) { // for_min
int ask = getLightest(A, B, C);
for(auto &perm : perms) {
for(int i = 0; i < 6; i++) {
if(perm[i] == A) inda = i;
if(perm[i] == B) indb = i;
if(perm[i] == C) indc = i;
}
if(inda > min(indb, indc) && ask == A) for_del.pb(perm);
if(indb > min(inda, indc) && ask == B) for_del.pb(perm);
if(indc > min(inda, indb) && ask == C) for_del.pb(perm);
}
// for_min.erase({A, B, C});
// for_med.erase({A, B, C});
// for_max.erase({A, B, C});
}
if( best[1] == 1 ) { // for_med
int ask = getMedian(A, B, C);
for(auto &perm : perms) {
for(int i = 0; i < 6; i++) {
if(perm[i] == A) inda = i;
if(perm[i] == B) indb = i;
if(perm[i] == C) indc = i;
}
if( !( min(indb, indc) < inda && inda < max(indb, indc) ) && ask == A ) for_del.pb(perm);
if( !( min(inda, indc) < indb && indb < max(inda, indc) ) && ask == B ) for_del.pb(perm);
if( !( min(inda, indb) < indc && indc < max(inda, indb) ) && ask == C ) for_del.pb(perm);
}
// for_min.erase({A, B, C});
// for_med.erase({A, B, C});
// for_max.erase({A, B, C});
}
if( best[1] == 2 ) { // for_max
int ask = getHeaviest(A, B, C);
for(auto &perm : perms) {
for(int i = 0; i < 6; i++) {
if(perm[i] == A) inda = i;
if(perm[i] == B) indb = i;
if(perm[i] == C) indc = i;
}
if(inda < max(indb, indc) && ask == A) for_del.pb(perm);
if(indb < max(inda, indc) && ask == B) for_del.pb(perm);
if(indc < max(inda, indb) && ask == C) for_del.pb(perm);
}
// for_min.erase({A, B, C});
// for_med.erase({A, B, C});
// for_max.erase({A, B, C});
}
if(best[1] == 3) { // for_next_max
int D = best[5], ask = getNextLightest(A, B, C, D);
for(auto &perm : perms) {
for(int i = 0; i < 6; i++) {
if(perm[i] == A) inda = i;
if(perm[i] == B) indb = i;
if(perm[i] == C) indc = i;
if(perm[i] == D) indd = i;
}
vector<ar<int, 2>> a;
a.pb({inda, 0});
a.pb({indb, 1});
a.pb({indc, 2});
sort(all(a));
int i = upper_bound(all(a), ar<int, 2>{indd, 0}) - a.begin();
if(i == (int)a.size()) mn = a[0][1];
else mn = a[i][1];
if(mn != 0 && ask == A) for_del.pb(perm);
if(mn != 1 && ask == B) for_del.pb(perm);
if(mn != 2 && ask == C) for_del.pb(perm);
}
// for_next_max.erase({A, B, C, D});
}
// cout << for_del.size() << nl;
for(auto &perm : for_del) perms.erase(perm);
}
assert(perms.size() == 1);
int C[6];
auto ans = *perms.begin();
for(int i = 0; i < 6; i++) C[i] = ans[i];
answer(C);
}
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
