Submission #1288178

#	Time	Username	Problem	Language	Result	Execution time	Memory
1288178		ortsac	Scales (IOI15_scales)	C++20	73.21 / 100	12 ms	468 KiB

scales

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

using namespace std;

#define pii pair<int, int>
#define fr first
#define se second

struct Query {
    array<int, 3> vals = {0, 0, 0};
    int t = 0, d = 0;
    // 1 is light, 2 is heavy, 3 is median, and 4 is the lightest greater
    bool operator<(const Query& a) const {
        return false;
    }
    bool operator>(const Query& a) const {
        return false;
    }
};

Query start;

vector<Query> allQueries;

void init(int T) {
    // pergunta inicial
    start.t = 1;
    start.vals = {4, 5, 6};
    // ok
    vector<int> n3 = {0, 0, 0, 1, 1, 1};
    vector<int> n4 = {0, 0, 1, 1, 1, 2};
    // find all of 3 type
    do {
        Query q;
        int cnt = 0;
        for (int i = 0; i < 6; i++) if (n3[i]) q.vals[cnt++] = (i + 1);
        q.t = 1;
        allQueries.push_back(q);
        q.t = 2;
        allQueries.push_back(q);
        q.t = 3;
        allQueries.push_back(q);
    } while (next_permutation(n3.begin(), n3.end()));
    do {
        Query q;
        int cnt = 0;
        for (int i = 0; i < 6; i++) if (n4[i]) {
            if (n4[i] < 2) q.vals[cnt++] = (i + 1);
            else q.d = i + 1;
        }
        q.t = 4;
        allQueries.push_back(q);
    } while (next_permutation(n4.begin(), n4.end()));
}

int ans(array<int, 6>& perm, Query& q) {
    array<pii, 3> ord;
    for (int i = 0; i < 3; i++) ord[i] = {perm[q.vals[i] - 1], q.vals[i]};
    sort(ord.begin(), ord.end());
    if (q.t == 1) return ord[0].se;
    if (q.t == 2) return ord[2].se;
    if (q.t == 3) return ord[1].se;
    for (int i = 0; i < 3; i++) if (perm[q.d - 1] < ord[i].fr) return ord[i].se;
    return ord[0].se;
}

Query bst(vector<array<int, 6>>& pos) {
    pair<int, Query> mi = {1e9, Query()};
    for (auto u : allQueries) {
        vector<int> amnt(7);
        for (auto p : pos) amnt[ans(p, u)]++;
        int mic = *max_element(amnt.begin(), amnt.end());
        mi = min(mi, {mic, u});
    }
    return mi.se;
}

vector<array<int, 6>> re(int result, Query& q, vector<array<int, 6>>& pos) {
    vector<array<int, 6>> withval;
    for (auto u : pos) if (ans(u, q) == result) withval.push_back(u);
    return withval;
}

int askQuery(Query q) {
    if (q.t == 1) return getLightest(q.vals[0], q.vals[1], q.vals[2]);
    if (q.t == 2) return getHeaviest(q.vals[0], q.vals[1], q.vals[2]);
    if (q.t == 3) return getMedian(q.vals[0], q.vals[1], q.vals[2]);
    return getNextLightest(q.vals[0], q.vals[1], q.vals[2], q.d);
}

void orderCoins() {
    // all perms
    vector<array<int, 6>> pos;
    array<int, 6> perm;
    for (int i = 1; i <= 6; i++) perm[i - 1] = i;
    do {
        pos.push_back(perm);
    } while (next_permutation(perm.begin(), perm.end()));
    // ok
    pos = re(askQuery(start), start, pos);
    while (((int) pos.size()) > 1) {
        Query q = bst(pos);
        pos = re(askQuery(q), q, pos);
    }
    perm = pos[0];
    int w[] = {0, 0, 0, 0, 0, 0};
    for (int i = 0; i < 6; i++) {
        int pomx = (min_element(perm.begin(), perm.end()) - perm.begin());
        w[i] = (pomx + 1);
        perm[pomx] = 1e9;
    }
    answer(w);
    return;
}

• Subtask 1: 73.2143 / 100