Submission #1017561

#	Time	Username	Problem	Language	Result	Execution time	Memory
1017561		huutuan	Scales (IOI15_scales)	C++14	72.02 / 100	16 ms	1012 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(int dep){
   if (cur.count()==1) return;
   pair<int, vector<vector<int>>> opt={100000, {}};
   // pair<int, vector<int>> opt={100000, {}};
   if (dep<=2){
      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});
                  // opt=min(opt, {mx, {i, A, B, C}});
               }
            }
         }
      }
   }else{
      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());
                  if (opt.first>mx) opt={mx, {{3, A, B, C, D}}};
                  else if (opt.first==mx) opt.second.push_back({3, A, B, C, D});
                  // opt=min(opt, {mx, {3, A, B, C, D}});
               }
            }
         }
      }
   }
   vector<int> tr=opt.second[rand(0, (int)opt.second.size()-1)];
   // vector<int> tr=opt.second;
   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(dep+1);
}

void orderCoins() {
   cur.set();
   solve(0);
   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:26:23: warning: declaration of 'ans' shadows a global declaration [-Wshadow]
   26 |                   int ans=v[0].second;
      |                       ^~~
scales.cpp:8:5: note: shadowed declaration is here
    8 | int ans[720][6];
      |     ^~~
scales.cpp:10:15: warning: unused parameter 'T' [-Wunused-parameter]
   10 | void init(int T) {
      |           ~~~~^
scales.cpp: In function 'void solve(int)':
scales.cpp:98:54: warning: conversion from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
   98 |    id=find(tr.begin()+1, tr.begin()+4, id)-tr.begin()-1;
      |       ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~
scales.cpp: In function 'void orderCoins()':
scales.cpp:107:26: warning: conversion from 'std::size_t' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
  107 |    int id=cur._Find_first();
      |           ~~~~~~~~~~~~~~~^~

• Subtask 1: 72.02381 / 100