Submission #126038

#	Time	Username	Problem	Language	Result	Execution time	Memory
126038		dragonslayerit	Scales (IOI15_scales)	C++14	71.73 / 100	13 ms	476 KiB

scales

#include "scales.h"
#include <vector>
#include <array>
#include <algorithm>
#include <cassert>

void init(int T) {
  (void)T;
}

//possible ranks of coins
std::vector<std::array<int,6> > possible;

int consider(int a,int b,int c){
  int remain[3][3]={{0,0,0},{0,0,0},{0,0,0}};
  int vs[3]={a,b,c};
  int xs[3]={0,1,2};
  for(auto ps:possible){
    std::sort(xs,xs+3,[&ps,&vs](int i,int j){return ps[vs[i]]<ps[vs[j]];});
    for(int i=0;i<3;i++){
      remain[i][xs[i]]++;
    }
  }
  int best=720;
  for(int i=0;i<3;i++){
    best=std::min(best,*std::max_element(remain[i],remain[i]+3));
  }
  return best;
}

int query(int a,int b,int c,int t){
  a++,b++,c++;
  if(t==0) return getLightest(a,b,c)-1;
  if(t==1) return getMedian(a,b,c)-1;
  if(t==2) return getHeaviest(a,b,c)-1;
  assert(0);
}

void reduce(int a,int b,int c){
  std::vector<std::array<int,6> > remain[3][3];
  int vs[3]={a,b,c};
  int xs[3]={0,1,2};
  for(auto ps:possible){
    std::sort(xs,xs+3,[&ps,&vs](int i,int j){return ps[vs[i]]<ps[vs[j]];});
    for(int i=0;i<3;i++){
      remain[i][xs[i]].push_back(ps);
    }
  }
  int worst[3]={0,0,0};
  for(int i=0;i<3;i++){
    for(int j=0;j<3;j++){
      worst[i]=std::max<int>(worst[i],remain[i][j].size());
    }
  }
  int type=std::min_element(worst,worst+3)-worst;
  int which=std::find(vs,vs+3,query(a,b,c,type))-vs;
  possible=remain[type][which];
}

void orderCoins() {
  //init
  {
    std::array<int,6> ps({0,1,2,3,4,5});
    do{
      possible.push_back(ps);
    }while(std::next_permutation(ps.begin(),ps.end()));
  }
  //main
  while(possible.size()>1){
    std::array<int,4> best={720,10,10,10};
    for(int a=0;a<6;a++){
      for(int b=0;b<a;b++){
	for(int c=0;c<b;c++){
	  best=std::min(best,{consider(a,b,c),a,b,c});
	}
      }
    }
    reduce(best[1],best[2],best[3]);
    /*
    printf("%d permuations remaining\n",(int)possible.size());
    if(possible.size()<=10){
      for(auto ps:possible){
	printf("%d %d %d %d %d %d\n",ps[0],ps[1],ps[2],ps[3],ps[4],ps[5]);
      }
    }
    */
  }
  assert(possible.size()==1);
  int coins[6]={1,2,3,4,5,6};
  std::sort(coins,coins+6,[](int i,int j){return possible[0][i-1]<possible[0][j-1];});
  answer(coins);
}

Compilation message (stderr)

scales.cpp: In function 'void reduce(int, int, int)':
scales.cpp:52:56: warning: conversion to 'int' from 'std::vector<std::array<int, 6> >::size_type {aka long unsigned int}' may alter its value [-Wconversion]
       worst[i]=std::max<int>(worst[i],remain[i][j].size());
                                       ~~~~~~~~~~~~~~~~~^~
scales.cpp:55:43: warning: conversion to 'int' from 'long int' may alter its value [-Wconversion]
   int type=std::min_element(worst,worst+3)-worst;
            ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~
scales.cpp:56:49: warning: conversion to 'int' from 'long int' may alter its value [-Wconversion]
   int which=std::find(vs,vs+3,query(a,b,c,type))-vs;
             ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~

• Subtask 1: 71.72619 / 100