제출 #1224836

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1224836		faruk	저울 (IOI15_scales)	C++17	71.43 / 100	810 ms	1576 KiB

scales

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

using namespace std;

typedef pair<int, int> pii;
typedef pair<int, vector<int> > op_info;

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

vector<vector<int> > threes, fours, perms;
map<vector<int>, int> perm_to_idx;
map<vector<int>, op_info> best_op;

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

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<int> > get_split(int op_type, vector<int> &poss, vector<int> &op) {
    vector<vector<int> > out(3);
    for (int me : poss) {
        int outcome = get_outcome(op_type, op, perms[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;
}

const int what_best = 2;

vector<pair<int, op_info> > get_best_split(vector<int> &poss) {
    // try all operations of type 1-3
    vector<pair<int, op_info> > good_tries;
    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 (good_tries.size() < what_best || good_tries.back().first > cmxmin)
            {
                good_tries.emplace_back(cmxmin, op_info(typ, op));
                sort(all(good_tries));
                if (good_tries.size() > what_best)
                    good_tries.pop_back();
            }
        }
    }
    // try type 4
    for (auto op : fours) {
        auto splits = get_split(4, poss, op);
        int cmxmin = max({splits[0].size(), splits[1].size(), splits[2].size()});
        if (good_tries.size() < what_best || good_tries.back().first > cmxmin)
        {
            good_tries.emplace_back(cmxmin, op_info(4, op));
            sort(all(good_tries));
            if (good_tries.size() > what_best)
                good_tries.pop_back();
        }
    }
    return good_tries;
}

// returns depth
int build_tree(vector<int> poss) {
    if (poss.size() == 0)
        return 0;
    if (poss.size() == 1)
        return 1;
    vector<pair<int, op_info> > best_ops = get_best_split(poss);
    op_info bst; int dpth = INF;
    for (auto [useless, op] : best_ops) {
        auto splits = get_split(op.first, poss, op.second);
        int actual_depth = 0;
        for (auto splt : splits) 
            actual_depth = max(actual_depth, build_tree(splt));
        if (actual_depth < dpth)
            dpth = actual_depth, bst = op;
    }
    best_op[poss] = bst;
    return dpth + 1;
}

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

    vector<int> perm(6);
    iota(all(perm), 1);
    do {
        perm_to_idx[perm] = perms.size();
        perms.push_back(perm);
    } while (next_permutation(all(perm)));

    vector<int> strt(720);
    iota(all(strt), 0);
    build_tree(strt);
}

void orderCoins() {
    /* ... */
    vector<int> poss(720);
    iota(all(poss), 0);
    //cout << best_op.size() << "\n";

    while (poss.size() > 1) 
    {
        
        op_info to_do = best_op[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<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] = perms[poss[0]][i];
    answer(W);
}

• Subtask 1: 71.4286 / 100