#include "scales.h"
#include <iostream>
#include <vector>
#include <random>
#include <chrono>
#include <algorithm>
#include <iomanip>
#include <set>
#include <map>
#include <deque>
#include <queue>
#define ff first
#define ss second
typedef long long ll;
typedef long double ld;
using namespace std;
const int N = 1e5 + 10;
void init(int T) {
return;
}
vector <int> ans(6);
int cur_count_of_queries = 0;
int cur_sum_of_queries = 0;
vector <int> cur_vec(6);
/*
inline void answer(int* esim) {
cur_sum_of_queries += cur_count_of_queries;
//cout << "? " << cur_count_of_queries << "\n";
cur_count_of_queries = 0;
}
inline int getLightest(int A, int B, int C) {
cur_count_of_queries++;
for (auto it : cur_vec) {
if (it == A || it == B || it == C) return it;
}
return A;
}
inline int getHeaviest(int A, int B, int C) {
cur_count_of_queries++;
int w = 0;
for (auto it : cur_vec) {
if (it == A || it == B || it == C) w++;
if (w == 3) return it;
}
return A;
}
inline int getMedian(int A, int B, int C) {
cur_count_of_queries++;
int w = 0;
for (auto it : cur_vec) {
if (it == A || it == B || it == C) w++;
if (w == 2) return it;
}
return A;
}
inline int getNextLightest(int A, int B, int C, int D) {
cur_count_of_queries++;
bool ch = false;
for (auto it : cur_vec) {
if (it == D) ch = true;
if (!ch) continue;
if (it == A || it == B || it == C) return it;
}
for (auto it : cur_vec) {
if (it == A || it == B || it == C) return it;
}
return A;
}
*/
int W;
vector <vector<int>> current_states;
void rec() {
vector <int> v(6);
for (int i = 0; i < 6; i++) {
v[i] = i + 1;
}
while (1) {
current_states.push_back(v);
if (!next_permutation(v.begin(), v.end())) break;
}
while (1) {
W /= 3;
if ((int)current_states.size() == 1) {
ans = current_states[0];
return;
}
vector <vector<int>> best_case = current_states;
string type = "unknown";
int A, B, C, D;
//Median
for (int a = 1; a <= 6; a++) {
for (int b = 1; b <= 6; b++) {
for (int c = 1; c <= 6; c++) {
if (a == b || a == c || b == c) continue;
vector <vector<int>> f, s, t;
for (auto& it : current_states) {
int indA, indB, indC;
for (int j = 0; j < 6; j++) {
if (it[j] == a) indA = j;
if (it[j] == b) indB = j;
if (it[j] == c) indC = j;
}
if (indA > min(indB, indC) && indA < max(indC, indB)) {
f.push_back(it);
}
else if (indB > min(indA, indC) && indB < max(indA, indC)) {
s.push_back(it);
}
else t.push_back(it);
}
if ((int)f.size() < (int)s.size()) swap(f, s);
if ((int)f.size() < (int)t.size()) swap(f, t);
if ((int)f.size() <= W || (int)f.size() < (int)best_case.size()) {
best_case = f;
type = "Median";
A = a;
B = b;
C = c;
}
}
}
}
//Lightest
for (int a = 1; a <= 6; a++) {
for (int b = 1; b <= 6; b++) {
for (int c = 1; c <= 6; c++) {
if (a == b || a == c || b == c) continue;
vector <vector<int>> f, s, t;
for (auto& it : current_states) {
int indA, indB, indC;
for (int j = 0; j < 6; j++) {
if (it[j] == a) indA = j;
if (it[j] == b) indB = j;
if (it[j] == c) indC = j;
}
if (indA < indB && indA < indC) {
f.push_back(it);
}
else if (indB < indA && indB < indC) {
s.push_back(it);
}
else t.push_back(it);
}
if ((int)f.size() < (int)s.size()) swap(f, s);
if ((int)f.size() < (int)t.size()) swap(f, t);
if ((int)f.size() <= W || (int)f.size() < (int)best_case.size()) {
best_case = f;
type = "Light";
A = a;
B = b;
C = c;
}
}
}
}
//Heaviest
for (int a = 1; a <= 6; a++) {
for (int b = 1; b <= 6; b++) {
for (int c = 1; c <= 6; c++) {
if (a == b || a == c || b == c) continue;
vector <vector<int>> f, s, t;
for (auto& it : current_states) {
int indA, indB, indC;
for (int j = 0; j < 6; j++) {
if (it[j] == a) indA = j;
if (it[j] == b) indB = j;
if (it[j] == c) indC = j;
}
if (indA > indB && indA > indC) {
f.push_back(it);
}
else if (indB > indA && indB > indC) {
s.push_back(it);
}
else t.push_back(it);
}
if ((int)f.size() < (int)s.size()) swap(f, s);
if ((int)f.size() < (int)t.size()) swap(f, t);
if ((int)f.size() <= W || (int)f.size() < (int)best_case.size()) {
best_case = f;
type = "Heavy";
A = a;
B = b;
C = c;
}
}
}
}
//nextLightest
for (int a = 1; a <= 6; a++) {
for (int b = 1; b <= 6; b++) {
for (int c = 1; c <= 6; c++) {
for (int d = 1; d <= 6; d++) {
if (a == b || a == c || b == c) continue;
if (a == d || b == d || c == d) continue;
vector <vector<int>> f, s, t;
for (auto& it : current_states) {
int indA, indB, indC, indD;
for (int j = 0; j < 6; j++) {
if (it[j] == a) indA = j;
if (it[j] == b) indB = j;
if (it[j] == c) indC = j;
if (it[j] == d) indD = j;
}
int mn = 1000;
if (indA > indD) mn = min(mn, indA);
if (indB > indD) mn = min(mn, indB);
if (indC > indD) mn = min(mn, indC);
if (mn == 1000) {
if (indA < indB && indA < indC) {
f.push_back(it);
}
else if (indB < indA && indB < indC) {
s.push_back(it);
}
else {
t.push_back(it);
}
}
else if (mn == indA) {
f.push_back(it);
}
else if (mn == indB) {
s.push_back(it);
}
else t.push_back(it);
}
if ((int)f.size() < (int)s.size()) swap(f, s);
if ((int)f.size() < (int)t.size()) swap(f, t);
if ((int)f.size() <= W || (int)f.size() < (int)best_case.size()) {
best_case = f;
type = "nextLightest";
A = a;
B = b;
C = c;
D = d;
}
}
}
}
}
vector <vector<int>> nxt_case;
if (type == "Light") {
int u = getLightest(A, B, C);
vector <vector<int>> f, s, t;
for (auto& it : current_states) {
int indA, indB, indC;
for (int j = 0; j < 6; j++) {
if (it[j] == A) indA = j;
if (it[j] == B) indB = j;
if (it[j] == C) indC = j;
}
if (indA < indB && indA < indC) {
f.push_back(it);
}
else if (indB < indA && indB < indC) {
s.push_back(it);
}
else t.push_back(it);
}
if (u == A) nxt_case = f;
else if (u == B) nxt_case = s;
else nxt_case = t;
}
else if (type == "Heavy") {
int u = getHeaviest(A, B, C);
vector <vector<int>> f, s, t;
for (auto& it : current_states) {
int indA, indB, indC;
for (int j = 0; j < 6; j++) {
if (it[j] == A) indA = j;
if (it[j] == B) indB = j;
if (it[j] == C) indC = j;
}
if (indA > indB && indA > indC) {
f.push_back(it);
}
else if (indB > indA && indB > indC) {
s.push_back(it);
}
else t.push_back(it);
}
if (u == A) nxt_case = f;
else if (u == B) nxt_case = s;
else nxt_case = t;
}
else if (type == "Median") {
int u = getMedian(A, B, C);
vector <vector<int>> f, s, t;
for (auto& it : current_states) {
int indA, indB, indC;
for (int j = 0; j < 6; j++) {
if (it[j] == A) indA = j;
if (it[j] == B) indB = j;
if (it[j] == C) indC = j;
}
if (indA > min(indB, indC) && indA < max(indC, indB)) {
f.push_back(it);
}
else if (indB > min(indA, indC) && indB < max(indA, indC)) {
s.push_back(it);
}
else t.push_back(it);
}
if (u == A) nxt_case = f;
else if (u == B) nxt_case = s;
else nxt_case = t;
}
else {
int u = getNextLightest(A, B, C, D);
vector <vector<int>> f, s, t;
for (auto& it : current_states) {
int indA, indB, indC, indD;
for (int j = 0; j < 6; j++) {
if (it[j] == A) indA = j;
if (it[j] == B) indB = j;
if (it[j] == C) indC = j;
if (it[j] == D) indD = j;
}
int mn = 1000;
if (indA > indD) mn = min(mn, indA);
if (indB > indD) mn = min(mn, indB);
if (indC > indD) mn = min(mn, indC);
if (mn == 1000) {
if (indA < indB && indA < indC) {
f.push_back(it);
}
else if (indB < indA && indB < indC) {
s.push_back(it);
}
else {
t.push_back(it);
}
}
else if (mn == indA) {
f.push_back(it);
}
else if (mn == indB) {
s.push_back(it);
}
else t.push_back(it);
}
if (u == A) nxt_case = f;
else if (u == B) nxt_case = s;
else nxt_case = t;
}
current_states = nxt_case;
}
}
void orderCoins() {
W = 729;
vector <int> v(6);
for (int i = 0; i < 6; i++) {
v[i] = i + 1;
}
rec();
int* answ = new int[6];
for (int i = 0; i < 6; i++) {
answ[i] = ans[i];
}
answer(answ);
}
/*
int main() {
for (int i = 0; i < 6; i++) {
cur_vec[i] = i + 1;
}
orderCoins();
int ind = 0;
int limit = 0;
int range = 40;
while (next_permutation(cur_vec.begin(), cur_vec.end())) {
int prev_val = cur_sum_of_queries;
ind++;
if (ind >= limit && ind <= limit + range) {
orderCoins();
if ((cur_sum_of_queries - prev_val) > 7) {
cout << "! ";
for (auto it : cur_vec) {
cout << it << " ";
}
return 0;
}
}
}
cout << cur_sum_of_queries << "\n";
}
*/
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
