Submission #424549

#	Time	Username	Problem	Language	Result	Execution time	Memory
424549		KoD	저울 (IOI15_scales)	C++17	71.43 / 100	24 ms	664 KiB

scales

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

template <int N, int... SZ> struct ArrayImpl { using type = std::array<typename ArrayImpl<SZ...>::type, N>; };
template <int N> struct ArrayImpl<N> { using type = std::array<int, N>; };

template <int... SZ> using Array = typename ArrayImpl<SZ...>::type;
template <class T> using Vec = std::vector<T>;

Array<720, 6> perm;
Array<20, 3> query;
Array<60, 4> special;
Array<3, 20, 720> query_rsp;
Array<60, 720> special_rsp;

void init(int) {
    {
        Array<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_q = 0, idx_s = 0;
    for (int i = 0; i < 6; ++i) {
        for (int j = i + 1; j < 6; ++j) {
            for (int k = j + 1; k < 6; ++k) {
                query[idx_q++] = {i, j, k};
                for (int l = 0; l < 6; ++l) {
                    if (l != i and l != j and l != k) {
                        special[idx_s++] = {i, j, k, l};
                    }
                }
            }
        }
    }
    for (int i = 0; i < 20; ++i) {
        Array<3> ord = query[i];
        for (int p = 0; p < 720; ++p) {
            std::sort(ord.begin(), ord.end(), [&](const int x, const int y) {
                return perm[p][x] < perm[p][y];
            });
            for (int k = 0; k < 3; ++k) {
                query_rsp[k][i][p] = ord[k];
            }
        }
    }
    for (int i = 0; i < 60; ++i) {
        Array<4> ord = special[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];
            });
            int idx = 0;
            while (idx < 3 and perm[p][ord[idx]] < perm[p][ord[3]]) {
                idx += 1;
            }
            if (idx == 3) {
                special_rsp[i][p] = ord[0];
            } else {
                special_rsp[i][p] = ord[idx];
            }
        }
    }
}

void orderCoins() {
    Vec<int> cand(720);
    std::iota(cand.begin(), cand.end(), 0);
    while (cand.size() > 1) {
        int sk = -1, si = -1, max = -1;
        for (int k = 0; k < 3; ++k) {
            for (int i = 0; i < 20; ++i) {
                std::map<int, int> cnt;
                for (const int p : cand) {
                    cnt[query_rsp[k][i][p]] += 1;
                }
                int tmp = 0;
                for (const auto& p : cnt) {
                    tmp = std::max(tmp, p.second);
                }
                if (max == -1 or tmp < max) {
                    sk = k;
                    si = i;
                    max = tmp;
                }
            }
        }
        for (int i = 0; i < 60; ++i) {
            std::map<int, int> cnt;
            for (const int p : cand) {
                cnt[special_rsp[i][p]] += 1;
            }
            int tmp = 0;
            for (const auto& p : cnt) {
                tmp = std::max(tmp, p.second);
            }
            if (max == -1 or tmp < max) {
                sk = 3;
                si = i;
                max = tmp;
            }
        }
        if (sk == 0) {
            const auto [a, b, c] = query[si];
            const int d = getLightest(a + 1, b + 1, c + 1) - 1;
            std::cerr << "l " << a << ' ' << b << ' ' << c << ' ' << d << '\n';
            Vec<int> next;
            for (const int p : cand) {
                if (query_rsp[sk][si][p] == d) {
                    next.push_back(p);
                }
            }
            cand = std::move(next);
        } else if (sk == 1) {
            const auto [a, b, c] = query[si];
            const int d = getMedian(a + 1, b + 1, c + 1) - 1;
            std::cerr << "m " << a << ' ' << b << ' ' << c << ' ' << d << '\n';
            Vec<int> next;
            for (const int p : cand) {
                if (query_rsp[sk][si][p] == d) {
                    next.push_back(p);
                }
            }
            cand = std::move(next);
        } else if (sk == 2) {
            const auto [a, b, c] = query[si];
            const int d = getHeaviest(a + 1, b + 1, c + 1) - 1;
            std::cerr << "h " << a << ' ' << b << ' ' << c << ' ' << d << '\n';
            Vec<int> next;
            for (const int p : cand) {
                if (query_rsp[sk][si][p] == d) {
                    next.push_back(p);
                }
            }
            cand = std::move(next);
        } else {
            const auto [a, b, c, d] = special[si];
            const int e = getNextLightest(a + 1, b + 1, c + 1, d + 1) - 1;
            std::cerr << "n " << a << ' ' << b << ' ' << c << ' ' << d  << ' ' << e << '\n';
            Vec<int> next;
            for (const int p : cand) {
                if (special_rsp[si][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: 71.428571 / 100