제출 #1159499

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1159499		Seb	저울 (IOI15_scales)	C++17	0 / 100	1095 ms	320 KiB

scales

#include "scales.h"
#include <bits/stdc++.h>

using namespace std;

struct query{
    int id, a, b, c, d, score;
    query(int id, int a, int b, int c, int d):
        id(id), a(a), b(b), c(c), d(d), score(0) {}
    query(): id(0), a(0), b(0), c(0), d(0), score(0) {}
};

struct caso{
    array<int, 6> ar; int val;
    caso(): val(0) {
        for (int i = 0; i < 6; i++)
            ar[i] = 0;
    }
};

vector<caso> posi;
caso aux = caso();
int vis[7], cnt;

vector<query> ans;

void genera(int idx = 0) {
    if (idx == 6) {
        posi.push_back(aux);
        return;
    }

    for (int i = 1; i <= 6; i++)
    if (!vis[i]) {
        aux.ar[idx] = i;
        vis[i] = 1;
        genera(idx + 1);
        vis[i] = 0;
    }
    return;
}

void init(int T) {
    for (int i =     1; i <= 6; i++)
    for (int j = i + 1; j <= 6; j++)
    for (int k = j + 1; k <= 6; k++) {
        ans.push_back(query(0, i, j, k, 0));
        ans.push_back(query(1, i, j, k, 0));
        ans.push_back(query(2, i, j, k, 0));

        for (int x = 1; x <= 6; x++) {
            if (x == i || x == j || x == k) continue;
            ans.push_back(query(3, i, j, k, x));
        }
    }

    genera();
    return;
}

int calc(query A) {
    int caso_resp, ansA = 0, ansB = 0, ansC = 0;

    if (A.id == 0) {
        for (int i = 0; i < posi.size(); i++) {
            if (!posi[i].val) continue;
            caso_resp = 0;
            for (int j = 0; j < 6; j++)
                if (posi[i].ar[j] == A.a || posi[i].ar[j] == A.b || posi[i].ar[j] == A.c)
                    caso_resp = posi[i].ar[j];
            if (caso_resp != ansA) ansA++;
            if (caso_resp != ansB) ansB++;
            if (caso_resp != ansC) ansC++;
        }
        return min({ansA, ansB, ansC});
    }

    if (A.id == 1) {
        for (int i = 0; i < posi.size(); i++) {
            if (!posi[i].val) continue;
            caso_resp = 0;
            for (int j = 0; j < 6; j++)
                if (posi[i].ar[j] == A.a || posi[i].ar[j] == A.b || posi[i].ar[j] == A.c) {
                    if (!caso_resp) caso_resp = posi[i].ar[j];
                    else { caso_resp = posi[i].ar[j]; break; }
                }
            if (caso_resp != ansA) ansA++;
            if (caso_resp != ansB) ansB++;
            if (caso_resp != ansC) ansC++;
        }
        return min({ansA, ansB, ansC});
    }

    if (A.id == 2) {
        for (int i = 0; i < posi.size(); i++) {
            if (!posi[i].val) continue;
            caso_resp = 0;
            for (int j = 0; j < 6; j++)
                if (posi[i].ar[j] == A.a || posi[i].ar[j] == A.b || posi[i].ar[j] == A.c)
                    { caso_resp = posi[i].ar[j]; break; }
            if (caso_resp != ansA) ansA++;
            if (caso_resp != ansB) ansB++;
            if (caso_resp != ansC) ansC++;
        }
        return min({ansA, ansB, ansC});
    }

    if (A.id == 3) {
        for (int i = 0; i < posi.size(); i++) {
            if (!posi[i].val) continue;
            caso_resp = 0;
            for (int j = 0; j < 6; j++)
                if (posi[i].ar[j] == A.a || posi[i].ar[j] == A.b || posi[i].ar[j] == A.c || posi[i].ar[j] == A.d) {
                    if (posi[i].ar[j] == A.d) { caso_resp = posi[i].ar[j]; break; }
                    else caso_resp = posi[i].ar[j];
                }

            if (caso_resp == A.d) {
                for (int j = 0; j < 6; j++)
                    if (posi[i].ar[j] == A.a || posi[i].ar[j] == A.b || posi[i].ar[j] == A.c || posi[i].ar[j] == A.d) {
                        if (posi[i].ar[j] == A.d) { caso_resp = posi[i].ar[j]; break; }
                        else caso_resp = posi[i].ar[j];
                    }
            }

            if (caso_resp != ansA) ansA++;
            if (caso_resp != ansB) ansB++;
            if (caso_resp != ansC) ansC++;
        }
        return min({ansA, ansB, ansC});
    }

    return 0;
}

void ask(query A) {
    int resp, caso_resp;

    if (A.id == 0) {
        resp = getHeaviest(A.a, A.b, A.c);
        for (int i = 0; i < posi.size(); i++) {
            if (!posi[i].val) continue;
            caso_resp = 0;
            for (int j = 0; j < 6; j++)
                if (posi[i].ar[j] == A.a || posi[i].ar[j] == A.b || posi[i].ar[j] == A.c)
                    caso_resp = posi[i].ar[j];
            if (resp != caso_resp) posi[i].val = 0;
        }
        return;
    }

    if (A.id == 1) {
        resp = getMedian(A.a, A.b, A.c);
        for (int i = 0; i < posi.size(); i++) {
            if (!posi[i].val) continue;
            caso_resp = 0;
            for (int j = 0; j < 6; j++)
                if (posi[i].ar[j] == A.a || posi[i].ar[j] == A.b || posi[i].ar[j] == A.c) {
                    if (!caso_resp) caso_resp = posi[i].ar[j];
                    else { caso_resp = posi[i].ar[j]; break; }
                }
            if (resp != caso_resp) posi[i].val = 0;
        }
        return;
    }

    if (A.id == 2) {
        resp = getLightest(A.a, A.b, A.c);
        for (int i = 0; i < posi.size(); i++) {
            if (!posi[i].val) continue;
            caso_resp = 0;
            for (int j = 0; j < 6; j++)
                if (posi[i].ar[j] == A.a || posi[i].ar[j] == A.b || posi[i].ar[j] == A.c)
                    { caso_resp = posi[i].ar[j]; break; }
            if (resp != caso_resp) posi[i].val = 0;
        }
        return;
    }

    if (A.id == 3) {
        resp = getNextLightest(A.a, A.b, A.c, A.d);
        for (int i = 0; i < posi.size(); i++) {
            if (!posi[i].val) continue;
            caso_resp = 0;
            for (int j = 0; j < 6; j++)
                if (posi[i].ar[j] == A.a || posi[i].ar[j] == A.b || posi[i].ar[j] == A.c || posi[i].ar[j] == A.d) {
                    if (posi[i].ar[j] == A.d) { caso_resp = posi[i].ar[j]; break; }
                    else caso_resp = posi[i].ar[j];
                }

            if (caso_resp == A.d) {
                for (int j = 0; j < 6; j++)
                    if (posi[i].ar[j] == A.a || posi[i].ar[j] == A.b || posi[i].ar[j] == A.c || posi[i].ar[j] == A.d) {
                        if (posi[i].ar[j] == A.d) { caso_resp = posi[i].ar[j]; break; }
                        else caso_resp = posi[i].ar[j];
                    }
            }

            if (resp != caso_resp) posi[i].val = 0;
        }
        return;
    }

}

void orderCoins() {
    for (int i = 0; i < posi.size(); i++) posi[i].val = 1;

    do {
        query A = query();
        for (int i = 0; i < ans.size(); i++) {
            ans[i].score = calc(ans[i]);
            if (A.score <= ans[i].score) A = ans[i];
        }
        ask(A);

        cnt = 0;
        for (int i = 0; i < posi.size(); i++)
            if (posi[i].val) cnt++;

    } while (cnt > 1);

    // respuesta
    int arr[6];
    for (int i = 0; i < posi.size(); i++)
        if (posi[i].val) aux = posi[i];
    for (int i = 0; i < 6; i++) arr[i] = aux.ar[i];
    answer(arr);
}

• Subtask 1: 0 / 100