/*
________ ___ ________ ________ ________ ___ ________ ________ ________
|\ ____\|\ \|\ ____\|\ __ \ |\ ___ \|\ \|\ ____\|\ ____\|\ __ \
\ \ \___|\ \ \ \ \___|\ \ \|\ \ \ \ \\ \ \ \ \ \ \___|\ \ \___|\ \ \|\ \
\ \ \ __\ \ \ \ \ __\ \ __ \ \ \ \\ \ \ \ \ \ \ __\ \ \ __\ \ __ \
\ \ \|\ \ \ \ \ \|\ \ \ \ \ \ \ \ \\ \ \ \ \ \ \|\ \ \ \|\ \ \ \ \ \
\ \_______\ \__\ \_______\ \__\ \__\ \ \__\\ \__\ \__\ \_______\ \_______\ \__\ \__\
\|_______|\|__|\|_______|\|__|\|__| \|__| \|__|\|__|\|_______|\|_______|\|__|\|__|
________ ________ ________ ________ ___ ___ ________ _________ ___ ________ ________
|\ __ \|\ __ \|\ __ \|\ ___ \|\ \|\ \|\ ____\\___ ___\\ \|\ __ \|\ ___ \
\ \ \|\ \ \ \|\ \ \ \|\ \ \ \_|\ \ \ \\\ \ \ \___\|___ \ \_\ \ \ \ \|\ \ \ \\ \ \
\ \ ____\ \ _ _\ \ \\\ \ \ \ \\ \ \ \\\ \ \ \ \ \ \ \ \ \ \ \\\ \ \ \\ \ \
\ \ \___|\ \ \\ \\ \ \\\ \ \ \_\\ \ \ \\\ \ \ \____ \ \ \ \ \ \ \ \\\ \ \ \\ \ \
\ \__\ \ \__\\ _\\ \_______\ \_______\ \_______\ \_______\ \ \__\ \ \__\ \_______\ \__\\ \__\
\|__| \|__|\|__|\|_______|\|_______|\|_______|\|_______| \|__| \|__|\|_______|\|__| \|__|
Written by: giga nigga
*/
// #include "largest.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define MASK(i) (1ULL << (i))
#define GETBIT(mask, i) (((mask) >> (i)) & 1)
#define ALL(v) (v).begin(), (v).end()
ll max(ll a, ll b){return (a > b) ? a : b;}
ll min(ll a, ll b){return (a < b) ? a : b;}
ll gcd(ll a, ll b){return __gcd(a, b);}
ll lcm(ll a, ll b){return a / gcd(a, b) * b;}
ll LASTBIT(ll mask){return (mask) & (-mask);}
int pop_cnt(ull mask){return __builtin_popcountll(mask);}
int ctz(ull mask){return __builtin_ctzll(mask);}
int logOf(ull mask){return 63 - __builtin_clzll(mask);}
// mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
mt19937_64 rng(1);
ll rngesus(ll l, ll r){return l + (ull) rng() % (r - l + 1);}
double rngesus_d(double l, double r){
double wow = (double) ((ull) rng()) / ((ull)(0-1));
return wow * (r - l) + l;
}
template <class T1, class T2>
bool maximize(T1 &a, T2 b){
if (a < b) {a = b; return true;}
return false;
}
template <class T1, class T2>
bool minimize(T1 &a, T2 b){
if (a > b) {a = b; return true;}
return false;
}
template <class T>
void printArr(T container, string separator = " ", string finish = "\n", ostream &out = cout){
for(auto item: container) out << item << separator;
out << finish;
}
template <class T>
void remove_dup(vector<T> &a){
sort(ALL(a));
a.resize(unique(ALL(a)) - a.begin());
}
#include "scales.h"
void init(int T);
void orderCoins();
namespace InteractorLib{
int o_cnt = 0;
vector<int> perm;
vector<int> no_king;
int getHeaviest(int i, int j, int k, int cost = 1){
o_cnt += cost;
if (perm[i] > perm[j] && perm[i] > perm[k]) return i;
if (perm[j] > perm[k]) return j;
return k;
}
int getLightest(int i, int j, int k, int cost = 1){
o_cnt += cost;
if (perm[i] < perm[j] && perm[i] < perm[k]) return i;
if (perm[j] < perm[k]) return j;
return k;
}
int getMedian(int i, int j, int k, int cost = 1){
o_cnt += cost;
return i ^ j ^ k ^ getHeaviest(i, j, k, 0) ^ getLightest(i, j, k, 0);
}
int getNextLightest(int i, int j, int k, int t, int cost = 1){
o_cnt += cost;
int mi = -1;
#define upd(i) {if (perm[i] > perm[t] && (mi == -1 || perm[i] < perm[mi])) mi = i;}
upd(i); upd(j); upd(k);
if (mi == -1) return getLightest(i, j, k, 0);
return mi;
}
void answer(int ans[]){
no_king.clear();
no_king.resize(7, -1);
for(int i = 1; i <= 6; ++i) no_king[ans[i-1]] = i;
}
double grade(){
int t = 100;
init(t);
o_cnt = 0;
for(int it = 0; it < t; ++it){
perm.resize(7, -1);
for(int i = 1; i <= 6; ++i) perm[i] = i;
shuffle(1+ALL(perm), rng);
orderCoins();
printArr(perm);
if (perm != no_king) return 0;
}
return (double) 6 * t / max(6, o_cnt);
}
}
void init(int T) {
}
int ans[6];
int T = 0;
void orderCoins() {
T++;
vector<int> A, B;
A.push_back(getLightest(1, 2, 3));
A.push_back(getMedian(1, 2, 3));
A.push_back(6 - A[0] - A[1]);
B.push_back(getLightest(4, 5, 6));
B.push_back(getMedian(4, 5, 6));
B.push_back(15 - B[0] - B[1]);
int j = 0;
memset(ans, 0, sizeof ans);
while((int) min(A.size(), B.size()) >= 2){
int vro = getNextLightest(A[1], B[0], B[1], A[0]);
if (vro == A[1]){
// B0 < B1 < A0
int cur = getMedian(A[0], B[0], B[1]);
if (cur == B[0]){
ans[j++] = A[0];
ans[j++] = A[1];
A.erase(A.begin());
A.erase(A.begin());
}
else if (cur == B[1]){
ans[j++] = B[0];
ans[j++] = B[1];
B.erase(B.begin());
B.erase(B.begin());
}
else{
ans[j++] = B[0];
ans[j++] = A[0];
ans[j++] = A[1];
A.erase(A.begin());
A.erase(A.begin());
B.erase(B.begin());
}
}
else if (vro == B[0]){
// A0 < B0 < min(A1, B1)
ans[j++] = A[0];
ans[j++] = B[0];
A.erase(A.begin());
B.erase(B.begin());
}
else if (vro == B[1]){
// B0 < A0 < B1 < A1
ans[j++] = B[0];
ans[j++] = A[0];
ans[j++] = B[1];
A.erase(A.begin());
B.erase(B.begin());
B.erase(B.begin());
}
}
if (A.empty()){
for(int i: B){
ans[j++] = i;
}
}
else if (B.empty()){
for(int i: A){
ans[j++] = i;
}
}
else{
if (A.size() > B.size()) swap(A, B);
if ((int) B.size() == 2){
int cur = getMedian(A[0], B[0], B[1]);
if (cur == A[0]){
ans[j++] = B[0];
ans[j++] = A[0];
ans[j++] = B[1];
}
else if (cur == B[0]){
ans[j++] = A[0];
ans[j++] = B[0];
ans[j++] = B[1];
}
else if (cur == B[1]){
ans[j++] = B[0];
ans[j++] = B[1];
ans[j++] = A[0];
}
}
else{
if (A[0] == getHeaviest(A[0], B[1], B[2])){
for(int i: B) ans[j++] = i;
ans[j++] = A[0];
}
else{
int cur = getNextLightest(B[0], B[1], B[2], A[0]);
for(int i: B){
if (i == cur) ans[j++]= A[0];
ans[j++] = i;
}
}
}
}
answer(ans);
}
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
