Submission #1017471

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

scales

#include "scales.h"

#include <bits/stdc++.h>

using namespace std;
using bs=bitset<720>;
bs f[3][6][6][6][3];// fd[6][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;
               vector<pair<int, int>> v{{val[A], 0}, {val[B], 1}, {val[C], 2}};
               sort(v.begin(), v.end());
               f[0][A-1][B-1][C-1][v[2].second].set(id);
               f[1][A-1][B-1][C-1][v[0].second].set(id);
               f[2][A-1][B-1][C-1][v[1].second].set(id);
               // for (int D=1; D<=6; ++D){
               //    if (A==D || B==D || C==D) continue;
               //    int ans=v[0].second;
               //    if (v[0].first>val[D]) ans=v[0].second;
               //    else if (v[1].first>val[D]) ans=v[1].second;
               //    else if (v[2].first>val[D]) ans=v[2].second;
               //    fd[A-1][B-1][C-1][D-1][ans].set(id);
               // }
            }
         }
      }
      ++id;
   }while (next_permutation(v.begin(), v.end()));
}

bs cur;

mt19937 rng(69420);

int rand(int l, int r){
   return uniform_int_distribution<int>(l, r)(rng);
}

void solve(){
   if (cur.count()==1) return;
   pair<int, vector<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());
               if (opt.first>mx) opt={mx, {{i, A, B, C}}};
               else if (opt.first==mx) opt.second.push_back({i, A, B, C});
            }
         }
      }
   }
   // 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;
   //          for (int D=1; D<=6; ++D){
   //             if (A==D || B==D || C==D) continue;
   //             int mx=0;
   //             for (int j=0; j<3; ++j) mx=max(mx, (int)(cur&fd[A-1][B-1][C-1][D-1][j]).count());
   //             opt=min(opt, {mx, {3, A, B, C, D}});
   //          }
   //       }
   //    }
   // }
   vector<int> tr=opt.second[rand(0, (int)opt.second.size()-1)];
   int id=0;
   if (tr[0]==0){
      id=getHeaviest(tr[1], tr[2], tr[3]);
   }
   if (tr[0]==1){
      id=getLightest(tr[1], tr[2], tr[3]);
   }
   if (tr[0]==2){
      id=getMedian(tr[1], tr[2], tr[3]);
   }
   // if (tr[0]==3){
   //    id=getNextLightest(tr[1], tr[2], tr[3], tr[4]);
   // }
   id=find(tr.begin()+1, tr.begin()+4, id)-tr.begin()-1;
   if (tr[0]!=3) cur&=f[tr[0]][tr[1]-1][tr[2]-1][tr[3]-1][id];
   // else cur&=fd[tr[1]-1][tr[2]-1][tr[3]-1][tr[4]-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:19:39: warning: declaration of 'v' shadows a previous local [-Wshadow]
   19 |                vector<pair<int, int>> v{{val[A], 0}, {val[B], 1}, {val[C], 2}};
      |                                       ^
scales.cpp:12:16: note: shadowed declaration is here
   12 |    vector<int> v{1, 2, 3, 4, 5, 6}, val(7);
      |                ^
scales.cpp:10:15: warning: unused parameter 'T' [-Wunused-parameter]
   10 | void init(int T) {
      |           ~~~~^
scales.cpp: In function 'void solve()':
scales.cpp:90:54: warning: conversion from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
   90 |    id=find(tr.begin()+1, tr.begin()+4, id)-tr.begin()-1;
      |       ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~
scales.cpp: In function 'void orderCoins()':
scales.cpp:99:26: warning: conversion from 'std::size_t' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   99 |    int id=cur._Find_first();
      |           ~~~~~~~~~~~~~~~^~

• Subtask 1: 71.428571 / 100