Submission #1017532

#	Time	Username	Problem	Language	Result	Execution time	Memory
1017532		huutuan	Scales (IOI15_scales)	C++14	0 / 100	1100 ms	5204 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];
map<string, int> mp[7];
map<string, vector<int>> tr[7];

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()));
}

int dp(bs cur, int dep, int _dep){
   if (_dep-dep>=2){
      int p=1, c=0;
      while (p<cur.count()) p*=3, ++c;
      return c;
   }
   if (mp[_dep].count(cur.to_string())) return mp[_dep][cur.to_string()];
   if (cur.count()<=1) return mp[_dep][cur.to_string()]=0;
   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){
                  bs nxt=cur&f[i][A-1][B-1][C-1][j];
                  if (nxt.count()==cur.count()) mx=1e9;
                  else mx=max(mx, dp(nxt, dep-1, _dep)+1);
               }
               opt=min(opt, {mx, {i, A, B, C}});
            }
         }
      }
   }
   if (dep!=6){
      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){
                     bs nxt=cur&fd[A-1][B-1][C-1][D-1][j];
                     if (nxt.count()==cur.count()) mx=1e9;
                     else mx=max(mx, dp(nxt, dep-1, _dep)+1);
                  }
                  opt=min(opt, {mx, {3, A, B, C, D}});
               }
            }
         }
      }
   }
   tr[_dep][cur.to_string()]=opt.second;
   return mp[_dep][cur.to_string()]=opt.first;
}

bs cur;

void solve(int dep){
   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}});
   //          }
   //       }
   //    }
   // }
   // 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}});
   //          }
   //       }
   //    }
   // }
   dp(cur, dep, dep);
   vector<int> opt=tr[dep][cur.to_string()];
   int id=0;
   if (opt[0]==0){
      id=getHeaviest(opt[1], opt[2], opt[3]);
   }
   if (opt[0]==1){
      id=getLightest(opt[1], opt[2], opt[3]);
   }
   if (opt[0]==2){
      id=getMedian(opt[1], opt[2], opt[3]);
   }
   if (opt[0]==3){
      id=getNextLightest(opt[1], opt[2], opt[3], opt[4]);
   }
   id=find(opt.begin()+1, opt.begin()+4, id)-opt.begin()-1;
   if (opt[0]!=3) cur&=f[opt[0]][opt[1]-1][opt[2]-1][opt[3]-1][id];
   else cur&=fd[opt[1]-1][opt[2]-1][opt[3]-1][opt[4]-1][id];
   solve(dep-1);
}

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

Compilation message (stderr)

scales.cpp: In function 'void init(int)':
scales.cpp:21:39: warning: declaration of 'v' shadows a previous local [-Wshadow]
   21 |                vector<pair<int, int>> v{{val[A], 0}, {val[B], 1}, {val[C], 2}};
      |                                       ^
scales.cpp:14:16: note: shadowed declaration is here
   14 |    vector<int> v{1, 2, 3, 4, 5, 6}, val(7);
      |                ^
scales.cpp:28:23: warning: declaration of 'ans' shadows a global declaration [-Wshadow]
   28 |                   int ans=v[0].second;
      |                       ^~~
scales.cpp:8:5: note: shadowed declaration is here
    8 | int ans[720][6];
      |     ^~~
scales.cpp:12:15: warning: unused parameter 'T' [-Wunused-parameter]
   12 | void init(int T) {
      |           ~~~~^
scales.cpp: In function 'int dp(bs, int, int)':
scales.cpp:44:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::size_t' {aka 'long unsigned int'} [-Wsign-compare]
   44 |       while (p<cur.count()) p*=3, ++c;
      |              ~^~~~~~~~~~~~
scales.cpp: In function 'void solve(int)':
scales.cpp:134:57: warning: conversion from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
  134 |    id=find(opt.begin()+1, opt.begin()+4, id)-opt.begin()-1;
      |       ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~
scales.cpp: In function 'void orderCoins()':
scales.cpp:143:26: warning: conversion from 'std::size_t' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
  143 |    int id=cur._Find_first();
      |           ~~~~~~~~~~~~~~~^~

• Subtask 1: 0 / 100