Submission #1076095

#	Time	Username	Problem	Language	Result	Execution time	Memory
1076095		Joshua_Andersson	Scales (IOI15_scales)	C++14	71.73 / 100	269 ms	744 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;
}
int q3(const vi& items, int a, int b, int c)
{
#if DEB
    assert(a < b);
    assert(b < c);
#endif
    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;
}


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} };
    }
    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 };
        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 (q3(p, a, b, c) == s[resp])
                {
                    newsz++;
                }
            }
            tot = max(tot, newsz);
        }
        return { tot,{2,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)
    rep(i, 10)
    {
        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()));

    vvi newp;
    int resp = getHeaviest(1, 2, 6) - 1;
    repe(p, possible)
    {
        if (q1(p, 0, 1, 5) == resp)
        {
            newp.push_back(p);
        }
    }
    possible = newp;

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

    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:167:10: warning: variable 'start' set but not used [-Wunused-but-set-variable]
  167 |     auto start = chrono::high_resolution_clock::now();
      |          ^~~~~
scales.cpp:158:15: warning: unused parameter 'T' [-Wunused-parameter]
  158 | void init(int T) {
      |           ~~~~^
scales.cpp: In function 'void orderCoins()':
scales.cpp:225:17: warning: declaration of 'newp' shadows a previous local [-Wshadow]
  225 |             vvi newp;
      |                 ^~~~
scales.cpp:195:9: note: shadowed declaration is here
  195 |     vvi newp;
      |         ^~~~
scales.cpp:226:17: warning: declaration of 'resp' shadows a previous local [-Wshadow]
  226 |             int resp = getHeaviest(bestquery[1]+1, bestquery[2]+1, bestquery[3]+1)-1;
      |                 ^~~~
scales.cpp:196:9: note: shadowed declaration is here
  196 |     int resp = getHeaviest(1, 2, 6) - 1;
      |         ^~~~
scales.cpp:238:17: warning: declaration of 'newp' shadows a previous local [-Wshadow]
  238 |             vvi newp;
      |                 ^~~~
scales.cpp:195:9: note: shadowed declaration is here
  195 |     vvi newp;
      |         ^~~~
scales.cpp:239:17: warning: declaration of 'resp' shadows a previous local [-Wshadow]
  239 |             int resp = getLightest(bestquery[1] + 1, bestquery[2] + 1, bestquery[3] + 1) - 1;
      |                 ^~~~
scales.cpp:196:9: note: shadowed declaration is here
  196 |     int resp = getHeaviest(1, 2, 6) - 1;
      |         ^~~~
scales.cpp:251:17: warning: declaration of 'newp' shadows a previous local [-Wshadow]
  251 |             vvi newp;
      |                 ^~~~
scales.cpp:195:9: note: shadowed declaration is here
  195 |     vvi newp;
      |         ^~~~
scales.cpp:252:17: warning: declaration of 'resp' shadows a previous local [-Wshadow]
  252 |             int resp = getMedian(bestquery[1] + 1, bestquery[2] + 1, bestquery[3] + 1) - 1;
      |                 ^~~~
scales.cpp:196:9: note: shadowed declaration is here
  196 |     int resp = getHeaviest(1, 2, 6) - 1;
      |         ^~~~
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:44:1: warning: control reaches end of non-void function [-Wreturn-type]
   44 | }
      | ^

• Subtask 1: 71.72619 / 100