Submission #830803

#	Time	Username	Problem	Language	Result	Execution time	Memory
830803		drdilyor	Boxes with souvenirs (IOI15_boxes)	C++17	Compilation error	0 ms	0 KiB

boxes

#include<bits/stdc++.h>
#include "scales.h"
using namespace std;
using ll = long long;
#define sz(x) int((x).size())

ll pw3[30];
const int n = 6;
const int inf = 1e9;

using st = array<int, 6>;
using op = tuple<int,int,int,int,int>;

map<vector<st>, op> usedop;

array<vector<st>, 3> getNext(vector<st> cur, op op) {
    auto [t, a, b, c, d] = op;
    array<vector<st>, 3> next{{}};
    if (t == 0) {
        for (auto& i : cur) {
            int mn = min({i[a], i[b], i[c]});
            if (i[a] == mn)
                next[0].push_back(i);
            else if (i[b] == mn)
                next[1].push_back(i);
            else
                next[2].push_back(i);
        }
    } else if (t == 1) {
        for (auto& i : cur) {
            int mx = max({i[a], i[b], i[c]});
            if (i[a] == mx)
                next[0].push_back(i);
            else if (i[b] == mx)
                next[1].push_back(i);
            else
                next[2].push_back(i);
        }
    } else if (t == 2) {
        for (auto& i : cur) {
            array cur{i[a], i[b], i[c]};
            sort(cur.begin(), cur.end());
            if (i[a] == cur[1])
                next[0].push_back(i);
            else if (i[b] == cur[1])
                next[1].push_back(i);
            else
                next[2].push_back(i);
        }
    } else {
        for (auto& i : cur) {
            array cur{i[a], i[b], i[c]};
            sort(cur.begin(), cur.end());
            int ans = -1;
            for (int j : cur) {
                if (j > i[d]) {
                    ans = j;
                    break;
                }
            }

            if (ans == -1) ans = cur[0];

            if (i[a] == ans)
                next[0].push_back(i);
            else if (i[b] == ans)
                next[1].push_back(i);
            else
                next[2].push_back(i);
        }
    }
    return next;
}

int cost(array<vector<st>, 3> pos) {
    return max({pos[0].size(), pos[1].size(), pos[2].size()});
}

int rec(vector<st> pos, int qleft) {
    if (pw3[qleft] < sz(pos)) return false;
    if (pos.size() <= 1) return true;
    array<vector<st>, 3> best;
    int bestx = inf;
    op bestq;

    auto tryAccept =[&](op op) {
        auto next = getNext(pos, op);
        int mx = max({next[0].size(), next[1].size(), next[2].size()});
        if (mx < bestx) {
            bestx = mx;
            best = next;
            bestq = op;
        }
    };

    for (int a = 0; a < n; a++) {
        for (int b = a+1; b < n; b++) {
            for (int c = b+1; c < n; c++) {
                tryAccept({0, a, b, c, -1});
                tryAccept({1, a, b, c, -1});
                tryAccept({2, a, b, c, -1});
                for (int d = 0; d < n; d++) {
                    if (d == a || d == b || d == c) continue;
                    tryAccept({3, a, b, c, d});
                }
            }
        }
    }

    assert(bestx != inf);

    if (!rec(best[0], qleft-1)) return false;
    if (!rec(best[1], qleft-1)) return false;
    if (!rec(best[2], qleft-1)) return false;
    usedop[pos] = bestq;
    return true;
}

void init(int T) {
    pw3[0] = 1;
    for (int i = 1; i < 30; i++)
        pw3[i] = pw3[i-1] * 3;

    vector<st> pos;
    st cur;
    iota(cur.begin(), cur.end(), 0);
    do {
        pos.push_back(cur);
    } while (next_permutation(cur.begin(), cur.end()));

    cerr << rec(pos, 7) << endl;
    // cout << rec(pos, 8) << endl;
}

void orderCoins() {
    vector<st> pos;{
    st cur;
    iota(cur.begin(), cur.end(), 0);
    do {
        pos.push_back(cur);
    } while (next_permutation(cur.begin(), cur.end()));}

    while (pos.size() > 1) {
        // cout << "pos.size()=" << pos.size() << endl;
        assert(usedop.count(pos));
        auto op = usedop[pos];
        auto[t, a, b, c, d] = op;
        auto next = getNext(pos, op);
        a++;b++;c++; d++;
        if (t == 0) {
            int ans = getLightest(a, b, c);
            if (ans == a) pos = next[0];
            if (ans == b) pos = next[1];
            if (ans == c) pos = next[2];
        } else if (t == 1) {
            int ans = getHeaviest(a, b, c);
            if (ans == a) pos = next[0];
            if (ans == b) pos = next[1];
            if (ans == c) pos = next[2];
        } else if (t == 2) {
            int ans = getMedian(a, b, c);
            if (ans == a) pos = next[0];
            if (ans == b) pos = next[1];
            if (ans == c) pos = next[2];
        } else {
            int ans = getNextLightest(a, b, c, d);
            if (ans == a) pos = next[0];
            if (ans == b) pos = next[1];
            if (ans == c) pos = next[2];
        }
    }
    assert(pos.size() == 1);
    int w[6];
    for (int i = 0; i < 6; i++) {
        w[pos[0][i]] = i+1;
    }
    answer(w);
}

Compilation message (stderr)

boxes.cpp:2:10: fatal error: scales.h: No such file or directory
    2 | #include "scales.h"
      |          ^~~~~~~~~~
compilation terminated.