Submission #1099033

#	Time	Username	Problem	Language	Result	Execution time	Memory
1099033		alexander_707070	Scales (IOI15_scales)	C++14	73.21 / 100	69 ms	600 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 getbro(vector<int> s,int a,int b,int c,int d){
    if(s[a]<s[d] and s[b]<s[d] and s[c]<s[d])return getmin(s,a,b,c);

    if(s[a]>s[d] and (s[b]<s[d] or s[a]<s[b]) and (s[c]<s[d] or s[a]<s[c]))return 0;
    if(s[b]>s[d] and (s[a]<s[d] or s[b]<s[a]) and (s[c]<s[d] or s[b]<s[c]))return 1;
    return 2;
}

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

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

	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)]++;
					}

					sort(br,br+3);

					if(br[2]<minsz){
						minsz=br[2]; minsz2=br[1]; 
                        q={i,s1,s2,s3};
					}else if(br[2]==minsz and br[1]<minsz2){
                        minsz2=br[1];
                        q={i,s1,s2,s3};
                    }
				}

			}
		}
	}

    for(int s1=0;s1<6;s1++){
        for(int s2=s1+1;s2<6;s2++){
            for(int s3=s2+1;s3<6;s3++){
                for(int s4=0;s4<6;s4++){
                    if(s4==s1 or s4==s2 or s4==s3)continue;
                
                    br[0]=br[1]=br[2]=0;
                    for(int t=0;t<perms.size();t++){
                        br[getbro(perms[t],s1,s2,s3,s4)]++;
                    }

                    sort(br,br+3);

					if(br[2]<minsz){
						minsz=br[2]; minsz2=br[1]; 
                        q={3,s1,s2,s3,s4};
					}else if(br[2]==minsz and br[1]<minsz2){
                        minsz2=br[1];
                        q={3,s1,s2,s3,s4};
                    }
                }
            }
        }
    }
}

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]);
            }
        }else if(q[0]==3){
            int s=getNextLightest(q[1]+1,q[2]+1,q[3]+1,q[4]+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(getbro(perms[t],q[1],q[2],q[3],q[4])==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:37:34: warning: declaration of 'perms' shadows a global declaration [-Wshadow]
   37 | void solve(vector< vector<int> > perms){
      |            ~~~~~~~~~~~~~~~~~~~~~~^~~~~
scales.cpp:6:23: note: shadowed declaration is here
    6 | vector< vector<int> > perms,news;
      |                       ^~~~~
scales.cpp:38:22: warning: conversion from 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   38 |  int minsz=perms.size(),minsz2=minsz;
      |            ~~~~~~~~~~^~
scales.cpp:46:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |      for(int t=0;t<perms.size();t++){
      |                  ~^~~~~~~~~~~~~
scales.cpp:74:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |                     for(int t=0;t<perms.size();t++){
      |                                 ~^~~~~~~~~~~~~
scales.cpp: In function 'void init(int)':
scales.cpp:93:15: warning: unused parameter 'T' [-Wunused-parameter]
   93 | void init(int T) {
      |           ~~~~^
scales.cpp: In function 'void orderCoins()':
scales.cpp:116:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  116 |             for(int t=0;t<perms.size();t++){
      |                         ~^~~~~~~~~~~~~
scales.cpp:125:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  125 |             for(int t=0;t<perms.size();t++){
      |                         ~^~~~~~~~~~~~~
scales.cpp:134:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  134 |             for(int t=0;t<perms.size();t++){
      |                         ~^~~~~~~~~~~~~
scales.cpp:143:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  143 |             for(int t=0;t<perms.size();t++){
      |                         ~^~~~~~~~~~~~~

• Subtask 1: 73.214286 / 100