#include <bits/stdc++.h>
#include "scales.h"
using namespace std;
int t;
vector<vector<int> > possiblePerms;
bool used[7];
void init(int T) {
t = T;
}
int vectorFind(vector<int> v, int a) {
for (int i = 0; i < v.size(); i++)
{
if (v[i] == a)
{
return i;
}
}
return -1;
}
void generatePerms(vector<int> v) {
if (v.size() == 6)
{
possiblePerms.push_back(v);
return;
}
for (int i = 1; i <= 6; i++)
{
if (!used[i])
{
used[i] = true;
v.push_back(i);
generatePerms(v);
v.pop_back();
used[i] = false;
}
}
}
int checkMin(int a, int b, int c) {
int aCount = 0;
int bCount = 0;
int cCount = 0;
for (auto i : possiblePerms)
{
if (vectorFind(i, a) < vectorFind(i, b) and vectorFind(i, a) < vectorFind(i, c))
{
aCount++;
}
else if (vectorFind(i, b) < vectorFind(i,c))
{
bCount++;
}
else
{
cCount++;
}
}
return max(aCount, max(bCount, cCount));
}
int checkMax(int a, int b, int c) {
int aCount = 0;
int bCount = 0;
int cCount = 0;
for (auto i : possiblePerms)
{
if (vectorFind(i, a) > vectorFind(i, b) and vectorFind(i, a) > vectorFind(i, c))
{
aCount++;
}
else if (vectorFind(i, b) > vectorFind(i,c))
{
bCount++;
}
else
{
cCount++;
}
}
return max(aCount, max(bCount, cCount));
}
int checkMed(int a, int b, int c) {
int aCount = 0;
int bCount = 0;
int cCount = 0;
for (auto i : possiblePerms)
{
if (vectorFind(i, b) < vectorFind(i, a) and vectorFind(i, a) < vectorFind(i, c))
{
aCount++;
}
else if (vectorFind(i, c) < vectorFind(i,a) and vectorFind(i, a) < vectorFind(i, b))
{
aCount++;
}
else if (vectorFind(i, c) < vectorFind(i,b) and vectorFind(i, b) < vectorFind(i, a))
{
bCount++;
}
else if (vectorFind(i, a) < vectorFind(i,b) and vectorFind(i, b) < vectorFind(i, c))
{
bCount++;
}
else
{
cCount++;
}
}
return max(aCount, max(bCount, cCount));
}
int checkOther(int a, int b, int c, int d) {
return 1000000009;
}
void optimalQuestion() {
int minAnswer = 1000000000;
int minType = -1;
int mina, minb, minc, mind;
for (int i = 1; i <= 6; i++)
{
for (int j = i+1; j <= 6; j++)
{
for (int k = j+1; k <= 6; k++)
{
int small = checkMin(i, j, k);
int large = checkMax(i, j, k);
int med = checkMed(i, j, k);
if (small < minAnswer)
{
minAnswer = small;
mina = i;
minb = j;
minc = k;
minType = 1;
}
if (large < minAnswer)
{
minAnswer = large;
mina = i;
minb = j;
minc = k;
minType = 3;
}
if (med < minAnswer)
{
minAnswer = med;
mina = i;
minb = j;
minc = k;
minType = 2;
}
for (int l = k+1; l <= 6; l++)
{
int ans;
ans = checkOther(i, j, k, l);
if (ans < minAnswer)
{
minAnswer = ans;
mina = i;
minb = j;
minc = k;
mind = l;
minType = 4;
}
ans = checkOther(i, j, l, k);
if (ans < minAnswer)
{
minAnswer = ans;
mina = i;
minb = j;
minc = l;
mind = k;
minType = 4;
}
ans = checkOther(i, k, l, j);
if (ans < minAnswer)
{
minAnswer = ans;
mina = i;
minb = k;
minc = l;
mind = j;
minType = 4;
}
ans = checkOther(j, k, l, i);
if (ans < minAnswer)
{
minAnswer = ans;
mina = j;
minb = k;
minc = l;
mind = i;
minType = 4;
}
}
}
}
}
//cout << possiblePerms.size() << " possiblities\n";
if (minType == 1)
{
int x = getLightest(mina, minb, minc);
vector<vector<int> > newPossiblePerms;
for (auto i : possiblePerms)
{
if (vectorFind(i, x) > vectorFind(i, mina))
{
continue;
}
if (vectorFind(i, x) > vectorFind(i, minb))
{
continue;
}
if (vectorFind(i, x) > vectorFind(i, minc))
{
continue;
}
newPossiblePerms.push_back(i);
}
possiblePerms = newPossiblePerms;
newPossiblePerms.clear();
}
if (minType == 3)
{
int x = getHeaviest(mina, minb, minc);
vector<vector<int> > newPossiblePerms;
for (auto i : possiblePerms)
{
if (vectorFind(i, x) < vectorFind(i, mina))
{
continue;
}
if (vectorFind(i, x) < vectorFind(i, minb))
{
continue;
}
if (vectorFind(i, x) < vectorFind(i, minc))
{
continue;
}
newPossiblePerms.push_back(i);
}
possiblePerms = newPossiblePerms;
newPossiblePerms.clear();
}
if (minType == 2)
{
int x = getMedian(mina, minb, minc);
vector<vector<int> > newPossiblePerms;
for (auto i : possiblePerms)
{
if (vectorFind(i, minb) > vectorFind(i, x) and vectorFind(i, x) > vectorFind(i, mina))
{
newPossiblePerms.push_back(i);
}
if (vectorFind(i, mina) > vectorFind(i, x) and vectorFind(i, x) > vectorFind(i, minb))
{
newPossiblePerms.push_back(i);
}
if (vectorFind(i, minb) > vectorFind(i, x) and vectorFind(i, x) > vectorFind(i, minc))
{
newPossiblePerms.push_back(i);
}
if (vectorFind(i, minc) > vectorFind(i, x) and vectorFind(i, x) > vectorFind(i, minb))
{
newPossiblePerms.push_back(i);
}
if (vectorFind(i, mina) > vectorFind(i, x) and vectorFind(i, x) > vectorFind(i, minc))
{
newPossiblePerms.push_back(i);
}
if (vectorFind(i, minc) > vectorFind(i, x) and vectorFind(i, x) > vectorFind(i, mina))
{
newPossiblePerms.push_back(i);
}
}
possiblePerms = newPossiblePerms;
newPossiblePerms.clear();
}
return;
}
void orderCoins() {
possiblePerms.clear();
generatePerms({});
int x = getLightest(1, 2, 3);
vector<vector<int> > newPossiblePerms;
// cout << possiblePerms.size() << " possiblities\n";
for (auto i : possiblePerms)
{
if (vectorFind(i, x) > vectorFind(i, 1))
{
continue;
}
if (vectorFind(i, x) > vectorFind(i, 2))
{
continue;
}
if (vectorFind(i, x) > vectorFind(i, 3))
{
continue;
}
newPossiblePerms.push_back(i);
}
possiblePerms = newPossiblePerms;
newPossiblePerms.clear();
// cout << possiblePerms.size() << " possiblities\n";
x = getLightest(4, 5, 6);
for (auto i : possiblePerms)
{
if (vectorFind(i, x) > vectorFind(i, 4))
{
continue;
}
if (vectorFind(i, x) > vectorFind(i, 5))
{
continue;
}
if (vectorFind(i, x) > vectorFind(i, 6))
{
continue;
}
newPossiblePerms.push_back(i);
}
possiblePerms = newPossiblePerms;
newPossiblePerms.clear();
while (possiblePerms.size() > 1)
{
optimalQuestion();
}
int finalAnswer[6];
for (int i = 0; i < 6; i++)
{
finalAnswer[i] = possiblePerms[0][i];
}
answer(finalAnswer);
return;
}
Compilation message
scales.cpp: In function 'int vectorFind(std::vector<int>, int)':
scales.cpp:14:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
14 | for (int i = 0; i < v.size(); i++)
| ~~^~~~~~~~~~
scales.cpp: In function 'int checkOther(int, int, int, int)':
scales.cpp:117:20: warning: unused parameter 'a' [-Wunused-parameter]
117 | int checkOther(int a, int b, int c, int d) {
| ~~~~^
scales.cpp:117:27: warning: unused parameter 'b' [-Wunused-parameter]
117 | int checkOther(int a, int b, int c, int d) {
| ~~~~^
scales.cpp:117:34: warning: unused parameter 'c' [-Wunused-parameter]
117 | int checkOther(int a, int b, int c, int d) {
| ~~~~^
scales.cpp:117:41: warning: unused parameter 'd' [-Wunused-parameter]
117 | int checkOther(int a, int b, int c, int d) {
| ~~~~^
scales.cpp: In function 'void optimalQuestion()':
scales.cpp:124:27: warning: variable 'mind' set but not used [-Wunused-but-set-variable]
124 | int mina, minb, minc, mind;
| ^~~~
scales.cpp:16:9: warning: 'minc' may be used uninitialized in this function [-Wmaybe-uninitialized]
16 | if (v[i] == a)
| ^~
scales.cpp:124:21: note: 'minc' was declared here
124 | int mina, minb, minc, mind;
| ^~~~
scales.cpp:16:9: warning: 'minb' may be used uninitialized in this function [-Wmaybe-uninitialized]
16 | if (v[i] == a)
| ^~
scales.cpp:124:15: note: 'minb' was declared here
124 | int mina, minb, minc, mind;
| ^~~~
scales.cpp:16:9: warning: 'mina' may be used uninitialized in this function [-Wmaybe-uninitialized]
16 | if (v[i] == a)
| ^~
scales.cpp:124:9: note: 'mina' was declared here
124 | int mina, minb, minc, mind;
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Partially correct |
51 ms |
384 KB |
Output is partially correct |
| 2 |
Partially correct |
51 ms |
384 KB |
Output is partially correct |
| 3 |
Partially correct |
50 ms |
384 KB |
Output is partially correct |
| 4 |
Partially correct |
50 ms |
384 KB |
Output is partially correct |
| 5 |
Partially correct |
50 ms |
384 KB |
Output is partially correct |
| 6 |
Partially correct |
50 ms |
384 KB |
Output is partially correct |
| 7 |
Partially correct |
51 ms |
424 KB |
Output is partially correct |
| 8 |
Partially correct |
50 ms |
384 KB |
Output is partially correct |
| 9 |
Partially correct |
51 ms |
424 KB |
Output is partially correct |
| 10 |
Partially correct |
50 ms |
384 KB |
Output is partially correct |
| 11 |
Partially correct |
52 ms |
384 KB |
Output is partially correct |
| 12 |
Partially correct |
50 ms |
384 KB |
Output is partially correct |
| 13 |
Partially correct |
53 ms |
504 KB |
Output is partially correct |
| 14 |
Partially correct |
51 ms |
384 KB |
Output is partially correct |
| 15 |
Partially correct |
50 ms |
384 KB |
Output is partially correct |
| 16 |
Partially correct |
50 ms |
428 KB |
Output is partially correct |
| 17 |
Partially correct |
50 ms |
384 KB |
Output is partially correct |
| 18 |
Partially correct |
50 ms |
504 KB |
Output is partially correct |
| 19 |
Partially correct |
51 ms |
384 KB |
Output is partially correct |
| 20 |
Partially correct |
50 ms |
384 KB |
Output is partially correct |
| 21 |
Partially correct |
50 ms |
384 KB |
Output is partially correct |
| 22 |
Partially correct |
51 ms |
384 KB |
Output is partially correct |
| 23 |
Partially correct |
50 ms |
384 KB |
Output is partially correct |
| 24 |
Partially correct |
53 ms |
416 KB |
Output is partially correct |
| 25 |
Partially correct |
50 ms |
384 KB |
Output is partially correct |
| 26 |
Partially correct |
50 ms |
384 KB |
Output is partially correct |
| 27 |
Partially correct |
50 ms |
384 KB |
Output is partially correct |
| 28 |
Partially correct |
50 ms |
420 KB |
Output is partially correct |
| 29 |
Partially correct |
51 ms |
384 KB |
Output is partially correct |
| 30 |
Partially correct |
53 ms |
384 KB |
Output is partially correct |
| 31 |
Partially correct |
54 ms |
384 KB |
Output is partially correct |
| 32 |
Partially correct |
51 ms |
384 KB |
Output is partially correct |
| 33 |
Partially correct |
50 ms |
384 KB |
Output is partially correct |
| 34 |
Partially correct |
50 ms |
384 KB |
Output is partially correct |
| 35 |
Partially correct |
50 ms |
384 KB |
Output is partially correct |
| 36 |
Partially correct |
50 ms |
384 KB |
Output is partially correct |
| 37 |
Partially correct |
50 ms |
384 KB |
Output is partially correct |
| 38 |
Partially correct |
50 ms |
384 KB |
Output is partially correct |
| 39 |
Partially correct |
52 ms |
512 KB |
Output is partially correct |
| 40 |
Partially correct |
50 ms |
384 KB |
Output is partially correct |
