#include "scales.h"
#include <bits/stdc++.h>
#define ll long long
using namespace std;
int p[7];
void getInit(vector<int> &v)
{
for (int i = 0; i < 6; i++)
p[v[i]] = i;
}
int getM(int A, int B, int C, vector<int> &v)
{
getInit(v);
int mx = max({p[A], p[B], p[C]}), mi = min({p[A], p[B], p[C]});
if (mi < p[A] && p[A] < mx)
return A;
if (mi < p[B] && p[B] < mx)
return B;
return C;
}
int getH(int A, int B, int C, vector<int> &v)
{
getInit(v);
int mx = max({p[A], p[B], p[C]});
if (p[A] == mx)
return A;
if (p[B] == mx)
return B;
return C;
}
int getL(int A, int B, int C, vector<int> &v)
{
getInit(v);
int mi = min({p[A], p[B], p[C]});
if (p[A] == mi)
return A;
if (p[B] == mi)
return B;
return C;
}
int getNL(int A, int B, int C, int D, vector<int> &v)
{
int mi = getL(A, B, C, v),
me = getM(A, B, C, v),
mx = getH(A, B, C, v);
if (p[D] < p[mi])
return mi;
if (p[D] < p[me])
return me;
if (p[D] < p[mx])
return mx;
return mi;
}
/*
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);
*/
struct op
{
int type, a, b, c, d, out;
} tree[800][6];
bool brute(vector<pair<vector<int>, int>> &state, int dep)
{
// cout << "brute " << sz << '\n';
int sz = state.size();
if (sz <= 1)
return 1;
for (int D = 1; D <= 6; D++)
for (int A = 1; A <= 6; A++)
for (int B = A + 1; B <= 6; B++)
for (int C = B + 1; C <= 6; C++)
if (A != D && B != D && C != D)
{
vector<pair<vector<int>, int>> space[7];
for (auto [v, i] : state)
space[getNL(A, B, C, D, v)].emplace_back(make_pair(v, i));
bool good = 1;
for (int k = 1; k <= 6; k++)
if (space[k].size() > (sz + 2) / 3)
good = 0;
if (good)
{
bool solve = 1;
for (int k = 1; k <= 6; k++)
if (!space[k].empty())
solve &= brute(space[k], dep + 1);
if (solve)
{
for (int k = 1; k <= 6; k++)
for (auto [v, i] : space[k])
tree[i][dep] = {2, A, B, C, D, k};
return 1;
}
}
}
for (int A = 1; A <= 6; A++)
for (int B = A + 1; B <= 6; B++)
for (int C = B + 1; C <= 6; C++)
{
vector<pair<vector<int>, int>> space[7];
for (auto [v, i] : state)
{
for (int i = 0; i < 6; i++)
p[i + 1] = v[i];
space[getM(A, B, C, v)].emplace_back(make_pair(v, i));
}
bool good = 1;
for (int k = 1; k <= 6; k++)
if (space[k].size() > (sz + 2) / 3)
good = 0;
if (good)
{
bool solve = 1;
for (int k = 1; k <= 6; k++)
if (!space[k].empty())
solve &= brute(space[k], dep + 1);
if (solve)
{
for (int k = 1; k <= 6; k++)
for (auto [v, i] : space[k])
tree[i][dep] = {1, A, B, C, 0, k};
return 1;
}
}
}
return 0;
}
vector<pair<vector<int>, int>> allp;
void init(int T)
{
vector<int> v = {1, 2, 3, 4, 5, 6};
for (int i = 0; i < 720; i++)
{
allp.emplace_back(make_pair(v, i));
next_permutation(v.begin(), v.end());
}
brute(allp, 0);
}
void orderCoins()
{
vector<int> remain, tmp;
for (int i = 0; i < 720; i++)
remain.emplace_back(i);
for (int i = 0; i < 6; i++)
{
int j = remain.back(), res;
auto [t, a, b, c, d, o] = tree[j][i];
if (t == 1)
res = getMedian(a, b, c);
else
res = getNextLightest(a, b, c, d);
tmp.clear();
for (auto k : remain)
if (tree[k][i].out == res)
tmp.emplace_back(k);
swap(tmp, remain);
}
int ans[6];
for (int i = 0; i < 6; i++)
ans[i] = allp[remain[0]].first[i];
answer(ans);
}
Compilation message
scales.cpp: In function 'bool brute(std::vector<std::pair<std::vector<int>, int> >&, int)':
scales.cpp:70:24: warning: conversion from 'std::vector<std::pair<std::vector<int>, int> >::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
70 | int sz = state.size();
| ~~~~~~~~~~^~
scales.cpp:81:35: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
81 | for (auto [v, i] : state)
| ^
scales.cpp:85:49: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<std::vector<int>, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
85 | if (space[k].size() > (sz + 2) / 3)
| ~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~
scales.cpp:96:47: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
96 | for (auto [v, i] : space[k])
| ^
scales.cpp:108:27: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
108 | for (auto [v, i] : state)
| ^
scales.cpp:110:30: warning: declaration of 'i' shadows a previous local [-Wshadow]
110 | for (int i = 0; i < 6; i++)
| ^
scales.cpp:108:31: note: shadowed declaration is here
108 | for (auto [v, i] : state)
| ^
scales.cpp:116:41: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<std::vector<int>, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
116 | if (space[k].size() > (sz + 2) / 3)
| ~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~
scales.cpp:127:39: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
127 | for (auto [v, i] : space[k])
| ^
scales.cpp: In function 'void init(int)':
scales.cpp:137:15: warning: unused parameter 'T' [-Wunused-parameter]
137 | void init(int T)
| ~~~~^
scales.cpp: In function 'void orderCoins()':
scales.cpp:156:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
156 | auto [t, a, b, c, d, o] = tree[j][i];
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
34 ms |
436 KB |
Output is correct |
| 2 |
Correct |
34 ms |
500 KB |
Output is correct |
| 3 |
Correct |
34 ms |
516 KB |
Output is correct |
| 4 |
Correct |
35 ms |
516 KB |
Output is correct |
| 5 |
Correct |
38 ms |
620 KB |
Output is correct |
| 6 |
Correct |
34 ms |
468 KB |
Output is correct |
| 7 |
Correct |
35 ms |
504 KB |
Output is correct |
| 8 |
Correct |
35 ms |
468 KB |
Output is correct |
| 9 |
Correct |
34 ms |
468 KB |
Output is correct |
| 10 |
Correct |
35 ms |
528 KB |
Output is correct |
| 11 |
Correct |
35 ms |
468 KB |
Output is correct |
| 12 |
Correct |
35 ms |
512 KB |
Output is correct |
| 13 |
Correct |
35 ms |
468 KB |
Output is correct |
| 14 |
Correct |
34 ms |
432 KB |
Output is correct |
| 15 |
Correct |
34 ms |
468 KB |
Output is correct |
| 16 |
Correct |
35 ms |
432 KB |
Output is correct |
| 17 |
Correct |
35 ms |
504 KB |
Output is correct |
| 18 |
Correct |
35 ms |
516 KB |
Output is correct |
| 19 |
Correct |
35 ms |
520 KB |
Output is correct |
| 20 |
Correct |
35 ms |
596 KB |
Output is correct |
| 21 |
Correct |
36 ms |
468 KB |
Output is correct |
| 22 |
Correct |
35 ms |
512 KB |
Output is correct |
| 23 |
Correct |
35 ms |
524 KB |
Output is correct |
| 24 |
Correct |
35 ms |
468 KB |
Output is correct |
| 25 |
Correct |
35 ms |
428 KB |
Output is correct |
| 26 |
Correct |
35 ms |
432 KB |
Output is correct |
| 27 |
Correct |
35 ms |
496 KB |
Output is correct |
| 28 |
Correct |
35 ms |
504 KB |
Output is correct |
| 29 |
Correct |
36 ms |
468 KB |
Output is correct |
| 30 |
Correct |
35 ms |
512 KB |
Output is correct |
| 31 |
Correct |
35 ms |
468 KB |
Output is correct |
| 32 |
Correct |
35 ms |
528 KB |
Output is correct |
| 33 |
Correct |
35 ms |
524 KB |
Output is correct |
| 34 |
Correct |
34 ms |
468 KB |
Output is correct |
| 35 |
Correct |
35 ms |
468 KB |
Output is correct |
| 36 |
Correct |
35 ms |
512 KB |
Output is correct |
| 37 |
Correct |
36 ms |
516 KB |
Output is correct |
| 38 |
Correct |
36 ms |
468 KB |
Output is correct |
| 39 |
Correct |
35 ms |
516 KB |
Output is correct |
| 40 |
Correct |
35 ms |
532 KB |
Output is correct |
