Submission #1076058

#	Time	Username	Problem	Language	Result	Execution time	Memory
1076058		Joshua_Andersson	Scales (IOI15_scales)	C++14	0 / 100	502 ms	600 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 DEB
    assert(a < b);
    assert(b < c);
#endif
    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 DEB
    assert(a < b);
    assert(b < c);
#endif
    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;
    
}


uniform_int_distribution<int> adist(0, 3);
uniform_int_distribution<int> ndist(0, 5);
mt19937 rng(10);
pair<int, vi> getmove(const vvi& possible)
{
    while (1) {
    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 };
        sort(all(s));
        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 };
        sort(all(s));
        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} };
    }
    }
}

void init(int T) {
    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();

    vi bestquery;
    int bestval = 10000;
    while (chrono::duration_cast<chrono::milliseconds>(chrono::high_resolution_clock::now() - start).count() < 500)
    {
        int v;
        vi q;
        tie(v, q) = getmove(possible);
        if (v<bestval)
        {
            bestval = v;
            bestquery = q;
        }
    }
    cout << "";
}

void orderCoins() {
    /* ... */

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


    int rounds = 0;
    while (sz(possible)>1)
    {
        vi bestquery;
        int bestval = 10000;
        rep(i, 100)
        {
            int v;
            vi q;
            tie(v, q) = getmove(possible);
            if (v < bestval)
            {
                bestval = v;
                bestquery = q;
            }
        }
        rounds++;
        if (bestquery[0] == 0)
        {
            vvi newp;
            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);
                }
            }
            possible = newp;
        }
        else if (bestquery[0] == 1)
        {
            vvi newp;
            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);
                }
            }
            possible = newp;
        }
        else assert(0);
    }

    cerr << "rounds: " << rounds << "\n";
    vi p = possible[0];
    int W[] = { p[0],
                p[1], 
                p[2], 
                p[3], 
                p[4], 
                p[5]};
    answer(W);
}

Compilation message (stderr)

scales.cpp: In function 'void init(int)':
scales.cpp:116:15: warning: unused parameter 'T' [-Wunused-parameter]
  116 | void init(int T) {
      |           ~~~~^
scales.cpp: In function 'int q1(const vi&, int, int, int)':
scales.cpp:34:1: warning: control reaches end of non-void function [-Wreturn-type]
   34 | }
      | ^
scales.cpp: In function 'int q2(const vi&, int, int, int)':
scales.cpp:45:1: warning: control reaches end of non-void function [-Wreturn-type]
   45 | }
      | ^

• Subtask 1: 0 / 100