// moreflags=grader.cpp
//
// 10
// In retrospect, there's a much easier way in this particular case.
// For a more complex search algorithm, this might not be possible.
#include "scales.h"
#include<array>
#include<algorithm>
#include<bitset>
#include<numeric>
#include<climits>
#include<random>
#include<iostream>
#if LOCAL
#else
#define NDEBUG
#endif
#include<cassert>
using P=std::array<unsigned char, 6>;
using M=std::bitset<720>;
struct Query{
int type;
std::array<unsigned char, 4> parameter;
int operator()(P it) const{
std::array<std::pair<unsigned char, unsigned char>, 3> pairs;
for(int index=0; index<3; ++index)
pairs[index]={it[parameter[index]], index};
std::sort(begin(pairs), end(pairs),[&](auto first, auto sec){return first.first<sec.first;});
if(type==3){
auto const cut=it[parameter[3]];
for(auto [value, index]: pairs) if(value>cut) return index;
return pairs[0].second;
}
return pairs[type].second;
}
int get(){
auto const process=[&](auto function){
auto const result=function(parameter[0]+1, parameter[1]+1, parameter[2]+1)-1;
for(int index=0;; ++index){
assert(index<3);
if(result==parameter[index]) return index;
}
};
auto const process4=[&](auto function){
auto const result=function(parameter[0]+1, parameter[1]+1, parameter[2]+1, parameter[3]+1)-1;
for(int index=0;; ++index){
assert(index<3);
if(result==parameter[index]) return index;
}
};
switch(type){
case 0:
return process(getLightest);
case 1:
return process(getMedian);
case 2:
return process(getHeaviest);
case 3:
return process4(getNextLightest);
default:
assert(false); __builtin_unreachable();
}
}
};
int const numLayer=6;
std::array<P, 720> permutations_;
std::array<int, numLayer+1> pow3;
std::vector<int> layerOf;
std::vector<M> masks;
std::vector<Query> bestQuery;
void init(int T) {
{
P it; std::iota(begin(it), end(it), 0);
int index=0;
do{
permutations_[index++]=it;
}while(std::next_permutation(begin(it), end(it)));
}
auto const get=[&](int index)->P{return permutations_[index];};
for(int index=0, value=1; index<(int)pow3.size(); ++index, value*=3)
pow3[index]=value;
//for(int layer=0; layer<=numLayer; ++layer)
for(int layer=numLayer; layer>=0; --layer)
layerOf.insert(layerOf.end(), pow3[numLayer-layer], layer);
masks.resize(layerOf.size());
bestQuery.resize(layerOf.size());
masks[0]=~ M{};
int seed=9887;
// 37 seconds to find this value
auto const process=[&]{
std::mt19937 engine(++seed);
for(int index=0; index*3+3<(int)masks.size(); ++index){
Query best;
int bestValue=INT_MAX;
int numFound=1;
auto const process=[&](Query query){
std::array<M, 3> split{};
for(auto index2=masks[index]._Find_first(); index2<masks[index].size();
index2=masks[index]._Find_next(index2)){
split[query(get((int)index2))][index2]=true;
}
int curValue{};
for(auto it: split) curValue=std::max(curValue, (int)it.count());
if(curValue<bestValue){ bestValue=curValue; best=query; numFound=1; }
else if(curValue==bestValue){
if(std::uniform_int_distribution(0, numFound++)(engine)==0)
best=query;
}
return split;
};
/*
if(layerOf[index]>=numLayer){
process(Query{0, {{0, 1, 2}}});
}else if(layerOf[index]>=numLayer-1){
process(Query{0, {{3, 4, 5}}});
}else{
*/
{
for(unsigned char a=2; a<6; ++a)
for(unsigned char b=1; b<a; ++b)
for(unsigned char c=0; c<b; ++c){
for(int type=0; type<3; ++type)
process(Query{type, {{a, b, c}}});
for(unsigned char d=0; d<c; ++d){
process(Query{3, {{a, b, c, d}}});
process(Query{3, {{a, b, d, c}}});
process(Query{3, {{a, d, c, b}}});
process(Query{3, {{d, b, c, a}}});
}
}
}
assert(bestValue!=INT_MAX);
if(bestValue>pow3[layerOf[index]-1]){
return false;
}
auto const tmp=process(best);
bestQuery[index]=best;
for(int i=0; i<3; ++i)
masks[index*3+i+1]=std::move(tmp[i]);
}
return true;
};
while(not process()){
// assert(false);
}
//std::cerr<<seed<<'\n';
}
void orderCoins() {
int node=0;
while(masks[node].count()!=1)
node=node*3+1+bestQuery[node].get();
auto result_=permutations_[masks[node]._Find_first()];
std::array<int, 6> result;
for(int i=0; i<6; ++i)
result[result_[i]]=i+1;
answer(result.data());
}
Compilation message
scales.cpp: In lambda function:
scales.cpp:109:15: warning: declaration of 'process' shadows a previous local [-Wshadow]
109 | auto const process=[&](Query query){
| ^~~~~~~
scales.cpp:102:13: note: shadowed declaration is here
102 | auto const process=[&]{
| ^~~~~~~
scales.cpp: In function 'void init(int)':
scales.cpp:78:15: warning: unused parameter 'T' [-Wunused-parameter]
78 | void init(int T) {
| ~~~~^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
25 ms |
384 KB |
Output is correct |
| 2 |
Correct |
25 ms |
384 KB |
Output is correct |
| 3 |
Correct |
25 ms |
384 KB |
Output is correct |
| 4 |
Correct |
25 ms |
384 KB |
Output is correct |
| 5 |
Correct |
25 ms |
384 KB |
Output is correct |
| 6 |
Correct |
25 ms |
384 KB |
Output is correct |
| 7 |
Correct |
25 ms |
384 KB |
Output is correct |
| 8 |
Correct |
25 ms |
384 KB |
Output is correct |
| 9 |
Correct |
25 ms |
384 KB |
Output is correct |
| 10 |
Correct |
25 ms |
384 KB |
Output is correct |
| 11 |
Correct |
26 ms |
384 KB |
Output is correct |
| 12 |
Correct |
25 ms |
384 KB |
Output is correct |
| 13 |
Correct |
25 ms |
512 KB |
Output is correct |
| 14 |
Correct |
25 ms |
496 KB |
Output is correct |
| 15 |
Correct |
25 ms |
384 KB |
Output is correct |
| 16 |
Correct |
25 ms |
384 KB |
Output is correct |
| 17 |
Correct |
27 ms |
384 KB |
Output is correct |
| 18 |
Correct |
25 ms |
384 KB |
Output is correct |
| 19 |
Correct |
25 ms |
384 KB |
Output is correct |
| 20 |
Correct |
25 ms |
480 KB |
Output is correct |
| 21 |
Correct |
25 ms |
384 KB |
Output is correct |
| 22 |
Correct |
25 ms |
384 KB |
Output is correct |
| 23 |
Correct |
26 ms |
504 KB |
Output is correct |
| 24 |
Correct |
25 ms |
384 KB |
Output is correct |
| 25 |
Correct |
25 ms |
384 KB |
Output is correct |
| 26 |
Correct |
25 ms |
624 KB |
Output is correct |
| 27 |
Correct |
25 ms |
384 KB |
Output is correct |
| 28 |
Correct |
26 ms |
384 KB |
Output is correct |
| 29 |
Correct |
28 ms |
384 KB |
Output is correct |
| 30 |
Correct |
25 ms |
384 KB |
Output is correct |
| 31 |
Correct |
26 ms |
384 KB |
Output is correct |
| 32 |
Correct |
26 ms |
384 KB |
Output is correct |
| 33 |
Correct |
25 ms |
384 KB |
Output is correct |
| 34 |
Correct |
25 ms |
384 KB |
Output is correct |
| 35 |
Correct |
26 ms |
384 KB |
Output is correct |
| 36 |
Correct |
25 ms |
384 KB |
Output is correct |
| 37 |
Correct |
27 ms |
384 KB |
Output is correct |
| 38 |
Correct |
27 ms |
384 KB |
Output is correct |
| 39 |
Correct |
25 ms |
384 KB |
Output is correct |
| 40 |
Correct |
27 ms |
384 KB |
Output is correct |
