Submission #1224800

#	Time	Username	Problem	Language	Result	Execution time	Memory
1224800		faruk	Scales (IOI15_scales)	C++17	71.43 / 100	355 ms	528 KiB

scales

#include "scales.h"
#include <bits/stdc++.h>
#define all(a) a.begin(), a.end()

using namespace std;

typedef pair<int, int> pii;

const int num_coins = 6;
const int INF = 1e9;

vector<vector<int> > threes, fours;

void get_guys(int curr, int lft, vector<int> me, vector<vector<int> > &add) {
    if (lft == 0) {
        add.push_back(me);
        return;
    }
    if (curr == num_coins + 1)
        return;
    get_guys(curr + 1, lft, me ,add);
    me.push_back(curr);
    get_guys(curr + 1, lft - 1, me, add);
}

void init(int T) {
    get_guys(1, 3, vector<int>(), threes);
    for (auto vec : threes) {
        for (int j = 1; j <= num_coins; j++) {
            if (count(all(vec), j) == 0) 
            {
                auto me = vec;
                vec.push_back(j);
                fours.push_back(vec);       
            }
        }
    }
}

int get_outcome(int op_type, vector<int> &op, vector<int> &me) {
    vector<int> ord;
    int four_weight = -1, id;
    for (int i = 0; i < 6; i++)
    {
        if (me[i] == op[2])
            ord.push_back(op[2]);
        else if (me[i] == op[0])
            ord.push_back(op[0]);
        else if (me[i] == op[1])
            ord.push_back(op[1]);
        else if (op_type == 4 and op[3] == me[i])
        {
            four_weight = i;
            if (ord.size() == 3)
                return ord[0];
            id = ord.size();
        }
    }
    if (op_type == 1)
        return ord.back();
    else if (op_type == 2)
        return ord[0];
    else if (op_type == 3)
        return ord[1];
    else
        return ord[id];
}

vector<vector<vector<int> > > get_split(int op_type, vector<vector<int> > &poss, vector<int> &op) {
    vector<vector<vector<int> > > out(3);
    for (vector<int> me : poss) {
        int outcome = get_outcome(op_type, op, me);
        if (outcome == op[0])
            out[0].push_back(me);
        else if (outcome == op[1])
            out[1].push_back(me);
        else
            out[2].push_back(me);
    }
    return out;
}

pair<int, vector<int> > get_best_split(vector<vector<int> > &poss) {
    // try all operations of type 1-3
    pair<int, vector<int> > bst; int max_min = INF;
    for (auto op : threes) {
        for (int typ = 1; typ <= 3; typ++) {
            auto splits = get_split(typ, poss, op);
            int cmxmin = max({splits[0].size(), splits[1].size(), splits[2].size()});
            if (cmxmin < max_min)
                bst = pair<int, vector<int> > (typ, op), max_min = cmxmin;
        }
    }
    for (auto op : fours) {
        auto splits = get_split(4, poss, op);
        int cmxmin = max({splits[0].size(), splits[1].size(), splits[2].size()});
            if (cmxmin < max_min)
                bst = pair<int, vector<int> > (4, op), max_min = cmxmin;
    }
    return bst;
}

void orderCoins() {
    /* ... */
    vector<vector<int> > poss;
    vector<int> perm(6);
    iota(all(perm), 1);
    do {
        poss.push_back(perm);
    } while (next_permutation(all(perm)));

    while (poss.size() > 1) 
    {
        pair<int, vector<int> > to_do = get_best_split(poss);
        int out;
        int a = to_do.second[0], b = to_do.second[1], c = to_do.second[2];
        if (to_do.first <= 3) {
            if (to_do.first == 1)
                out = getHeaviest(a, b, c);
            else if (to_do.first == 2)
                out = getLightest(a, b, c);
            else
                out = getMedian(a, b, c);
        } else {
            out = getNextLightest(a, b, c, to_do.second[3]);
        }

        vector<vector<vector<int> > > split = get_split(to_do.first, poss, to_do.second);

        if (out == a)
            poss = split[0];
        else if (out == b)
            poss = split[1];
        else if (out == c)
            poss = split[2];
    }

    int W[6];
    for (int i = 0; i < 6; i++)
        W[i] = poss[0][i];
    answer(W);
}

• Subtask 1: 71.4286 / 100