Submission #793243

#	Time	Username	Problem	Language	Result	Execution time	Memory
793243		PixelCat	Scales (IOI15_scales)	C++14	71.43 / 100	24 ms	360 KiB

scales

#ifdef NYAOWO
#include "grader.cpp"
#endif

#include "scales.h"

#include <bits/stdc++.h>
#define For(i, a, b) for(int i = a; i <= b; i++)
#define Forr(i, a, b) for(int i = a; i >= b; i--)
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define sz(x) ((int)x.size())
#define eb emplace_back
using namespace std;
using LL = long long;
using pii = pair<int, int>;

int W[] = {1, 2, 3, 4, 5, 6};
mt19937_64 rng(48763);

// 0 for lightest, 1 for median, 2 for heaviest
vector<vector<int>> options;
vector<vector<int>> alive;

void init(int T) {
    assert(T < 20);
    For(i, 0, 5) For(j, i + 1, 5) For(k, j + 1, 5) {
        options.push_back({0, i, j, k});
        options.push_back({1, i, j, k});
        options.push_back({2, i, j, k});
    }
}

bool match(const vector<int> &ord, const vector<int> &opt, int res) {
    if(opt[0] == 0) {
        bool ok = true;
        For(i, 1, 3) ok = ok && (ord[opt[i]] >= ord[opt[res]]);
        return ok;
    }
    if(opt[0] == 2) {
        bool ok = true;
        For(i, 1, 3) ok = ok && (ord[opt[i]] <= ord[opt[res]]);
        return ok;
    }
    if(opt[0] == 1) {
        int owo = 0;
        For(i, 1, 3) {
            int dif = (ord[opt[i]] - ord[opt[res]]);
            if(dif < 0)  owo |= 1;
            if(dif == 0) owo |= 2;
            if(dif > 0)  owo |= 4;
        }
        return owo == 7;
    }
    return false;
}

// how many possibilities remain at most?
int worstmatch(const vector<vector<int>> &ords, const vector<int> &opt) {
    int mx = 0;
    For(res, 1, 3) {
        int cnt = 0;
        for(auto &ord:ords) {
            if(match(ord, opt, res)) {
                cnt++;
            }
        }
        mx = max(mx, cnt);
    }
    return mx;
}

int best_opt(const vector<vector<int>> &ords) {
    int mx = 1000, idx = -1;
    For(i, 0, sz(options) - 1) {
        int k = worstmatch(ords, options[i]);
        if(k < mx) {
            mx = k; idx = i;
        }
    }
    // cout << idx << " " << mx << "\n" << flush;
    return idx;
}

int make_query(const vector<int> &opt) {
    int x = -1;
    if(opt[0] == 0) {
        x = getLightest(opt[1] + 1, opt[2] + 1, opt[3] + 1);
    } else if(opt[0] == 1) {
        x = getMedian(opt[1] + 1, opt[2] + 1, opt[3] + 1);
    } else if(opt[0] == 2) {
        x = getHeaviest(opt[1] + 1, opt[2] + 1, opt[3] + 1);
    }
    For(i, 1, 3) if(x == opt[i] + 1) return i;
    assert(false);
    return -1;
}

void remove_impossible(vector<vector<int>> &ords, const vector<int> &opt, int res) {
    int ptr = 0;
    while(ptr < sz(ords)) {
        if(match(ords[ptr], opt, res)) {
            ptr++;
        } else {
            swap(ords[ptr], ords[sz(ords) - 1]);
            ords.pop_back();
        }
    }
}

void orderCoins() {
    alive.clear();
    int a[6] = {0, 1, 2, 3, 4, 5};
    alive.clear();
    do {
        alive.eb(a, a + 6);
    } while(next_permutation(a, a + 6));

    while(sz(alive) > 1) {
        int k = best_opt(alive);
        int r = make_query(options[k]);
        remove_impossible(alive, options[k], r);
        // cout << sz(alive) << " " << k << " " << r << "\n" << flush;
    }
    
    vector<int> &ord = alive[0];
    For(i, 0, 5) W[ord[i]] = i + 1;

    answer(W);
}

• Subtask 1: 71.428571 / 100