Submission #1098901

#	Time	Username	Problem	Language	Result	Execution time	Memory
1098901		alexander_707070	Scales (IOI15_scales)	C++14	71.43 / 100	42 ms	604 KiB

scales

#include<bits/stdc++.h>
#include "scales.h"
using namespace std;

vector<int> p;
vector< vector<int> > perms,news;

int getmin(vector<int> s,int a,int b,int c){
	if(s[a]<s[b] and s[a]<s[c])return 0;
	if(s[b]<s[c] and s[b]<s[a])return 1;
	return 2;
}

int getmax(vector<int> s,int a,int b,int c){
	if(s[a]>s[b] and s[a]>s[c])return 0;
	if(s[b]>s[c] and s[b]>s[a])return 1;
	return 2;
}

int getmed(vector<int> s,int a,int b,int c){
	if(s[a]<max(s[b],s[c]) and s[a]>min(s[b],s[c]))return 0;
	if(s[b]<max(s[a],s[c]) and s[b]>min(s[a],s[c]))return 1;
	return 2;
}

int br[3];
vector<int> q;

void solve(vector< vector<int> > perms){
	int minsz=perms.size();

	for(int i=0;i<3;i++){
		for(int s1=0;s1<6;s1++){
			for(int s2=s1+1;s2<6;s2++){
				for(int s3=s2+1;s3<6;s3++){
					
					br[0]=br[1]=br[2]=0;
					for(int t=0;t<perms.size();t++){
						if(i==0)br[getmin(perms[t],s1,s2,s3)]++;
						if(i==1)br[getmax(perms[t],s1,s2,s3)]++;
						if(i==2)br[getmed(perms[t],s1,s2,s3)]++;
					}

					int sz=max(br[0],max(br[1],br[2]));
					if(sz<minsz){
						minsz=sz; q={i,s1,s2,s3};
					}
				}
			}
		}
	}
}

void init(int T) {
    
}

void orderCoins() {
    
    p.clear();
    for(int i=1;i<=6;i++)p.push_back(i);

	do{
		perms.push_back(p);
	}while(next_permutation(p.begin(),p.end()));

    while(perms.size()>1){
        solve(perms);
        news.clear();

        if(q[0]==0){
            int s=getLightest(q[1]+1,q[2]+1,q[3]+1);
            if(s==q[1]+1)s=0;
            else if(s==q[2]+1)s=1;
            else if(s==q[3]+1)s=2;
            
            for(int t=0;t<perms.size();t++){
                if(getmin(perms[t],q[1],q[2],q[3])==s)news.push_back(perms[t]);
            }
        }else if(q[0]==1){
            int s=getHeaviest(q[1]+1,q[2]+1,q[3]+1);
            if(s==q[1]+1)s=0;
            else if(s==q[2]+1)s=1;
            else if(s==q[3]+1)s=2;
            
            for(int t=0;t<perms.size();t++){
                if(getmax(perms[t],q[1],q[2],q[3])==s)news.push_back(perms[t]);
            }
        }else if(q[0]==2){
            int s=getMedian(q[1]+1,q[2]+1,q[3]+1);
            if(s==q[1]+1)s=0;
            else if(s==q[2]+1)s=1;
            else if(s==q[3]+1)s=2;
            
            for(int t=0;t<perms.size();t++){
                if(getmed(perms[t],q[1],q[2],q[3])==s)news.push_back(perms[t]);
            }
        }

        perms=news;
    }

    int W[]={0,0,0,0,0,0};

    for(int i=0;i<6;i++){
        W[perms[0][i]-1]=i+1;
    }

    answer(W);
    return;
}

Compilation message (stderr)

scales.cpp: In function 'void solve(std::vector<std::vector<int> >)':
scales.cpp:29:34: warning: declaration of 'perms' shadows a global declaration [-Wshadow]
   29 | void solve(vector< vector<int> > perms){
      |            ~~~~~~~~~~~~~~~~~~~~~~^~~~~
scales.cpp:6:23: note: shadowed declaration is here
    6 | vector< vector<int> > perms,news;
      |                       ^~~~~
scales.cpp:30:22: warning: conversion from 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   30 |  int minsz=perms.size();
      |            ~~~~~~~~~~^~
scales.cpp:38:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |      for(int t=0;t<perms.size();t++){
      |                  ~^~~~~~~~~~~~~
scales.cpp: In function 'void init(int)':
scales.cpp:54:15: warning: unused parameter 'T' [-Wunused-parameter]
   54 | void init(int T) {
      |           ~~~~^
scales.cpp: In function 'void orderCoins()':
scales.cpp:77:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |             for(int t=0;t<perms.size();t++){
      |                         ~^~~~~~~~~~~~~
scales.cpp:86:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   86 |             for(int t=0;t<perms.size();t++){
      |                         ~^~~~~~~~~~~~~
scales.cpp:95:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   95 |             for(int t=0;t<perms.size();t++){
      |                         ~^~~~~~~~~~~~~

• Subtask 1: 71.428571 / 100