Submission #126040

#	Time	Username	Problem	Language	Result	Execution time	Memory
126040		dragonslayerit	Scales (IOI15_scales)	C++14	72.62 / 100	48 ms	504 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 consider1(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 consider2(int a,int b,int c,int d){
  int remain[3]={0,0,0};
  int vs[4]={a,b,c,d};
  int xs[4]={0,1,2,3};
  for(auto ps:possible){
    std::sort(xs,xs+4,[&ps,&vs](int i,int j){return ps[vs[i]]<ps[vs[j]];});
    remain[xs[(std::find(xs,xs+4,3)-xs+1)%4]]++;
  }
  return *std::max_element(remain,remain+3);
}

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 reduce1(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 reduce2(int a,int b,int c,int d){
  //fprintf(stderr,"DDDDDDDDDDDD\n");
  std::vector<std::array<int,6> > remain[3];
  int vs[4]={a,b,c,d};
  int xs[4]={0,1,2,3};
  for(auto ps:possible){
    std::sort(xs,xs+4,[&ps,&vs](int i,int j){return ps[vs[i]]<ps[vs[j]];});
    remain[xs[(std::find(xs,xs+4,3)-xs+1)%4]].push_back(ps);
  }
  int which=std::find(vs,vs+3,getNextLightest(a+1,b+1,c+1,d+1)-1)-vs;
  possible=remain[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,5> best={720,10,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,{consider1(a,b,c),a,b,c,-1});
	  for(int d=0;d<6;d++){
	    if(d==a||d==b||d==c) continue;
	    best=std::min(best,{consider2(a,b,c,d),a,b,c,d});
	  }
	}
      }
    }
    //printf("expect %d permutations\n",best[0]);
    if(best[4]==-1){
      reduce1(best[1],best[2],best[3]);
    }else{
      reduce2(best[1],best[2],best[3],best[4]);
    }
    /*
    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 reduce1(int, int, int)':
scales.cpp:63: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:66:43: warning: conversion to 'int' from 'long int' may alter its value [-Wconversion]
   int type=std::min_element(worst,worst+3)-worst;
            ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~
scales.cpp:67: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;
             ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~
scales.cpp: In function 'void reduce2(int, int, int, int)':
scales.cpp:80:66: warning: conversion to 'int' from 'long int' may alter its value [-Wconversion]
   int which=std::find(vs,vs+3,getNextLightest(a+1,b+1,c+1,d+1)-1)-vs;
             ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~

• Subtask 1: 72.619048 / 100