Submission #1017426

#	Time	Username	Problem	Language	Result	Execution time	Memory
1017426		huutuan	Scales (IOI15_scales)	C++14	71.43 / 100	14 ms	640 KiB

scales

#include "scales.h"

#include <bits/stdc++.h>

using namespace std;
using bs=bitset<720>;
bs f[3][6][6][6][3];
int ans[720][6];

void init(int T) {
   int id=0;
   vector<int> v{1, 2, 3, 4, 5, 6}, val(7);
   do{
      for (int i=0; i<6; ++i) ans[id][i]=v[i], val[v[i]]=i;
      for (int A=1; A<=6; ++A){
         for (int B=1; B<=6; ++B){
            for (int C=1; C<=6; ++C){
               if (A==B || B==C || C==A) continue;
               int id0=0, id1=0, id2=0;
               if (max({val[A], val[B], val[C]})==val[A]) id0=0;
               if (max({val[A], val[B], val[C]})==val[B]) id0=1;
               if (max({val[A], val[B], val[C]})==val[C]) id0=2;
               f[0][A-1][B-1][C-1][id0].set(id);
               if (min({val[A], val[B], val[C]})==val[A]) id1=0;
               if (min({val[A], val[B], val[C]})==val[B]) id1=1;
               if (min({val[A], val[B], val[C]})==val[C]) id1=2;
               f[1][A-1][B-1][C-1][id1].set(id);
               id2=3-id0-id1;
               f[2][A-1][B-1][C-1][id2].set(id);
            }
         }
      }
      ++id;
   }while (next_permutation(v.begin(), v.end()));
}

bs cur;

void solve(){
   if (cur.count()==1) return;
   pair<int, vector<int>> opt={100000, {}};
   for (int i=0; i<3; ++i){
      for (int A=1; A<=6; ++A){
         for (int B=1; B<=6; ++B){
            for (int C=1; C<=6; ++C){
               if (A==B || B==C || C==A) continue;
               int mx=0;
               for (int j=0; j<3; ++j) mx=max(mx, (int)(cur&f[i][A-1][B-1][C-1][j]).count());
               opt=min(opt, {mx, {i, A, B, C}});
            }
         }
      }
   }
   int id=0;
   if (opt.second[0]==0){
      id=getHeaviest(opt.second[1], opt.second[2], opt.second[3]);
   }
   if (opt.second[0]==1){
      id=getLightest(opt.second[1], opt.second[2], opt.second[3]);
   }
   if (opt.second[0]==2){
      id=getMedian(opt.second[1], opt.second[2], opt.second[3]);
   }
   id=find(opt.second.begin()+1, opt.second.begin()+4, id)-opt.second.begin()-1;
   cur&=f[opt.second[0]][opt.second[1]-1][opt.second[2]-1][opt.second[3]-1][id];
   solve();
}

void orderCoins() {
   cur.set();
   solve();
   int id=cur._Find_first();
   answer(ans[id]);
}

Compilation message (stderr)

scales.cpp: In function 'void init(int)':
scales.cpp:10:15: warning: unused parameter 'T' [-Wunused-parameter]
   10 | void init(int T) {
      |           ~~~~^
scales.cpp: In function 'void solve()':
scales.cpp:64:78: warning: conversion from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
   64 |    id=find(opt.second.begin()+1, opt.second.begin()+4, id)-opt.second.begin()-1;
      |       ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~
scales.cpp: In function 'void orderCoins()':
scales.cpp:72:26: warning: conversion from 'std::size_t' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   72 |    int id=cur._Find_first();
      |           ~~~~~~~~~~~~~~~^~

• Subtask 1: 71.428571 / 100