Submission #1159501

#	Time	Username	Problem	Language	Result	Execution time	Memory
1159501		Seb	Scales (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;
    query(int id, int a, int b, int c, int d):
        id(id), a(a), b(b), c(c), d(d) {}
    query(): id(0), a(0), b(0), c(0), d(0) {}
};

vector<array<int, 6>> posi, posi_save;
array<int, 6> aux;
int vis[7];

vector<query> ans;

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

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

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();
}

int Heaviest(array<int, 6> C, query A) {
    for (int i = 5; i >= 0; i--)
        if (C[i] == A.a || C[i] == A.b || C[i] == A.c) return C[i];
}

int Median(array<int, 6> C, query A) {
    bool flag = false;
    for (int i = 0; i < 6; i++) {
        if (flag) {
            if (C[i] == A.a || C[i] == A.b || C[i] == A.c)
                return C[i];
        }
        else if (C[i] == A.a || C[i] == A.b || C[i] == A.c) flag = true;
    }
}

int Lightest(array<int, 6> C, query A) {
    for (int i = 0; i < 6; i++)
        if (C[i] == A.a || C[i] == A.b || C[i] == A.c) return C[i];
}

int NextLightest(array<int, 6> C, query A) {
    bool flag = false;
    for (int i = 0; i < 12; i++) {
        if (flag) {
            if (C[i%6] == A.a || C[i%6] == A.b || C[i%6] == A.c)
                return C[i%6];
        }
        else if (C[i] == A.d) flag = true;
    }
}

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

    for (int i = 0; i < posi.size(); i++) {
        if (A.id == 0)      caso_resp = Heaviest(posi[i], A);
        else if (A.id == 1) caso_resp = Median(posi[i], A);
        else if (A.id == 2) caso_resp = Lightest(posi[i], A);
        else                caso_resp = NextLightest(posi[i], A);

        if (caso_resp != ansA) ansA++;
        if (caso_resp != ansB) ansB++;
        if (caso_resp != ansC) ansC++;
    }

    return min({ansA, ansB, ansC});
}

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

    for (int i = 0; i < posi.size(); i++) {
        if (A.id == 0) {
            caso_resp = Heaviest(posi[i], A);
            resp = getHeaviest(A.a, A.b, A.c);
        }
        else if (A.id == 1) {
            caso_resp = Median(posi[i], A);
            resp = getMedian(A.a, A.b, A.c);
        }
        else if (A.id == 2) {
            caso_resp = Lightest(posi[i], A);
            resp = getLightest(A.a, A.b, A.c);
        }
        else {
            caso_resp = NextLightest(posi[i], A);
            resp = getNextLightest(A.a, A.b, A.c, A.d);
        }

        if (caso_resp != resp) {
            swap(posi[i], posi[posi.size() - 1]);
            posi.pop_back();
            i--; continue;
        }
    }
}

void orderCoins() {
    posi = posi_save;

    while (posi.size() > 1) {
        query A = query(); int cnt = 0, cnt_aux;
        for (int i = 0; i < ans.size(); i++) {
            cnt_aux = calc(ans[i]);
            if (cnt <= cnt_aux) {
                A = ans[i];
                cnt = cnt_aux;
            }
        }
        ask(A);
    }

    // respuesta
    int arr[6];
    for (int i = 0; i < 6; i++) arr[i] = posi[0][i];
    answer(arr);
    posi.clear();
}

Compilation message (stderr)

scales.cpp: In function 'int Heaviest(std::array<int, 6>, query)':
scales.cpp:54:1: warning: control reaches end of non-void function [-Wreturn-type]
   54 | }
      | ^
scales.cpp: In function 'int Median(std::array<int, 6>, query)':
scales.cpp:65:1: warning: control reaches end of non-void function [-Wreturn-type]
   65 | }
      | ^
scales.cpp: In function 'int Lightest(std::array<int, 6>, query)':
scales.cpp:70:1: warning: control reaches end of non-void function [-Wreturn-type]
   70 | }
      | ^
scales.cpp: In function 'int NextLightest(std::array<int, 6>, query)':
scales.cpp:81:1: warning: control reaches end of non-void function [-Wreturn-type]
   81 | }
      | ^

• Subtask 1: 0 / 100