Submission #424567

#	Time	Username	Problem	Language	Result	Execution time	Memory
424567		KoD	Scales (IOI15_scales)	C++17	100 / 100	732 ms	8708 KiB

scales

#include <bits/stdc++.h>
#include "scales.h"

template <class T> using Vec = std::vector<T>;

std::array<std::array<int, 6>, 720> perm;
std::array<std::array<int, 4>, 120> query;
std::array<std::array<int, 720>, 120> rsp;

std::map<Vec<int>, int> memo;
int find_next(const Vec<int>& cand) {
    const auto itr = memo.find(cand);
    if (itr != memo.end()) {
        return itr -> second;
    }
    const int sz = (int) cand.size();
    if (sz == 1)  { 
        return memo[cand] = -2;
    }
    int nsz = 1;
    while (nsz * 3 < sz) {
        nsz *= 3;
    }
    for (int i = 0; i < 120; ++i) {
        std::map<int, Vec<int>> next;
        for (const int p : cand) {
            next[rsp[i][p]].push_back(p);
        }
        bool ok = true;
        for (const auto& p: next) {
            if ((int) p.second.size() > nsz or find_next(p.second) == -1) {
                ok = false;
                break;
            }
        }
        if (ok) {
            return memo[cand] = i;
        }
    }
    return memo[cand] = -1;
}

void init(int) {
    {
        std::array<int, 6> ord;
        std::iota(ord.begin(), ord.end(), 1);
        for (int i = 0; i < 720; ++i) {
            perm[i] = ord;
            std::next_permutation(ord.begin(), ord.end());
        } 
    }
    {
        int idx = 0;
        for (int i = 0; i < 6; ++i) {
            for (int j = i + 1; j < 6; ++j) {
                for (int k = j + 1; k < 6; ++k) {
                    for (int l = 0; l < 6; ++l) {
                        query[idx++] = {i, j, k, l};
                    }
                }
            }
        }
    }
    for (int i = 0; i < 120; ++i) {
        auto ord = query[i];
        for (int p = 0; p < 720; ++p) {
            std::sort(ord.begin(), ord.begin() + 3, [&](const int x, const int y) {
                return perm[p][x] < perm[p][y];
            });
            bool done = false;
            for (int k = 0; k < 3; ++k) {
                if (query[i][k] == query[i][3]) {
                    rsp[i][p] = ord[k];
                    done = true;
                }
            }
            if (!done) {
                int idx = 0;
                while (perm[p][ord[idx]] < perm[p][ord[3]]) {
                    idx += 1;
                }
                rsp[i][p] = (idx == 3 ? ord[0] : ord[idx]);
            }
        }
    }
}

void orderCoins() {
    Vec<int> cand(720);
    std::iota(cand.begin(), cand.end(), 0);
    while (cand.size() > 1) {
        const auto i = find_next(cand);
        const auto [a, b, c, d] = query[i];
        Vec<int> next;
        const auto e = [&] {
            if (a == d) return getLightest(a + 1, b + 1, c + 1) - 1;
            if (b == d) return getMedian(a + 1, b + 1, c + 1) - 1;
            if (c == d) return getHeaviest(a + 1, b + 1, c + 1) - 1;
            return getNextLightest(a + 1, b + 1, c + 1, d + 1) - 1;
        }();
        for (const auto p : cand) {
            if (rsp[i][p] == e) {
                next.push_back(p);
            }
        }
        cand = std::move(next);
    }
    const int p = cand[0];
    int W[6];
    std::iota(W, W + 6, 0);
    std::sort(W, W + 6, [&](const int x, const int y) {
        return perm[p][x] < perm[p][y];
    });
    for (auto& x : W) {
        x += 1;
    }
    answer(W);
}

• Subtask 1: 100 / 100