#include<bits/stdc++.h>
#include "scales.h"
using namespace std;
const int INF = 1e9;
template<class T>void minimize(T& a, T b){
if(a > b){
a = b;
}
}
void init(int T){}
int W_ans[6];
void __answer(const vector<int>& ans){
for(int i = 0; i < 6; i++){
W_ans[i] = ans[i];
}
answer(W_ans);
}
bool update_min(pair<vector<vector<int>>, int>& best, pair<vector<vector<int>>, int>candidate){
if(best.first.size() > candidate.first.size() || (best.first.size() == candidate.first.size() && best.second > candidate.second)){
swap(best, candidate);
return true;
}
return false;
}
void update_max(vector<vector<int>>& best, vector<vector<int>>candidate){
if(best.size() < candidate.size()){
swap(best, candidate);
}
}
vector<vector<int>>candidate;
vector<vector<int>>get_min_query(vector<vector<int>>& perm, const vector<int>& index, const int r){
candidate.clear();
for(vector<int>& p : perm){
bool flag;
for(int& x : p){
if(x == index[0] || x == index[1] || x == index[2]){
flag = bool(x == index[r]);
break;
}
}
if(flag){
candidate.emplace_back(p);
}
}
return candidate;
}
vector<vector<int>>get_max_query(vector<vector<int>>& perm, const vector<int>& index, const int r){
candidate.clear();
for(vector<int>& p : perm){
bool flag;
for(int i = 5; i > -1; i--){
if(p[i] == index[0] || p[i] == index[1] || p[i] == index[2]){
flag = bool(p[i] == index[r]);
break;
}
}
if(flag){
candidate.emplace_back(p);
}
}
return candidate;
}
vector<vector<int>>get_median_query(vector<vector<int>>& perm, const vector<int>& index, const int r){
candidate.clear();
for(vector<int>& p : perm){
bool flag;
for(int& x : p){
if(x == index[0] || x == index[1] || x == index[2]){
flag = bool(x != index[r]);
break;
}
}
if(flag){
for(int i = 5; i > -1; i--){
if(p[i] == index[0] || p[i] == index[1] || p[i] == index[2]){
flag = bool(p[i] != index[r]);
break;
}
}
if(flag){
candidate.emplace_back(p);
}
}
}
return candidate;
}
vector<vector<int>>get_next_min_query(vector<vector<int>>& perm, const vector<int>& index, const int r){
candidate.clear();
for(vector<int>& p : perm){
vector<int>ord;
for(int& x : p){
if(x == index[0] || x == index[1] || x == index[2] || x == index[3]){
ord.emplace_back(x);
}
}
for(int i = 0; i < 4; i++){
if(index[3] == ord[i]){
if((i == 3 && index[r] == ord[0]) || (i < 3 && index[r] == ord[i + 1])){
candidate.emplace_back(p);
}
break;
}
}
}
return candidate;
}
void orderCoins(){
vector<int>_p(6);
iota(_p.begin(), _p.end(), 1);
vector<vector<int>>perm;
do{
perm.emplace_back(_p);
} while(next_permutation(_p.begin(), _p.end()));
while(perm.size() > 1){
pair<vector<vector<int>>, int>best = make_pair(perm, INF);
pair<vector<int>, int>query;
for(int i = 1; i < 7; i++){
for(int j = i + 1; j < 7; j++){
for(int k = j + 1; k < 7; k++){
vector<int>index = {i, j, k};
vector<vector<int>>_min, _max, _median;
int min_min = 0, min_max = 0, min_median = 0;
for(int r = 0; r < 3; r++){
update_max(_min, get_min_query(perm, index, r));
min_min += candidate.size();
update_max(_max, get_max_query(perm, index, r));
min_max += candidate.size();
update_max(_median, get_median_query(perm, index, r));
min_median += candidate.size();
}
for(int t = k + 1; t < 7; t++){
vector<int>index = {i, j, k, t};
for(int _i = 0; _i < 4; _i++){
swap(index[_i], index[3]);
vector<vector<int>>_next_min;
for(int r = 0; r < 3; r++){
update_max(_next_min, get_next_min_query(perm, index, r));
}
if(update_min(best, make_pair(_next_min, INF))){
query = make_pair(index, 3);
}
swap(index[_i], index[3]);
}
}
if(update_min(best, make_pair(_min, min_min))){
query = make_pair(index, 0);
}
if(update_min(best, make_pair(_max, min_max))){
query = make_pair(index, 1);
}
if(update_min(best, make_pair(_median, min_median))){
query = make_pair(index, 2);
}
}
}
}
if(query.second == 0){
int x = getLightest(query.first[0], query.first[1], query.first[2]);
perm = get_min_query(perm, query.first, x == query.first[0] ? 0 : (x == query.first[1] ? 1 : 2));
}
else if(query.second == 1){
int x = getHeaviest(query.first[0], query.first[1], query.first[2]);
perm = get_max_query(perm, query.first, x == query.first[0] ? 0 : (x == query.first[1] ? 1 : 2));
}
else if(query.second == 2){
int x = getMedian(query.first[0], query.first[1], query.first[2]);
perm = get_median_query(perm, query.first, x == query.first[0] ? 0 : (x == query.first[1] ? 1 : 2));
}
else{
int x = getNextLightest(query.first[0], query.first[1], query.first[2], query.first[3]);
perm = get_next_min_query(perm, query.first, x == query.first[0] ? 0 : (x == query.first[1] ? 1 : 2));
}
}
__answer(perm[0]);
}
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
