Submission #1076194

#	Time	Username	Problem	Language	Result	Execution time	Memory
1076194		Joshua_Andersson	Scales (IOI15_scales)	C++14	71.43 / 100	689 ms	504 KiB

scales

#include "scales.h"

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const ll linf = ll(1e18);

typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> p2;

#define rep(i, high) for (int i = 0; i < high; i++)
#define repp(i, low, high) for (int i = low; i < high; i++)
#define repe(i, container) for (auto& i : container)
#define sz(container) ((int)container.size())
#define all(x) begin(x),end(x)

#if _LOCAL
#define assert(x) if (!(x)) __debugbreak()
#endif

#define DEB 1
int q1(const vi& items, int a, int b, int c)
{
    if (items[a] > items[b] && items[a] > items[c]) return a;
    if (items[b] > items[a] && items[b] > items[c]) return b;
    if (items[c] > items[b] && items[c] > items[a]) return c;
    
}
int q2(const vi& items, int a, int b, int c)
{
    if (items[a] < items[b] && items[a] < items[c]) return a;
    if (items[b] < items[a] && items[b] < items[c]) return b;
    if (items[c] < items[b] && items[c] < items[a]) return c;
}
int q3(const vi& items, int a, int b, int c)
{
    vector<p2> v;
    v.emplace_back(items[a], a);
    v.emplace_back(items[b], b);
    v.emplace_back(items[c], c);
    sort(all(v));
    return v[1].second;
}
int q4(const vi& items, int a, int b, int c, int d)
{
    vector<p2> heavier;
    if (items[a] > items[d]) heavier.emplace_back(items[a], a);
    if (items[b] > items[d]) heavier.emplace_back(items[b], b);
    if (items[c] > items[d]) heavier.emplace_back(items[c], c);
    if (sz(heavier))
    {
        sort(all(heavier));
        return heavier[0].second;
    }
    else
    {
        return q2(items, a, b, c);
    }
}

uniform_int_distribution<int> adist(0, 3);
uniform_int_distribution<int> ndist(0, 5);
mt19937 rng(rand());
pair<int, vi> getmove(const vvi& possible)
{
    int move = adist(rng);
    if (move == 0)
    {
        int a, b, c;
        a = ndist(rng);
        b = ndist(rng);
        while (b == a) b = ndist(rng);
        c = ndist(rng);
        while (c == b || c == a) c = ndist(rng);
        vi s = { a,b,c };
        a = s[0];
        b = s[1];
        c = s[2];

        int tot = 0;
        rep(resp, 3)
        {
            int newsz = 0;
            repe(p, possible)
            {
                if (q1(p, a, b, c) == s[resp])
                {
                    newsz++;
                }
            }
            tot = max(tot, newsz);
        }
        return { tot,{0,a,b,c} };
    }
    if (move == 1)
    {
        int a, b, c;
        a = ndist(rng);
        b = ndist(rng);
        while (b == a) b = ndist(rng);
        c = ndist(rng);
        while (c == b || c == a) c = ndist(rng);
        vi s = { a,b,c };
        a = s[0];
        b = s[1];
        c = s[2];

        int tot = 0;
        rep(resp, 3)
        {
            int newsz = 0;
            repe(p, possible)
            {
                if (q2(p, a, b, c) == s[resp])
                {
                    newsz++;
                }
            }
            tot = max(tot, newsz);
        }
        return { tot,{1,a,b,c} };
    }
    if (move == 2)
    {
        int a, b, c;
        a = ndist(rng);
        b = ndist(rng);
        while (b == a) b = ndist(rng);
        c = ndist(rng);
        while (c == b || c == a) c = ndist(rng);
        vi s = { a,b,c };
        a = s[0];
        b = s[1];
        c = s[2];

        int tot = 0;
        rep(resp, 3)
        {
            int newsz = 0;
            repe(p, possible)
            {
                if (q3(p, a, b, c) == s[resp])
                {
                    newsz++;
                }
            }
            tot = max(tot, newsz);
        }
        return { tot,{2,a,b,c} };
    }
    else
    {
        int a, b, c, d;
        a = ndist(rng);
        b = ndist(rng);
        while (b == a) b = ndist(rng);
        c = ndist(rng);
        while (c == b || c == a) c = ndist(rng);
        d = ndist(rng);
        while (d == a || d == b || d == c) d = ndist(rng);
        vi s = { a,b,c, d };

        int tot = 0;
        rep(resp, 3)
        {
            int newsz = 0;
            repe(p, possible)
            {
                if (q4(p, a, b, c, d) == s[resp])
                {
                    newsz++;
                }
            }
            tot = max(tot, newsz);
        }
        return { tot,{3,a,b,c, d} };
    }
}

vvi filter(const vvi& possible, vi& bestquery)
{
    vvi newp;

    if (bestquery[0] == 0)
    {
        int resp = getHeaviest(bestquery[1] + 1, bestquery[2] + 1, bestquery[3] + 1) - 1;
        repe(p, possible)
        {
            if (q1(p, bestquery[1], bestquery[2], bestquery[3]) == resp)
            {
                newp.push_back(p);
            }
        }
    }
    else if (bestquery[0] == 1)
    {
        int resp = getLightest(bestquery[1] + 1, bestquery[2] + 1, bestquery[3] + 1) - 1;
        repe(p, possible)
        {
            if (q2(p, bestquery[1], bestquery[2], bestquery[3]) == resp)
            {
                newp.push_back(p);
            }
        }
    }
    else if (bestquery[0] == 2)
    {
        int resp = getMedian(bestquery[1] + 1, bestquery[2] + 1, bestquery[3] + 1) - 1;
        repe(p, possible)
        {
            if (q3(p, bestquery[1], bestquery[2], bestquery[3]) == resp)
            {
                newp.push_back(p);
            }
        }
    }
    else if (bestquery[0] == 3)
    {
        int resp = getNextLightest(bestquery[1] + 1, bestquery[2] + 1, bestquery[3] + 1, bestquery[4] + 1) - 1;
        repe(p, possible)
        {
            if (q4(p, bestquery[1], bestquery[2], bestquery[3], bestquery[4]) == resp)
            {
                newp.push_back(p);
            }
        }
    }
    else assert(0);
    return newp;
}

vvi fakefilter(const vvi& possible, vi& bestquery)
{
    vvi newp;


    rep(resp, 3)
    {
        vvi res;
        repe(p, possible)
        {
            int v;
            if (bestquery[0] == 0) v = q1(p, bestquery[1], bestquery[2], bestquery[3]);
            if (bestquery[0] == 1) v = q2(p, bestquery[1], bestquery[2], bestquery[3]);
            if (bestquery[0] == 2) v = q3(p, bestquery[1], bestquery[2], bestquery[3]);
            if (bestquery[0] == 3) v = q4(p, bestquery[1], bestquery[2], bestquery[3], bestquery[4]);
            if (v == bestquery[resp+1])
            {
                res.push_back(p);
            }
        }
        if (sz(res) > sz(newp)) newp = res;
    }
    

    return newp;
}

void init(int T) {
    return;
#if !_LOCAL
#endif
    vvi possible;
    vi order = { 1,2,3,4,5,6 };
    do
    {
        possible.push_back(order);
    } while (next_permutation(order.begin(),order.end()));


    auto start = chrono::high_resolution_clock::now();

    vvi bestquery;
    int bestval = 10000;
    //while (chrono::duration_cast<chrono::milliseconds>(chrono::high_resolution_clock::now() - start).count() < 500)
    rep(i, 1000000)
    {
        int _;
        vi q1, q2, q3, q4, q5, q6;
        //tie(_, q1) = getmove(possible);
        q1 = { 1,0,2,4 };
        //tie(_, q2) = getmove(possible);
        q2 = { 3,1,0,3,4 };
        //tie(_, q3) = getmove(possible);
        q3 = { 3,1,2,0,5 };
        tie(_, q4) = getmove(possible);
        tie(_, q5) = getmove(possible);
        tie(_, q6) = getmove(possible);
        vvi res = fakefilter(possible, q1);
        res = fakefilter(res, q2);
        res = fakefilter(res, q3);
        res = fakefilter(res, q4);
        res = fakefilter(res, q5);
        res = fakefilter(res, q6);
        if (sz(res)<bestval)
        {
            assert(sz(res));
            bestval = sz(res);
            if (bestval==1)
            {
                break;
            }
            bestquery = { q1,q2, q3, q4, q5, q6 };
        }
    }
    cout << bestval << "\n";
    repe(q, bestquery)
    {
        repe(v, q) cout << v << " ";
        cout << "\n";
    }
}



void orderCoins() {

    vvi possible;
    vi order = { 1,2,3,4,5,6 };
    do
    {
        possible.push_back(order);
    } while (next_permutation(order.begin(), order.end()));


    vvi queries = {{ 1,0,2,4 },
    //tie(_, q2) = getmove(possible);
    { 3,1,0,3,4 },
    //tie(_, q3) = getmove(possible);
    { 3,1,2,0,5 }};
    repe(q, queries) possible = filter(possible, q);

    int rounds = 3;
    while (sz(possible)>1)
    {
        vi bestquery;
        int bestval = 10000;
        rep(i, 8100)
        {
            int v;
            vi q;
            tie(v, q) = getmove(possible);
            if (v < bestval)
            {
                bestval = v;
                bestquery = q;
            }
        }
        rounds++;
        possible = filter(possible, bestquery);
    }

    cerr << "rounds: " << rounds << "\n";
    vi p = possible[0];
    int W[] = { 0,
                0, 
                0, 
                0, 
                0, 
                0};
    rep(i, 6) W[p[i]-1] = i + 1;
    answer(W);
}

Compilation message (stderr)

scales.cpp: In function 'void init(int)':
scales.cpp:273:10: warning: variable 'start' set but not used [-Wunused-but-set-variable]
  273 |     auto start = chrono::high_resolution_clock::now();
      |          ^~~~~
scales.cpp:261:15: warning: unused parameter 'T' [-Wunused-parameter]
  261 | void init(int T) {
      |           ~~~~^
scales.cpp: In function 'int q1(const vi&, int, int, int)':
scales.cpp:30:1: warning: control reaches end of non-void function [-Wreturn-type]
   30 | }
      | ^
scales.cpp: In function 'int q2(const vi&, int, int, int)':
scales.cpp:36:1: warning: control reaches end of non-void function [-Wreturn-type]
   36 | }
      | ^
scales.cpp: In function 'vvi fakefilter(const vvi&, vi&)':
scales.cpp:249:13: warning: 'v' may be used uninitialized in this function [-Wmaybe-uninitialized]
  249 |             if (v == bestquery[resp+1])
      |             ^~

• Subtask 1: 71.428571 / 100