Submission #550423

#	Time	Username	Problem	Language	Result	Execution time	Memory
550423		elazarkoren	Scales (IOI15_scales)	C++17	29.41 / 100	1 ms	292 KiB

scales

#include <bits/stdc++.h>
#include "scales.h"
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define chkmin(a, b) a = min(a, b)
#define chkmax(a, b) a = max(a, b)
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pii;
typedef vector<pii> vii;

mt19937 rng(time(0));

void init(int T) {
}

map<vi, int> asksLight;
int queryLight(int a, int b, int c) {
    vi v = {a, b, c};
    sort(all(v));
    if (asksLight.count(v)) return asksLight[v];
    return asksLight[v] = getLightest(a, b, c);
}

map<vi, int> asksHeavy;
int queryHeavy(int a, int b, int c) {
    vi v = {a, b, c};
    sort(all(v));
    if (asksHeavy.count(v)) return asksHeavy[v];
    return asksHeavy[v] = getHeaviest(a, b, c);
}

map<vi, int> asksMed;
int queryMed(int a, int b, int c) {
    vi v = {a, b, c};
    sort(all(v));
    if (asksMed.count(v)) return asksMed[v];
    return asksMed[v] = getMedian(a, b, c);
}

map<vi, int> asksNext;
int queryNext(int a, int b, int c, int d) {
    vi v = {a, b, c};
    sort(all(v));
    v.push_back(d);
    if (asksNext.count(v)) return asksNext[v];
    return asksNext[v] = getNextLightest(a, b, c, d);
}

void Sort(int i, int j, int k, int *w) {
    int x = queryLight(w[i], w[j], w[k]);
    if (x == w[j]) swap(w[i], w[j]);
    else if (x == w[k]) swap(w[i], w[k]);
    x = queryMed(w[i], w[j], w[k]);
    if (x == w[i]) swap(w[i], w[j]);
    else if (x == w[k]) swap(w[i], w[k]);
}

void orderCoins() {
    int w[] = {1, 2, 3, 4, 5, 6};
    shuffle(w, w + 6, rng);
    asksLight.clear();
    asksHeavy.clear();
    asksMed.clear();
    asksNext.clear();
    Sort(0, 1, 2, w);
    Sort(3, 4, 5, w);
    while (true) {
        bool b = false;
        for (int i = 0; i < 4; i++) {
            int x = queryLight(w[i], w[i + 1], w[i + 2]);
            if (x != w[i]) {
                b = true;
            }
            for (int j = i + 1; j < i + 3; j++) {
                if (x == w[j]) {
                    swap(w[i], w[j]);
                    break;
                }
            }
        }
        if (!b) break;
    }
    int x = getMedian(w[3], w[4], w[5]);
    if (x != w[4]) swap(w[4], w[5]);
    answer(w);
}

//1
//3 4 6 2 1 5

Compilation message (stderr)

scales.cpp: In function 'void init(int)':
scales.cpp:17:15: warning: unused parameter 'T' [-Wunused-parameter]
   17 | void init(int T) {
      |           ~~~~^

• Subtask 1: 29.411765 / 100