Submission #1041262

#	Time	Username	Problem	Language	Result	Execution time	Memory
1041262		c2zi6	Scales (IOI15_scales)	C++14	100 / 100	172 ms	864 KiB

scales

#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
#define ff first
#define ss second
#define pb push_back
#define all(a) (a).begin(), (a).end()
#define replr(i, a, b) for (int i = int(a); i <= int(b); ++i)
#define reprl(i, a, b) for (int i = int(a); i >= int(b); --i)
#define rep(i, n) for (int i = 0; i < int(n); ++i)
#define mkp(a, b) make_pair(a, b)
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> PII;
typedef vector<int> VI;
typedef vector<PII> VPI;
typedef vector<VI> VVI;
typedef vector<VVI> VVVI;
typedef vector<VPI> VVPI;
typedef pair<ll, ll> PLL;
typedef vector<ll> VL;
typedef vector<PLL> VPL;
typedef vector<VL> VVL;
typedef vector<VVL> VVVL;
typedef vector<VPL> VVPL;
template<class T> T setmax(T& a, T b) {if (a < b) return a = b; return a;}
template<class T> T setmin(T& a, T b) {if (a < b) return a; return a = b;}
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template<typename T>
using indset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#include "scales.h"


const int NVAL = 6;

struct HARC {
    int type;
    /*
     * 1 - Lightest
     * 2 - Median
     * 3 - Heaviest
     * 4 - Next Lightest
     */
    int a, b, c, d;
    int ret;
};
vector<HARC> questions;

bool check(VI& vec, HARC h) {
    auto[type, a, b, c, d, ret] = h;
    VI ind(NVAL+1);
    rep(i, NVAL) ind[vec[i]] = i;
    if (ind[a] > ind[b]) swap(a, b);
    if (ind[b] > ind[c]) swap(b, c);
    if (ind[a] > ind[b]) swap(a, b);
    if (type == 1) {
        return ret == a;
    } else if (type == 2) {
        return ret == b;
    } else if (type == 3) {
        return ret == c;
    } else {
        if (ind[a] > ind[d]) return ret == a;
        if (ind[b] > ind[d]) return ret == b;
        if (ind[c] > ind[d]) return ret == c;
        return ret == a;
    }
}
void operator+=(VVI& a, HARC h) {
    VVI b;
    for (VI& vec : a) if (check(vec, h)) b.pb(vec);
    a = b;
}
VVI operator+(VVI& a, HARC h) {
    VVI b;
    for (VI& vec : a) if (check(vec, h)) b.pb(vec);
    return b;
}
int worstcase(VVI& cur, HARC h) {
    int worst = 0;
    for (int r : {h.a, h.b, h.c}) {
        h.ret = r;
        int nw = (cur + h).size();
        setmax(worst, nw);
    }
    return worst;
}
vector<HARC> possiblequestions(VVI& cur, int lim) {
    vector<HARC> ret;
    for (HARC h : questions) {
        if (worstcase(cur, h) <= lim) ret.pb(h);
    }
    return ret;
}
map<VVI, HARC> question;
map<VVI, VVVI> nextstates;
bool dfs(VVI cur, int lim = 243) {
    if (cur.size() <= 1) return true;
    for (HARC h : possiblequestions(cur, lim)) {
        bool good = true;
        for (int r : {h.a, h.b, h.c}) {
            h.ret = r;
            if (!dfs(cur + h, lim/3)) {
                good = false;
                break;
            }
        }
        if (good) {
            question[cur] = h;
            return true;
        }
    }
    return false;
}
VVI initial;
void init(int T) {
    replr(a, 1, NVAL) replr(b, a+1, NVAL) replr(c, b+1, NVAL) {
        questions.pb({1, a, b, c, -1, -1});
        questions.pb({2, a, b, c, -1, -1});
        questions.pb({3, a, b, c, -1, -1});
        replr(d, 1, NVAL) if (d != a && d != b && d != c) {
            questions.pb({4, a, b, c, d, -1});
        }
    }
    VI b;
    replr(i, 1, NVAL) b.pb(i);
    do {
        initial.pb(b);
    } while (next_permutation(all(b)));
    dfs(initial, 243);
}

void answer(VI ans);
void orderCoins() {
    /*range += {1, 1, 2, 3, -1, 1};*/
    /*range += {2, 4, 5, 6, -1, 4};*/

    VVI cur = initial;
    while (true) {
        if (cur.size() == 1) {
            answer(cur[0]);
            return;
        }
        /*for (VI vec : cur) {*/
        /*    for (int x : vec) cout << x << " ";*/
        /*    cout << endl;*/
        /*}*/
        HARC h = question[cur];
        if (h.type == 1) h.ret = getLightest(h.a, h.b, h.c);
        else if (h.type == 2) h.ret = getMedian(h.a, h.b, h.c);
        else if (h.type == 3) h.ret = getHeaviest(h.a, h.b, h.c);
        else h.ret = getNextLightest(h.a, h.b, h.c, h.d);
        cur += h;
    }
}











void answer(VI ans) {
    int w[6];
    rep(i, 6) w[i] = ans[i];
    answer(w);
}

Compilation message (stderr)

scales.cpp: In function 'bool check(VI&, HARC)':
scales.cpp:51:9: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   51 |     auto[type, a, b, c, d, ret] = h;
      |         ^
scales.cpp: In function 'int worstcase(VVI&, HARC)':
scales.cpp:84:32: warning: conversion from 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   84 |         int nw = (cur + h).size();
      |                  ~~~~~~~~~~~~~~^~
scales.cpp: In function 'void init(int)':
scales.cpp:117:15: warning: unused parameter 'T' [-Wunused-parameter]
  117 | void init(int T) {
      |           ~~~~^

• Subtask 1: 100 / 100