#include "scales.h"
#include <vector>
#include <algorithm>
#include <stdio.h>
typedef struct node node;
struct node
{
int q, a, b, c, d;
std::vector<int> V;
node* next[3];
};
node* root;
std::vector<int> Permu[720];
int compare(std::pair<int, int> a, std::pair<int, int> b)
{
return (a.first < b.first);
}
int answer(int P, int q, int a, int b, int c, int d)
{
// printf("answer P%d q%d a%d b%d c%d d%d\n", P, q, a, b, c, d);
int i;
// for (i = 0; i < 6; i++)
// printf("%d ", Permu[P][i]);
// printf("\n");
std::vector<std::pair<int, int> > W;
switch (q)
{
case 1:
W.push_back({Permu[P][a], 0});
W.push_back({Permu[P][b], 1});
W.push_back({Permu[P][c], 2});
std::sort(W.begin(), W.end(), compare);
// printf("%d\n", W[2].second);
return W[2].second;
case 2:
W.push_back({Permu[P][a], 0});
W.push_back({Permu[P][b], 1});
W.push_back({Permu[P][c], 2});
std::sort(W.begin(), W.end(), compare);
// printf("%d\n", W[0].second);
return W[0].second;
break;
case 3:
W.push_back({Permu[P][a], 0});
W.push_back({Permu[P][b], 1});
W.push_back({Permu[P][c], 2});
std::sort(W.begin(), W.end(), compare);
// printf("%d\n", W[1].second);
return W[1].second;
break;
case 4:
if (Permu[P][a] > Permu[P][d]) W.push_back({Permu[P][a], 0});
if (Permu[P][b] > Permu[P][d]) W.push_back({Permu[P][b], 1});
if (Permu[P][c] > Permu[P][d]) W.push_back({Permu[P][c], 2});
std::sort(W.begin(), W.end(), compare);
if (W.size())
{
// printf("%d\n", W[0].second);
return W[0].second;
}
else return answer(P, 2, a, b, c, d);
break;
}
}
int makeTree(node* p, int LIM)
{
// printf("makeTree %p %d %d\n", p, p->V.size(), LIM);
int i, j, k, l, m, v;
// for (i = 0; i < p->V.size(); i++)
// printf("%d ", p->V[i]);
// printf("\n");
if (p->V.size() <= 1)
return 1;
int ok = 0;
std::vector<int> Scratch[3];
for (i = 1; i <= 4; i++)
{
for (j = 0; j < 6; j++)
{
for (k = j + 1; k < 6; k++)
{
for (l = k + 1; l < 6; l++)
{
if (i == 4)
{
for (m = l + 1; m < 6; m++)
{
// printf("i%d j%d k%d l%d m%d\n", i, j, k, l, m);
Scratch[0].clear();
Scratch[1].clear();
Scratch[2].clear();
for (v = 0; v < p->V.size(); v++)
Scratch[answer(p->V[v], i, j, k, l, m)].push_back(p->V[v]);
for (v = 0; v < 3; v++)
if (Scratch[v].size()*3 > LIM)
break;
// printf("%d %d %d\n", Scratch[0].size(), Scratch[1].size(), Scratch[2].size());
if (v == 3)
{
p->q = i;
p->a = j;
p->b = k;
p->c = l;
p->d = m;
if (p->next[0] == NULL) p->next[0] = new node();
p->next[0]->V = Scratch[0];
if (p->next[1] == NULL) p->next[1] = new node();
p->next[1]->V = Scratch[1];
if (p->next[2] == NULL) p->next[2] = new node();
p->next[2]->V = Scratch[2];
// printf("%p %d %d %d %d %d = %d %d %d\n", p, i, j, k, l, m, Scratch[0].size(), Scratch[1].size(), Scratch[2].size());
ok = 1;
ok &= makeTree(p->next[0], LIM/3);
ok &= makeTree(p->next[1], LIM/3);
ok &= makeTree(p->next[2], LIM/3);
// ok = 1;
if (ok)
break;
}
}
}
else
{
// printf("i%d j%d k%d l%d\n", i, j, k, l);
Scratch[0].clear();
Scratch[1].clear();
Scratch[2].clear();
for (v = 0; v < p->V.size(); v++)
{
// printf("%d\n", answer(p->V[v], i, j, k, l, m));
Scratch[answer(p->V[v], i, j, k, l, m)].push_back(p->V[v]);
}
for (v = 0; v < 3; v++)
if (Scratch[v].size()*3 > LIM)
break;
if (v == 3)
{
p->q = i;
p->a = j;
p->b = k;
p->c = l;
p->d = m;
if (p->next[0] == NULL) p->next[0] = new node();
p->next[0]->V = Scratch[0];
if (p->next[1] == NULL) p->next[1] = new node();
p->next[1]->V = Scratch[1];
if (p->next[2] == NULL) p->next[2] = new node();
p->next[2]->V = Scratch[2];
// printf("%p %d %d %d %d %d = %d %d %d\n", p, i, j, k, l, m, Scratch[0].size(), Scratch[1].size(), Scratch[2].size());
ok = 1;
ok &= makeTree(p->next[0], LIM/3);
ok &= makeTree(p->next[1], LIM/3);
ok &= makeTree(p->next[2], LIM/3);
// ok = 1;
if (ok)
break;
}
}
if (ok) break;
}
if (ok) break;
}
if (ok) break;
}
if (ok) break;
}
// printf("ok %d\n", ok);
// p->q = i;
// p->a = j;
// p->b = k;
// p->c = l;
// p->d = m;
// p->next[0] = new node();
// p->next[0]->V = Scratch[0];
// p->next[1] = new node();
// p->next[1]->V = Scratch[1];
// p->next[2] = new node();
// p->next[2]->V = Scratch[2];
// printf("%p %d %d %d %d %d = %d %d %d\n", p, i, j, k, l, m, Scratch[0].size(), Scratch[1].size(), Scratch[2].size());
// makeTree(p->next[0]);
// makeTree(p->next[1]);
// makeTree(p->next[2]);
return ok;
}
void init(int T) {
root = new node();
int i, j;
for (i = 0; i < 720; i++)
root->V.push_back(i);
for (i = 0; i < 6; i++)
Permu[0].push_back(i);
for (i = 1; i < 720; i++)
{
Permu[i] = Permu[i - 1];
std::next_permutation(Permu[i].begin(), Permu[i].end());
// for (j = 0; j < 6; j++)
// printf("%d ", Permu[i][j]);
// printf("\n");
}
int ok = makeTree(root, 729);
// printf("ok %d\n", ok);
}
void orderCoins() {
node* p = root;
int i, r;
while (p->V.size() > 1)
{
// printf("q %d a %d b %d c %d d %d\n", p->q, p->a, p->b, p->c, p->d);
switch (p->q)
{
case 1:
r = getHeaviest(p->a + 1, p->b + 1, p->c + 1);
if (r == p->a + 1) p = p->next[0];
else if (r == p->b + 1) p = p->next[1];
else if (r == p->c + 1) p = p->next[2];
break;
case 2:
r = getLightest(p->a + 1, p->b + 1, p->c + 1);
if (r == p->a + 1) p = p->next[0];
else if (r == p->b + 1) p = p->next[1];
else if (r == p->c + 1) p = p->next[2];
break;
case 3:
r = getMedian(p->a + 1, p->b + 1, p->c + 1);
if (r == p->a + 1) p = p->next[0];
else if (r == p->b + 1) p = p->next[1];
else if (r == p->c + 1) p = p->next[2];
break;
case 4:
r = getNextLightest(p->a + 1, p->b + 1, p->c + 1, p->d + 1);
if (r == p->a + 1) p = p->next[0];
else if (r == p->b + 1) p = p->next[1];
else if (r == p->c + 1) p = p->next[2];
break;
}
// printf("r %d\n", r);
}
int W[6];
for (i = 0; i < 6; i++)
{
W[Permu[p->V[0]][i]] = i + 1;
}
// for (i = 0; i < 6; i++)
// {
// printf("W %d\n", W[i]);
// }
answer(W);
}
Compilation message
In file included from grader.c:2:0:
graderlib.c: In function 'void answer(int*)':
graderlib.c:53:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
if (_ghksjhdfkae19ga_ > 1)
^~
graderlib.c:56:2: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
for (i = 0; i < 6; i++) {
^~~
scales.cpp: In function 'int answer(int, int, int, int, int, int)':
scales.cpp:21:9: warning: unused variable 'i' [-Wunused-variable]
int i;
^
scales.cpp: In function 'int makeTree(node*, int)':
scales.cpp:92:43: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (v = 0; v < p->V.size(); v++)
~~^~~~~~~~~~~~~
scales.cpp:95:57: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if (Scratch[v].size()*3 > LIM)
~~~~~~~~~~~~~~~~~~~~^~~~~
scales.cpp:128:39: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (v = 0; v < p->V.size(); v++)
~~^~~~~~~~~~~~~
scales.cpp:134:53: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if (Scratch[v].size()*3 > LIM)
~~~~~~~~~~~~~~~~~~~~^~~~~
scales.cpp: In function 'void init(int)':
scales.cpp:191:12: warning: unused variable 'j' [-Wunused-variable]
int i, j;
^
scales.cpp:204:9: warning: unused variable 'ok' [-Wunused-variable]
int ok = makeTree(root, 729);
^~
scales.cpp:189:15: warning: unused parameter 'T' [-Wunused-parameter]
void init(int T) {
^
scales.cpp: In function 'int answer(int, int, int, int, int, int)':
scales.cpp:64:1: warning: control reaches end of non-void function [-Wreturn-type]
}
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
57 ms |
504 KB |
Output is correct |
| 2 |
Correct |
56 ms |
504 KB |
Output is correct |
| 3 |
Correct |
104 ms |
692 KB |
Output is correct |
| 4 |
Correct |
80 ms |
700 KB |
Output is correct |
| 5 |
Correct |
62 ms |
700 KB |
Output is correct |
| 6 |
Correct |
59 ms |
700 KB |
Output is correct |
| 7 |
Correct |
58 ms |
700 KB |
Output is correct |
| 8 |
Correct |
55 ms |
700 KB |
Output is correct |
| 9 |
Correct |
95 ms |
716 KB |
Output is correct |
| 10 |
Correct |
59 ms |
716 KB |
Output is correct |
| 11 |
Correct |
56 ms |
728 KB |
Output is correct |
| 12 |
Correct |
104 ms |
728 KB |
Output is correct |
| 13 |
Correct |
54 ms |
728 KB |
Output is correct |
| 14 |
Correct |
59 ms |
728 KB |
Output is correct |
| 15 |
Correct |
55 ms |
728 KB |
Output is correct |
| 16 |
Correct |
57 ms |
728 KB |
Output is correct |
| 17 |
Correct |
66 ms |
752 KB |
Output is correct |
| 18 |
Correct |
55 ms |
852 KB |
Output is correct |
| 19 |
Correct |
55 ms |
852 KB |
Output is correct |
| 20 |
Correct |
58 ms |
852 KB |
Output is correct |
| 21 |
Correct |
56 ms |
852 KB |
Output is correct |
| 22 |
Correct |
57 ms |
852 KB |
Output is correct |
| 23 |
Correct |
65 ms |
852 KB |
Output is correct |
| 24 |
Correct |
58 ms |
852 KB |
Output is correct |
| 25 |
Correct |
57 ms |
852 KB |
Output is correct |
| 26 |
Correct |
55 ms |
852 KB |
Output is correct |
| 27 |
Correct |
58 ms |
852 KB |
Output is correct |
| 28 |
Correct |
58 ms |
852 KB |
Output is correct |
| 29 |
Correct |
81 ms |
852 KB |
Output is correct |
| 30 |
Correct |
57 ms |
852 KB |
Output is correct |
| 31 |
Correct |
56 ms |
852 KB |
Output is correct |
| 32 |
Correct |
63 ms |
852 KB |
Output is correct |
| 33 |
Correct |
55 ms |
892 KB |
Output is correct |
| 34 |
Correct |
56 ms |
892 KB |
Output is correct |
| 35 |
Correct |
59 ms |
892 KB |
Output is correct |
| 36 |
Correct |
57 ms |
892 KB |
Output is correct |
| 37 |
Correct |
73 ms |
892 KB |
Output is correct |
| 38 |
Correct |
59 ms |
892 KB |
Output is correct |
| 39 |
Correct |
79 ms |
892 KB |
Output is correct |
| 40 |
Correct |
60 ms |
892 KB |
Output is correct |
