Submission #1029583

#	Time	Username	Problem	Language	Result	Execution time	Memory
1029583		huutuan	Scales (IOI15_scales)	C++14	100 / 100	311 ms	604 KiB

scales

#include "scales.h"

#include <bits/stdc++.h>

using namespace std;
int ans[720][6], val[720][6];
array<int, 5> query[1000];
int cntq;

void init(int T) {
   int id=0;
   vector<int> v{1, 2, 3, 4, 5, 6};
   do{
      for (int i=0; i<6; ++i) ans[id][i]=v[i], val[id][v[i]-1]=i;
      ++id;
   }while (next_permutation(v.begin(), v.end()));
   for (int A=1; A<=6; ++A){
      for (int B=A+1; B<=6; ++B){
         for (int C=B+1; C<=6; ++C){
            query[cntq++]={1, A, B, C, -1};
            query[cntq++]={2, A, B, C, -1};
            query[cntq++]={3, A, B, C, -1};
            for (int D=1; D<=6; ++D){
               if (A==D || B==D || C==D) continue;
               query[cntq++]={4, A, B, C, D};
            }
         }
      }
   }
}

int GetHeaviest(int id, int A, int B, int C){
   int res=A;
   if (val[id][B-1]>val[id][res-1]) res=B;
   if (val[id][C-1]>val[id][res-1]) res=C;
   return res;
}

int GetLightest(int id, int A, int B, int C){
   int res=A;
   if (val[id][B-1]<val[id][res-1]) res=B;
   if (val[id][C-1]<val[id][res-1]) res=C;
   return res;
}

int GetMedian(int id, int A, int B, int C){
   return A+B+C-GetHeaviest(id, A, B, C)-GetLightest(id, A, B, C);
}

int GetNextLightest(int id, int A, int B, int C, int D){
   int res=-1;
   if (val[id][A-1]>val[id][D-1] && (res==-1 || val[id][A-1]<val[id][res-1])) res=A;
   if (val[id][B-1]>val[id][D-1] && (res==-1 || val[id][B-1]<val[id][res-1])) res=B;
   if (val[id][C-1]>val[id][D-1] && (res==-1 || val[id][C-1]<val[id][res-1])) res=C;
   if (res==-1) res=GetLightest(id, A, B, C);
   return res;
}

int Get(int type, int A, int B, int C, int D){
   if (type==1) return getHeaviest(A, B, C);
   if (type==2) return getLightest(A, B, C);
   if (type==3) return getMedian(A, B, C);
   return getNextLightest(A, B, C, D);
}

int Get(int id, int type, int A, int B, int C, int D){
   if (type==1) return GetHeaviest(id, A, B, C);
   if (type==2) return GetLightest(id, A, B, C);
   if (type==3) return GetMedian(id, A, B, C);
   return GetNextLightest(id, A, B, C, D);

}

int dp(vector<int> cur, int dep){
   int val=pow(3, dep);
   if ((int)cur.size()>val) return -1;
   if (cur.size()<=1) return 0;
   for (int i=0; i<cntq; ++i){
      vector<int> ca, cb, cc;
      int type=query[i][0], A=query[i][1], B=query[i][2], C=query[i][3], D=query[i][4];
      for (int j:cur){
         int res=Get(j, type, A, B, C, D);
         if (res==A) ca.push_back(j);
         if (res==B) cb.push_back(j);
         if (res==C) cc.push_back(j);
      }
      if (ca.size()==cur.size() || cb.size()==cur.size() || cc.size()==cur.size()) continue;
      if ((int)ca.size()>val/3 || (int)cb.size()>val/3 || (int)cc.size()>val/3) continue;
      if (dp(ca, dep-1)!=-1 && dp(cb, dep-1)!=-1 && dp(cc, dep-1)!=-1) return i;
   }
   return -1;
}

vector<int> cur;

void solve(int dep){
   if (cur.size()==1) return;
   int i=dp(cur, dep);
   vector<int> ca, cb, cc;
   int type=query[i][0], A=query[i][1], B=query[i][2], C=query[i][3], D=query[i][4];
   for (int j:cur){
      int res=Get(j, type, A, B, C, D);
      if (res==A) ca.push_back(j);
      if (res==B) cb.push_back(j);
      if (res==C) cc.push_back(j);
   }
   int res=Get(type, A, B, C, D);
   if (res==A) cur=ca;
   if (res==B) cur=cb;
   if (res==C) cur=cc;
   solve(dep-1);
}

void orderCoins() {
   cur.resize(720);
   iota(cur.begin(), cur.end(), 0);
   solve(6);
   answer(ans[cur[0]]);
}

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 'int dp(std::vector<int>, int)':
scales.cpp:75:8: warning: declaration of 'val' shadows a global declaration [-Wshadow]
   75 |    int val=pow(3, dep);
      |        ^~~
scales.cpp:6:18: note: shadowed declaration is here
    6 | int ans[720][6], val[720][6];
      |                  ^~~
scales.cpp:75:15: warning: conversion from '__gnu_cxx::__promote_2<int, int, double, double>::__type' {aka 'double'} to 'int' may change value [-Wfloat-conversion]
   75 |    int val=pow(3, dep);
      |            ~~~^~~~~~~~

• Subtask 1: 100 / 100