Submission #158382

#	Time	Username	Problem	Language	Result	Execution time	Memory
158382		johutha	Scales (IOI15_scales)	C++14	72.02 / 100	775 ms	584 KiB

scales

#include "scales.h"
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

enum optype
{
    Lightest, Median, Heaviest, Next,
};

void init(int t)
{

}

bool works(string input, optype op, int res, int a, int b, int c, int d = -1)
{
    vector<int> srtd;
    int dpos = -1;
    for (int i = 0; i < 6; i++)
    {
        int nm = input[i] - '0';
        if (nm == d) dpos = srtd.size();
        if (nm == a || nm == b || nm == c || nm == d) srtd.push_back(nm);
    }
    if (op == Lightest) return srtd[0] == res;
    if (op == Median) return srtd[1] == res;
    if (op == Heaviest) return srtd[2] == res;
    return srtd[(dpos + 1) % 4] == res;
}

void orderCoins() 
{
    vector<string> allst;
    string st = "123456";
    do
    {
        allst.push_back(st);
    } while (next_permutation(st.begin(), st.end()));
    while (allst.size() > 1)
    {
        vector<int> lbst;
        int lbv = 1000;
        for (int i1 = 1; i1 < 7; i1++)
        {
            for (int i2 = 1; i2 < i1; i2++)
            {
                for (int i3 = 1; i3 < i2; i3++)
                {
                    int s1 = 0;
                    int s2 = 0;
                    int s3 = 0;
                    for (string s : allst)
                    {
                        if (works(s, Lightest, i1, i1, i2, i3)) s1++;
                        else if (works(s, Lightest, i2, i1, i2, i3)) s2++;
                        else s3++;
                    }
                    if (max(s1, max(s2, s3)) < lbv)
                    {
                        lbv = max(s1, max(s2, s3));
                        lbst = {i1, i2, i3};
                    }
                }
            }
        }

        vector<int> mbst;
        int mbv = 1000;
        for (int i1 = 1; i1 < 7; i1++)
        {
            for (int i2 = 1; i2 < i1; i2++)
            {
                for (int i3 = 1; i3 < i2; i3++)
                {
                    int s1 = 0;
                    int s2 = 0;
                    int s3 = 0;
                    for (string s : allst)
                    {
                        if (works(s, Median, i1, i1, i2, i3)) s1++;
                        else if (works(s, Median, i2, i1, i2, i3)) s2++;
                        else s3++;
                    }
                    if (max(s1, max(s2, s3)) < mbv)
                    {
                        mbv = max(s1, max(s2, s3));
                        mbst = {i1, i2, i3};
                    }
                }
            }
        }

        vector<int> hbst;
        int hbv = 1000;
        for (int i1 = 1; i1 < 7; i1++)
        {
            for (int i2 = 1; i2 < i1; i2++)
            {
                for (int i3 = 1; i3 < i2; i3++)
                {
                    int s1 = 0;
                    int s2 = 0;
                    int s3 = 0;
                    for (string s : allst)
                    {
                        if (works(s, Heaviest, i1, i1, i2, i3)) s1++;
                        else if (works(s, Heaviest, i2, i1, i2, i3)) s2++;
                        else s3++;
                    }
                    if (max(s1, max(s2, s3)) < hbv)
                    {
                        hbv = max(s1, max(s2, s3));
                        hbst = {i1, i2, i3};
                    }
                }
            }
        }


        vector<int> nbst;
        int nbv = 1000;
        for (int i1 = 1; i1 < 7; i1++)
        {
            for (int i2 = 1; i2 < i1; i2++)
            {
                for (int i3 = 1; i3 < i2; i3++)
                {
                    for (int i4 = 1; i4 < 7; i4++)
                    {
                        if (i4 == i1 || i4 == i2 || i4 == i3) continue;
                        int s1 = 0;
                        int s2 = 0;
                        int s3 = 0;
                        for (string s : allst)
                        {
                            if (works(s, Next, i1, i1, i2, i3, i4)) s1++;
                            else if (works(s, Next, i2, i1, i2, i3, i4)) s2++;
                            else s3++;
                            
                        }
                        if (max(s1, max(s2, s3)) < nbv)
                        {
                            nbv = max(s1, max(s2, s3));
                            nbst = {i1, i2, i3, i4};
                        }
                    }
                }
            }
        }

        vector<string> nbt;

        if (lbv < mbv && lbv < hbv && lbv < nbv)
        {
            int r = getLightest(lbst[0], lbst[1], lbst[2]);
            for (string s : allst)
            {
                if (works(s, Lightest, r, lbst[0], lbst[1], lbst[2])) nbt.push_back(s);
            }
        }
        else if (mbv < hbv && mbv < nbv)
        {
            int r = getMedian(mbst[0], mbst[1], mbst[2]);
            for (string s : allst)
            {
                if (works(s, Median, r, mbst[0], mbst[1], mbst[2])) nbt.push_back(s);
            }
        }
        else if (hbv < nbv)
        {
            int r = getHeaviest(hbst[0], hbst[1], hbst[2]);
            for (string s : allst)
            {
                if (works(s, Heaviest, r, hbst[0], hbst[1], hbst[2])) nbt.push_back(s);
            }
        }
        else
        {
            int r = getNextLightest(nbst[0], nbst[1], nbst[2], nbst[3]);
            for (string s : allst)
            {
                if (works(s, Next, r, nbst[0], nbst[1], nbst[2], nbst[3])) nbt.push_back(s);
            }
        }
        
        allst = nbt;
    }
    vector<int> res;
    for (int i = 0; i < 6; i++)
    {
        res.push_back(allst[0][i] - '0');
    }
    answer(res.data());
}

Compilation message (stderr)

scales.cpp: In function 'void init(int)':
scales.cpp:13:15: warning: unused parameter 't' [-Wunused-parameter]
 void init(int t)
               ^
scales.cpp: In function 'bool works(std::__cxx11::string, optype, int, int, int, int, int)':
scales.cpp:25:38: warning: conversion to 'int' from 'std::vector<int>::size_type {aka long unsigned int}' may alter its value [-Wconversion]
         if (nm == d) dpos = srtd.size();
                             ~~~~~~~~~^~

• Subtask 1: 72.02381 / 100