제출 #550540

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
550540		elazarkoren	저울 (IOI15_scales)	C++17	71.43 / 100	1 ms	212 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);
}

vi Sort3(vi v) {
    int x = queryLight(v[0], v[1], v[2]);
    if (x == v[1]) swap(v[0], v[1]);
    else if (x == v[2]) swap(v[0], v[2]);
    x = queryMed(v[0], v[1], v[2]);
    if (x == v[0]) swap(v[1], v[0]);
    else if (x == v[2]) swap(v[1], v[2]);
    return v;
}

vi Sort4(vi v) {
    int x = queryLight(v[0], v[1], v[2]);
    if (x == v[1]) swap(v[0], v[1]);
    else if (x == v[2]) swap(v[0], v[2]);
    x = queryHeavy(v[1], v[2], v[3]);
    if (x == v[2]) swap(v[3], v[2]);
    else if (x == v[1]) {
        swap(v[1], v[2]);
        swap(v[3], v[2]);
    }
    x = queryMed(v[0], v[1], v[2]);
    vi ans;
    if (x == v[0]) {
        ans = {v[2], v[0], v[1], v[3]};
    } else if (x == v[1]) {
        ans = {v[0], v[1], v[2], v[3]};
    } else {
        ans = {v[0], v[2], v[1], v[3]};
    }
    return ans;
}

vi Sort5(vi v) {
    shuffle(all(v), rng);
    int x = v.back();
    v.pop_back();
    v = Sort4(v);
    int y = queryMed(v[0], v[1], x);
    vi ans;
    if (y == v[0]) {
        ans = {x, v[0], v[1], v[2], v[3]};
    } else if (y == x) {
        ans = {v[0], x, v[1], v[2], v[3]};
    } else {
        y = queryMed(v[2], v[3], x);
        if (y == v[2]) {
            ans = {v[0], v[1], x, v[2], v[3]};
        } else if (y == x) {
            ans = {v[0], v[1], v[2], x, v[3]};
        } else {
            ans = {v[0], v[1], v[2], v[3], x};
        }
    }
    return ans;
}

vi Solve(vi v, int x, int med, bool b) {
    vi ans;
    if (v.empty()) return {x};
    if (v.size() == 2) {
        int y = queryMed(v[0], v[1], x);
        if (y == x) {
            ans = {v[0], x, v[1]};
        } else if (y == v[0]) {
            ans = {x, v[0], v[1]};
        } else {
            ans = {v[0], v[1], x};
        }
    } else if (v.size() == 1) {
        int y = queryMed(v[0], x, med);
        if (y == x && b || y != x && !b) {
            ans = {x, v[0]};
        } else {
            ans = {v[0], x};
        }
    } else {
        int y = queryMed(v[0], v[1], x);
        if (v[0] == y) {
            ans = {x, v[0], v[1], v[2]};
        } else if (x == y) {
            ans = {v[0], x, v[1], v[2]};
        } else {
            vi t = Solve({v[2]}, x, med, b);
            ans = {v[0], v[1]};
            for (int z : t) ans.push_back(z);
        }
    }
    return ans;
}

vi Sort6() {
//    vi v = {1, 2, 3, 4, 5, 6};
    vi v1 = Sort3({1, 2, 3});
    int x = v1[1];
    vi v2 = Sort4({x, 4, 5, 6});
    vi l, r;
    bool b = false;
    for (int i = 0; i < 4; i++) {
        if (v2[i] == x) {
            b = true;
        } else if (!b) l.push_back(v2[i]);
        else r.push_back(v2[i]);
    }
    l = Solve(l, v1[0], x, 0);
    r = Solve(r, v1[2], x, 1);
    vi ans = l;
    ans.push_back(x);
    for (int y : r) ans.push_back(y);
//    shuffle(all(v), rng);
//    int x = v.back();
//    v.pop_back();
//    v = Sort5(v);
//    int y = queryNext(v[0], v[2], v[4], x);
//    vi ans;
//    if (y == v[2]) {
//        y = queryMed(v[0], v[1], x);
//        if (v[1] == y) {
//            ans = {v[0], v[1], x, v[2], v[3], v[4]};
//        } else {
//            ans = {v[0], x, v[1], v[2], v[3], v[4]};
//        }
//    } else if (y == v[4]) {
//        y = queryMed(v[2], v[3], x);
//        if (x == y) {
//            ans = {v[0], v[1], v[2], x, v[3], v[4]};
//        } else {
//            ans = {v[0], v[1], v[2], v[3], x, v[4]};
//        }
//    } else {
//        y = queryMed(v[0], v[4], x);
//        if (y == v[0]) {
//            ans = {x, v[0], v[1], v[2], v[3], v[4]};
//        } else if (y == v[4]) {
//            ans = {v[0], v[1], v[2], v[3], v[4], x};
//        }
//    }
    return ans;
}

void orderCoins() {
    int w[] = {1, 2, 3, 4, 5, 6};
//    shuffle(w, w + 6, rng);
    asksLight.clear();
    asksHeavy.clear();
    asksMed.clear();
    asksNext.clear();
    vi v = Sort6();
    for (int i = 0; i < 6; i++) {
        w[i] = v[i];
    }
    answer(w);
}

//1
//3 4 6 2 1 5

//1
//2 3 1 5 6 4

컴파일 시 표준 에러 (stderr) 메시지

scales.cpp: In function 'void init(int)':
scales.cpp:17:15: warning: unused parameter 'T' [-Wunused-parameter]
   17 | void init(int T) {
      |           ~~~~^
scales.cpp: In function 'vi Solve(vi, int, int, bool)':
scales.cpp:123:20: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
  123 |         if (y == x && b || y != x && !b) {
      |                    ^

• Subtask 1: 71.428571 / 100