#include "scales.h"
#include <algorithm>
#include <iostream>
#include <set>
#include <string>
#include <vector>
using namespace std;
int getMedian(int A, int B, int C);
int getHeaviest(int A, int B, int C);
int getLightest(int A, int B, int C);
int getNextLightest(int A, int B, int C, int D);
void answer(int C[]);
const int k = 6;
struct question { int typ; vector<int> c; };
int ask(question q)
{
if (q.typ == 0) return getLightest(q.c[0] + 1, q.c[1] + 1, q.c[2] + 1) - 1;
if (q.typ == 1) return getMedian(q.c[0] + 1, q.c[1] + 1, q.c[2] + 1) - 1;
if (q.typ == 2) return getHeaviest(q.c[0] + 1, q.c[1] + 1, q.c[2] + 1) - 1;
return getNextLightest(q.c[0] + 1, q.c[1] + 1, q.c[2] + 1, q.c[3] + 1) - 1;
}
struct permutacia
{
vector<int> p;
int ans(const question &q)
{
if (q.typ == 3)
{
for (int i = 0; i < k; i++) if (p[i] == q.c.back())
for (int j = i + 1; j < k; j++) if (count(q.c.begin(), q.c.end(), p[j])) return p[j];
for (int j = 0; j < k; j++) if (count(q.c.begin(), q.c.end(), p[j])) return p[j];
}
vector<int> v;
int cnt = 0;
for (int j = 0; j < k; j++)
{
if (count(q.c.begin(), q.c.end(), p[j])) cnt++;
if (cnt == q.typ + 1) return p[j];
}
}
};
struct node
{
vector<permutacia> can;
int id; vector<int> sons;
node() { id = 0, sons.resize(6, -1); }
} tr[2000];
int cnt = 1;
vector<question> v; // 75 otazok
void fill(int vr)
{
if (tr[vr].can.size() == 1) return;
else if (tr[vr].can.size() == 720) tr[vr].id = 0; // opytame sa na najlahsi z prvych troch
else if (tr[vr].can.size() == 120) tr[vr].id = 116; // opytame sa na najtazsi z poslednych troch
else
{
int best = tr[vr].can.size();
for (int q = 0; q < v.size(); q++)
{
vector<int> num(k, 0);
for (permutacia& i : tr[vr].can) num[i.ans(v[q])]++;
int maxi = *max_element(num.begin(), num.end());
if (maxi < best) best = maxi, tr[vr].id = q;
if (best == (tr[vr].can.size() + 2) / 3) break;
}
}
vector<vector<permutacia> > syn(k);
for (permutacia& i : tr[vr].can) syn[i.ans(v[tr[vr].id])].push_back(i);
for (int i = 0; i < k; i++) if (syn[i].size())
{
tr[cnt].can = syn[i], tr[vr].sons[i] = cnt;
fill(cnt++);
}
}
void init(int T)
{
permutacia p;
for (int i = 0; i < k; i++) p.p.push_back(i);
tr[0].can.push_back(p);
while (next_permutation(p.p.begin(), p.p.end())) tr[0].can.push_back(p);
for (int a = 0; a < k; a++) for (int b = a + 1; b < k; b++) for (int c = b + 1; c < k; c++)
{
for (int typ = 0; typ < 3; typ++) v.push_back({ typ, {a, b, c} });
for (int d = 0; d < k; d++) if (a != d && b != d && c != d) v.push_back({ 3, {a, b, c, d} });
}
fill(0);
}
int ans[k];
void orderCoins()
{
int vr = 0;
while (tr[vr].can.size() > 1)
{
vr = tr[vr].sons[ask(v[tr[vr].id])];
}
for (int i = 0; i < k; i++) ans[i] = tr[vr].can[0].p[i] + 1;
answer(ans);
}
Compilation message
scales.cpp: In function 'void fill(int)':
scales.cpp:58:29: warning: conversion from 'std::vector<permutacia>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
58 | int best = tr[vr].can.size();
| ~~~~~~~~~~~~~~~^~
scales.cpp:59:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<question>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
59 | for (int q = 0; q < v.size(); q++)
| ~~^~~~~~~~~~
scales.cpp:65:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<permutacia>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
65 | if (best == (tr[vr].can.size() + 2) / 3) break;
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
scales.cpp: In function 'void init(int)':
scales.cpp:76:15: warning: unused parameter 'T' [-Wunused-parameter]
76 | void init(int T)
| ~~~~^
scales.cpp: In member function 'int permutacia::ans(const question&)':
scales.cpp:34:15: warning: control reaches end of non-void function [-Wreturn-type]
34 | vector<int> v;
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Partially correct |
5 ms |
724 KB |
Output is partially correct |
| 2 |
Partially correct |
4 ms |
724 KB |
Output is partially correct |
| 3 |
Partially correct |
5 ms |
724 KB |
Output is partially correct |
| 4 |
Partially correct |
5 ms |
724 KB |
Output is partially correct |
| 5 |
Partially correct |
5 ms |
728 KB |
Output is partially correct |
| 6 |
Partially correct |
5 ms |
724 KB |
Output is partially correct |
| 7 |
Partially correct |
5 ms |
724 KB |
Output is partially correct |
| 8 |
Partially correct |
4 ms |
724 KB |
Output is partially correct |
| 9 |
Partially correct |
5 ms |
724 KB |
Output is partially correct |
| 10 |
Partially correct |
5 ms |
724 KB |
Output is partially correct |
| 11 |
Partially correct |
5 ms |
724 KB |
Output is partially correct |
| 12 |
Partially correct |
5 ms |
724 KB |
Output is partially correct |
| 13 |
Partially correct |
5 ms |
732 KB |
Output is partially correct |
| 14 |
Partially correct |
5 ms |
852 KB |
Output is partially correct |
| 15 |
Partially correct |
5 ms |
852 KB |
Output is partially correct |
| 16 |
Partially correct |
6 ms |
736 KB |
Output is partially correct |
| 17 |
Correct |
5 ms |
724 KB |
Output is correct |
| 18 |
Partially correct |
5 ms |
732 KB |
Output is partially correct |
| 19 |
Partially correct |
5 ms |
852 KB |
Output is partially correct |
| 20 |
Partially correct |
5 ms |
852 KB |
Output is partially correct |
| 21 |
Partially correct |
5 ms |
724 KB |
Output is partially correct |
| 22 |
Partially correct |
5 ms |
852 KB |
Output is partially correct |
| 23 |
Partially correct |
5 ms |
724 KB |
Output is partially correct |
| 24 |
Correct |
5 ms |
732 KB |
Output is correct |
| 25 |
Partially correct |
5 ms |
736 KB |
Output is partially correct |
| 26 |
Partially correct |
4 ms |
724 KB |
Output is partially correct |
| 27 |
Partially correct |
5 ms |
724 KB |
Output is partially correct |
| 28 |
Partially correct |
5 ms |
728 KB |
Output is partially correct |
| 29 |
Partially correct |
5 ms |
724 KB |
Output is partially correct |
| 30 |
Partially correct |
5 ms |
820 KB |
Output is partially correct |
| 31 |
Partially correct |
5 ms |
724 KB |
Output is partially correct |
| 32 |
Partially correct |
5 ms |
852 KB |
Output is partially correct |
| 33 |
Partially correct |
5 ms |
852 KB |
Output is partially correct |
| 34 |
Partially correct |
5 ms |
724 KB |
Output is partially correct |
| 35 |
Partially correct |
5 ms |
724 KB |
Output is partially correct |
| 36 |
Partially correct |
5 ms |
728 KB |
Output is partially correct |
| 37 |
Partially correct |
5 ms |
852 KB |
Output is partially correct |
| 38 |
Partially correct |
5 ms |
732 KB |
Output is partially correct |
| 39 |
Partially correct |
5 ms |
852 KB |
Output is partially correct |
| 40 |
Partially correct |
5 ms |
852 KB |
Output is partially correct |
