| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 289437 | user202729 | Scales (IOI15_scales) | C++17 | 2 ms | 512 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "scales.h"
#include<bits/stdc++.h>
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::mt19937 engine;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=numLayer; layer>=0; --layer)
layerOf.insert(layerOf.end(), pow3[numLayer-layer], layer);masks.resize(layerOf.size());bestQuery.resize(layerOf.size());masks[0]=~ M{};bestQuery={{{1,{4,2}},{3,{5,3,1}},{0,{5,3,1}},{3,{5,3,1}},{2,{4,3,1}},{3,{5,4,1,2}},{3,{5,4,3,2}},{3,{0,3,1,4}},{3,{0,4,1,5}},{3,{0,4,3,5}},{0,{4,3,1}},{3,{5,4,2,1}},{3,{5,4,2,3}},{3,{1,3,2,5}},{3,{2,4,3,5}},{3,{1,4,2,5}},{2,{5,4}},{3,{5,4,1,3}},{1,{4,2,1}},{3,{0,3,1,4}},{2,{5,3,2}},{3,{5,0,1,4}},{3,{1,3,2,5}},{3,{5,0,1,2}},{2,{4,3}},{0,{5,2}},{3,{5,0,2,3}},{3,{4,0,2,3}},{3,{5,4,2,1}},{3,{5,2,0,1}},{2,{4,3}},{2,{3,1}},{1,{4,3,2}},{3,{5,0,3,4}},{2,{5,4,3}},{2,{2,1}},{2,{4,1}},{1,{5,4,1}},{2,{3,2}},{2,{4,3}},{1,{5,2}},{1,{5,2}},{0,{5,3,1}},{3,{4,3,2,1}},{3,{5,4,2,1}},{3,{0,2,1,4}},{3,{0,3,2,4}},{1,{3,2,1}},{1,{5,4,2}},{1,{5,3,1}},{1,{5,4,3}},{3,{5,4,0,1}},{1,{5,4,1}},{2,{5,2,1}},{1,{5,4,3}},{1,{4,3,1}},{1,{5,3,2}},{1,{5,3,2}},{1,{4,1}},{0,{5,4,2}},{2,{5,4,3}},{1,{3,2,1}},{1,{5,2,1}},{2,{5,3,1}},{2,{3,2}},{2,{2,1}},{1,{5,3,1}},{0,{4,3,2}},{0,{4,2,1}},{3,{5,3,1}},{1,{2,1}},{3,{4,3,1,2}},{3,{0,4,1,5}},{3,{0,4,1,5}},{3,{0,4,2,5}},{3,{5,1,2,4}},{2,{5,4,1}},{3,{1,4,3,5}},{3,{5,0,2,3}},{2,{5,1}},{3,{5,2,1}},{3,{5,2,0,1}},{3,{2,4,3,5}},{1,{5,3,2}},{3,{5,0,2,4}},{1,{3,2,1}},{1,{5,3,2}},{1,{2,1}},{1,{5,3,2}},{3,{4,0,2,3}},{1,{5,3,2}},{1,{5,3,2}},{3,{3,0,1,2}},{1,{5,3,2}},{3,{3,0,1,2}},{3,{5,4,1,2}},{3,{1,3,2,5}},{3,{4,3,0,1}},{3,{2,4,3,5}},{1,{5,4,1}},{1,{5,3,2}},{0,{4,3}},{2,{3,2}},{3,{0,3,1,4}},{3,{5,0,3,4}},{1,{4,2,1}},{3,{5,2,3,4}},{3,{0,2,1,5}},{1,{5,3,2}},{3,{5,4,3,2}},{3,{0,4,2,5}},{3,{5,2,3,4}},{3,{5,0,1,2}},{3,{5,0,1,2}},{2,{5,2}},{2,{5,4,2}},{1,{5,3}},{1,{4,3,1}},{1,{5,2,1}},{3,{0,4,3,5}},{1,{3,2,1}},{1,{4,3}},{3,{4,3,2}},{3,{5,4,3,2}},{0,{3,2,1}},{3,{4,2,0,1}},{0,{5,2,1}},{0,{4,3,1}},{3,{5,0,3,4}},{0,{5,4,2}},{1,{5,4,2}},{0,{5,4,2}},{0,{5,2}},{3,{5,1,2,3}},{3,{5,3,0,2}},{1,{5,3,2}},{3,{5,3,2,1}},{3,{0,2,1,3}},{2,{5,1}},{1,{4,3,2}},{1,{5,3}},{3,{5,1,2,3}},{3,{0,3,2,4}},{1,{5,4,3}},{3,{4,0,2,3}},{1,{3,2}},{3,{4,0,2,3}},{1,{4,3,2}},{1,{4,3,2}},{3,{5,4,2,3}},{3,{5,1,3,4}},{3,{0,3,1,4}},{3,{4,3,1,2}},{1,{4,3,1}},{2,{3,2,1}},{1,{5,3,2}},{1,{3,2,1}},{3,{4,2,1}},{2,{5,3}},{0,{5,4,3}},{1,{4,3,2}},{3,{5,3,0,1}},{1,{3,2}},{2,{3,1}},{2,{3,1}},{1,{4,3}},{3,{5,4,3,2}},{3,{0,4,1,5}},{1,{5,4}},{3,{5,2,3,4}},{2,{5,4,3}},{0,{5,4,3}},{3,{0,4,2,5}},{3,{1,4,3,5}},{2,{5,4,3}},{3,{5,3,2,1}},{1,{5,2}},{1,{3,2}},{3,{0,4,3,5}},{1,{5,4,3}},{1,{4,2,1}},{3,{5,3,2,1}},{1,{5,2,1}},{0,{5,2,1}},{1,{5,4,1}},{3,{5,3,0,2}},{3,{4,2,0,1}},{1,{3,2,1}},{2,{3,1}},{3,{0,3,1,4}},{1,{5,4,1}},{3,{0,2,1,4}},{3,{5,2,3,4}},{1,{5,3,1}},{3,{5,3,2,1}},{1,{5,2,1}},{1,{3,2,1}},{1,{5,3,1}},{3,{5,3,2,1}},{2,{3,2,1}},{1,{4,2,1}},{3,{5,4,1,2}},{1,{5,4}},{3,{5,0,2,4}},{3,{5,2,1}},{1,{5,4}},{3,{0,4,2,5}},{1,{5,2}},{3,{5,0,1,3}},{3,{0,4,2,5}},{3,{0,4,2,5}},{3,{5,1,2,4}},{1,{3,2,1}},{3,{5,0,1,3}},{1,{5,4,1}},{3,{1,4,3,5}},{1,{5,4,1}},{3,{5,0,1,3}},{3,{4,3,0,2}},{1,{3,2,1}},{3,{5,0,2,3}},{3,{5,3,1,2}},{3,{5,0,2,3}},{1,{5,2}},{3,{4,3,1,2}},{1,{4,2,1}},{3,{3,0,1,2}},{3,{5,4,2,3}},{1,{5,4,3}},{1,{4,3,1}},{3,{3,2,0,1}},{1,{4,3}},{3,{4,1,2,3}},{3,{5,3,1,2}},{3,{4,3,2,1}},{3,{1,3,2,4}},{3,{5,4,2,1}},{3,{4,2,0,1}},{3,{5,4,0,2}},{3,{3,0,1,2}},{3,{4,2,0,1}},{0,{5,4,1}},{1,{5,1}},{1,{5,3,2}},{3,{5,4,0,3}},{1,{5,4,3}},{0,{4,3}},{1,{4,2,1}},{0,{3,2}},{3,{3,2,0,1}},{3,{3,2,0,1}},{1,{5,4}},{2,{5,4,1}},{3,{5,0,1,2}},{3,{5,0,1,2}},{3,{0,4,2,5}},{3,{4,3,2}},{3,{0,3,2,4}},{3,{4,3,2}},{3,{5,4,3,2}},{3,{0,3,2,4}},{3,{4,0,1,3}},{3,{5,1,2,3}},{3,{4,1,2,3}},{1,{4,3,2}},{1,{4,2,1}},{0,{4,2,1}},{3,{4,3,2}},{3,{5,4,0,1}},{1,{5,4,1}},{1,{5,4,1}},{3,{5,3,2}},{1,{3,2}},{1,{5,3}},{3,{4,2,0,1}},{1,{3,1}},{3,{5,2,1}},{3,{5,0,1,3}},{1,{4,2,1}},{3,{5,1,2,4}},{1,{4,2,1}},{3,{0,3,1,4}},{3,{0,3,1,4}},{3,{1,4,2,5}},{3,{5,0,3,4}},{3,{5,3,0,2}},{3,{4,3,1,2}},{1,{4,3}},{3,{0,2,1,3}},{1,{5,4,3}},{1,{5,4,3}},{3,{5,1,3,4}},{1,{5,4,2}},{1,{5,2,1}},{1,{5,2,1}},{0,{5,1}},{1,{4,1}},{3,{4,2,0,1}},{1,{5,2,1}},{1,{2,1}},{1,{5,2,1}},{3,{5,4,1,2}},{1,{3,2,1}},{1,{3,2,1}},{3,{5,3,0,2}},{1,{5,2}},{3,{5,4,2,1}},{1,{5,2,1}},{1,{5,2,1}},{3,{4,3,1,2}},{3,{3,0,1,2}},{3,{4,0,2,3}},{3,{4,3,0,2}},{1,{2,1}},{2,{3,2,1}},{3,{4,3,1,2}},{3,{4,3,1,2}},{1,{3,2}},{1,{3,2,1}},{1,{3,2}},{2,{5,3,2}},{1,{5,2,1}},{1,{5,3,2}},{0,{5,4}},{3,{4,3,0,2}},{1,{5,4,3}},{1,{4,3,1}},{3,{5,4,2,3}},{1,{5,4,3}},{2,{5,4,3}},{1,{5,4,2}},{2,{4,3,2}},{1,{5,3,1}},{3,{0,3,2,4}},{1,{4,3,2}},{0,{5,3}},{0,{5,3}},{3,{5,0,1,4}},{1,{3,2}},{1,{4,3}},{0,{3,2}},{1,{5,3}},{1,{3,1}},{1,{2,1}},{1,{3,1}},{1,{3,2}},{3,{4,0,1,2}},{1,{5,2,1}},{1,{5,2,1}},{1,{2,1}},{1,{4,2,1}},{3,{5,3,1,2}},{1,{5,4,2}},{3,{5,4,1,2}},{1,{5,3,2}},{3,{1,4,2,5}},{1,{5,4,1}},{3,{5,0,1,4}},{3,{5,1,2,4}},{2,{5,4}},{2,{4,2,1}},{3,{5,1,2,4}},{1,{5,4,1}},{1,{5,4,1}},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},}};auto const process=[&]{
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;};process(bestQuery[index]);assert(bestValue!=INT_MAX);if(bestValue>pow3[layerOf[index]-1]){
assert(false);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()){}
for(auto it: bestQuery){
std::cout<<it.type<<' ';for(auto it: it.parameter) std::cout<<it<<' ';std::cout<<'\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 (stderr)
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| Fetching results... | ||||