Submission #1213004

#	Time	Username	Problem	Language	Result	Execution time	Memory
1213004		Lemser	Scales (IOI15_scales)	C++20	71.43 / 100	216 ms	520 KiB

scales

#include "scales.h"
#include <bits/stdc++.h>
using namespace std;
 
using ll = long long;
using ull = unsigned long long;
using lld = long double;
using ii = pair<int,int>;
using pll = pair<ll, ll>;
 
using vi = vector<int>;
using vll = vector<ll>;
using vii = vector<ii>;
using vpll = vector<pll>;
using vlld = vector<lld>;
 
#define all(x) x.begin(),x.end()
#define lsb(x) x&(-x)
#define gcd(a,b) __gcd(a,b)
#define sz(x) (int)x.size()
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define fls cout.flush()
 
#define fore(i, l, r) for (auto i = l; i < r; i++)
#define fo(i, n) fore (i, 0, n)
#define forex(i, r, l) for (auto i = r-1; i >= l; i--)
#define ffo(i, n) forex (i, n, 0)
 
bool cmin(ll &a, ll b) { if (b < a) { a=b; return 1; } return 0; }
bool cmax(ll &a, ll b) { if (b > a) { a=b; return 1; } return 0; }

const ll INF = 1e18;
vector<array<ll, 5>> queries;

void init(int T) {
    for (ll a = 1; a <= 6; a++) {
        for (ll b = a+1; b <= 6; b++) {
            for (ll c = b+1; c <= 6; c++) {
                queries.pb({0, a, b, c, -1});
                queries.pb({1, a, b, c, -1});
                queries.pb({2, a, b, c, -1});
                for (ll d  =1; d <= 6; d++) {
                    if (a == d || b == d || c == d) continue;
                    queries.pb({3, a, b, c, d});
                }
            }
        }
    }
}

void orderCoins() {
    vector<vll> pos;
    vll uax = {1, 2, 3, 4, 5, 6};
    do {
        pos.pb(uax);
    } while (next_permutation(all(uax)));
    while (pos.size() > 1) {
        // cout << pos.size() << '\n';
        auto q = queries[0];
        ll mn = INF;
        for (auto [op, a, b, c, d]: queries) {
            ll cnt[7]{};
            for (vll perm: pos) {
                vll p;
                ll idx = 0;
                fo (i, 6) {
                    if (perm[i] != a && perm[i] != b && perm[i] != c && perm[i] != d) continue;
                    if (perm[i] == d) idx = p.size();
                    p.pb(perm[i]);
                }
                if (op == 0) cnt[p[2]]++;
                else if (op == 1) cnt[p[1]]++;
                else if (op == 2) cnt[p[0]]++;
                else cnt[p[(idx+1)%4]]++;
            }
            ll x = max({cnt[a], cnt[b], cnt[c]});
            if (x < mn) {
                q = array<ll, 5>{op, a, b, c, d};
                mn = x;
            }
        }
        ll x;
        // if (q[0] == 0) {
        //     x = func(q[0], q[1], q[2], q[3], -1);
        // } else if (q[0] == 1) {
        //     x = func(q[0], q[1], q[2], q[3], -1);
            
        // } else if (q[0] == 2) {
        //     x = func(q[0], q[1], q[2], q[3], -1);
        // } else {
        //     x = func(q[0], q[1], q[2], q[3], q[4]);
        // }
        if (q[0] == 0) {
            x = getHeaviest(q[1], q[2], q[3]);
        } else if (q[0] == 1) {
            x = getMedian(q[1], q[2], q[3]);
            
        } else if (q[0] == 2) {
            x = getLightest(q[1], q[2], q[3]);
        } else {
            x = getNextLightest(q[1], q[2], q[3], q[4]);
        }
        vector<vll> npos;
        auto [op, a, b, c, d] = q;
        for (vll perm: pos) {
            vll p;
            ll idx = 0;
            fo (i, 6) {
                if (perm[i] != a && perm[i] != b && perm[i] != c && perm[i] != d) continue;
                if (perm[i] == d) idx = p.size();
                p.pb(perm[i]);
            }
            ll x2;
            if (op == 0) x2 = p[2];
            else if (op == 1) x2 = p[1];
            else if (op == 2) x2 = p[0];
            else x2 = p[(idx+1)%4];
            if (x == x2) npos.pb(perm);
        }
        pos = npos;
    }
    int ans[6], d = 0;
    for (ll i: pos[0]) ans[d++] = i;
    answer(ans);
}

• Subtask 1: 71.4286 / 100