oj.uz

답안 #424560

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
424560 2021-06-12T06:02:33 Z KoD 저울 (IOI15_scales) C++17
100 / 100
 709 ms 8764 KB 
#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<120, 4> query;
Array<120, 720> rsp;

// -2: done
// -1: ng
// other: next query
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) {
    {
        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 = 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.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 640 ms 8696 KB Output is correct
2 Correct 642 ms 8728 KB Output is correct
3 Correct 646 ms 8508 KB Output is correct
4 Correct 627 ms 8516 KB Output is correct
5 Correct 635 ms 8528 KB Output is correct
6 Correct 674 ms 8472 KB Output is correct
7 Correct 646 ms 8584 KB Output is correct
8 Correct 662 ms 8764 KB Output is correct
9 Correct 699 ms 8544 KB Output is correct
10 Correct 643 ms 8576 KB Output is correct
11 Correct 656 ms 8488 KB Output is correct
12 Correct 633 ms 8680 KB Output is correct
13 Correct 625 ms 8524 KB Output is correct
14 Correct 643 ms 8552 KB Output is correct
15 Correct 640 ms 8604 KB Output is correct
16 Correct 666 ms 8632 KB Output is correct
17 Correct 638 ms 8584 KB Output is correct
18 Correct 693 ms 8504 KB Output is correct
19 Correct 661 ms 8676 KB Output is correct
20 Correct 647 ms 8548 KB Output is correct
21 Correct 655 ms 8620 KB Output is correct
22 Correct 641 ms 8596 KB Output is correct
23 Correct 700 ms 8504 KB Output is correct
24 Correct 633 ms 8688 KB Output is correct
25 Correct 635 ms 8704 KB Output is correct
26 Correct 677 ms 8644 KB Output is correct
27 Correct 696 ms 8512 KB Output is correct
28 Correct 637 ms 8556 KB Output is correct
29 Correct 698 ms 8500 KB Output is correct
30 Correct 646 ms 8616 KB Output is correct
31 Correct 633 ms 8488 KB Output is correct
32 Correct 667 ms 8516 KB Output is correct
33 Correct 709 ms 8512 KB Output is correct
34 Correct 630 ms 8524 KB Output is correct
35 Correct 682 ms 8512 KB Output is correct
36 Correct 642 ms 8508 KB Output is correct
37 Correct 656 ms 8540 KB Output is correct
38 Correct 645 ms 8572 KB Output is correct
39 Correct 652 ms 8560 KB Output is correct
40 Correct 634 ms 8468 KB Output is correct