#include "scales.h"
#include <bits/stdc++.h>
using namespace std;
typedef int INT;
#define FOR(i,l,r) for(int i = (l); i < (r); i++)
#define fst first
#define snd second
#define pb push_back
typedef vector<int> vi;
typedef pair<int,int> ii;
typedef vector<ii> vii;
typedef vector<vi> vvi;
vi op;
vvi args;
// this corresponds to the relative weight of the coins
vvi perms;
vi ans;
int pows[] = {1,3,9,27,81,243,729};
int heavy(int i, int A, int B, int C){
vi &p = perms[i];
if(p[A] > p[B] and p[A] > p[C]) return 0;
if(p[B] > p[A] and p[B] > p[C]) return 1;
if(p[C] > p[B] and p[C] > p[A]) return 2;
}
int light(int i, int A, int B, int C){
vi &p = perms[i];
if(p[A] < p[B] and p[A] < p[C]) return 0;
if(p[B] < p[A] and p[B] < p[C]) return 1;
if(p[C] < p[B] and p[C] < p[A]) return 2;
}
int median(int i, int A, int B, int C){
vi &p = perms[i];
vi arr(3, 0);
arr[0] = A; arr[1] = B; arr[2] = C;
sort(arr.begin(), arr.end(), [&p] (int i, int j) {return p[i] < p[j];});
if(arr[1] == A) return 0;
if(arr[1] == B) return 1;
if(arr[1] == C) return 2;
}
int nextl(int i, int A, int B, int C, int D){
vi &p = perms[i];
int l = 100;
if(p[A] > p[D] and p[A] < l) l = p[A];
if(p[B] > p[D] and p[B] < l) l = p[B];
if(p[C] > p[D] and p[C] < l) l = p[C];
if(l == 100) return light(i, A, B, C);
if(l == p[A]) return 0;
if(l == p[B]) return 1;
if(l == p[C]) return 2;
}
int maxh = 0;
int leafcnt = 0;
int cnt;
int build(vi &ps, int n, int h){
if(h > 6) return ps.size() == 0;
maxh = max(h, maxh);
ans[n] = -1;
//if(h < 5) return;
//cout << ps.size() << " " << n << " " << h << endl;
for(int i : ps){
//for(int k : perms[i]) cout << k << " ";
//cout << endl;
}
//cout<<endl;
if(ps.size() == 0) return 1;
if(ps.size() == 1){
leafcnt++;
cnt += h > 6;
ans[n] = ps[0];
return 1;
}
vi bestars; int bestop;
double bestentropy = 0;
// All must be <= |ps|/3
FOR(a, 0, 4) FOR(b, a+1, 5) FOR(c, b+1, 6){
//cerr<<a<<" "<<b<<" "<<c<<endl;
vvi division(3);
for(int i : ps) division[light(i, a, b, c)].pb(i);
if(max(division[0].size(), division[1].size()) <= pows[5-h] and division[2].size() <= pows[5-h]) {
bool done = 1;
FOR(i, 0, 3){
//cout << 0 << endl;
if(!build(division[i], 3*n+i-1, h+1)) {done = false; break;}
}
if(done) {
args[n].pb(a); args[n].pb(b); args[n].pb(c);
op[n] = 0;
return 1;
}
}
}
FOR(a, 0, 4) FOR(b, a+1, 5) FOR(c, b+1, 6){
vvi division(3);
for(int i : ps) division[heavy(i, a, b, c)].pb(i);
if(max(division[0].size(), division[1].size()) <= pows[5-h] and division[2].size() <= pows[5-h]) {
bool done = 1;
FOR(i, 0, 3){
//cout << 1 << endl;
if(!build(division[i], 3*n+i-1, h+1)) {done = false; break;}
}
if(done) {
args[n].pb(a); args[n].pb(b); args[n].pb(c);
op[n] = 1;
return 1;
}
}
}
FOR(a, 0, 4) FOR(b, a+1, 5) FOR(c, b+1, 6){
vvi division(3);
for(int i : ps) division[median(i, a, b, c)].pb(i);
if(max(division[0].size(), division[1].size()) <= pows[5-h] and division[2].size() <= pows[5-h]) {
bool done = 1;
FOR(i, 0, 3){
//cout << 2 << endl;
if(!build(division[i], 3*n+i-1, h+1)) {done = false; break;}
}
if(done) {
args[n].pb(a); args[n].pb(b); args[n].pb(c);
op[n] = 2;
return 1;
}
}
}
FOR(d, 0, 6) FOR(a, 0, 4) FOR(b, a+1, 5) FOR(c, b+1, 6){
//cout<<"lastl test"<<endl;
if(d == a or d == b or d == c) continue;
vvi division(3);
for(int i : ps) division[nextl(i, a, b, c, d)].pb(i);
//cout << division[0].size() << " " << division[1].size() << " " << division[2].size() << endl;
if(max(division[0].size(), division[1].size()) <= pows[5-h] and division[2].size() <= pows[5-h]) {
bool done = 1;
//cout << 3 << endl;
FOR(i, 0, 3){
if(!build(division[i], 3*n+i-1, h+1)) {done = false; break;}
}
if(done) {
args[n].pb(a); args[n].pb(b); args[n].pb(c); args[n].pb(d);
op[n] = 3;
return 1;
}
}
}
return 0;
}
int query(int i, vi arg){
int val = -1;
if(i == 0) val = getLightest(arg[0]+1, arg[1]+1, arg[2]+1)-1;
if(i == 1) val = getHeaviest(arg[0]+1, arg[1]+1, arg[2]+1)-1;
if(i == 2) val = getMedian(arg[0]+1, arg[1]+1, arg[2]+1)-1;
if(i == 3) val = getNextLightest(arg[0]+1, arg[1]+1, arg[2]+1, arg[3]+1)-1;
FOR(i, 0, 3) if(val == arg[i]) return i;
}
int get(int n){
//cout<<n<<endl;
if(ans[n] != -1) return ans[n];
return get( 3*n-1 + query(op[n], args[n]) );
}
void init(INT T) {
op.assign(5000, -1);
args.resize(5000);
ans.assign(5000, -1);
vi p;
FOR(i,0,6) p.pb(i);
do {
perms.pb(p);
} while(next_permutation(p.begin(), p.end()));
//cerr<<perms.size()<<endl;
//for(int w : perms[100]) cout << w << " ";
//cout<<endl;
//cerr<< median(100, 2, 5, 3) << endl;
vi all;
FOR(i, 0, 720)all.pb(i);
build(all, 1, 0);
//cout<<"initialized"<<endl;
//cout<<maxh<<endl;
//cout<<cnt<<endl;
/*cout<<leafcnt<<endl;
FOR(i, 0, 720){
for(int k : perms[i]) cout << k+1 << " ";
cout<<endl;
}*/
}
void orderCoins() {
/* ... */
INT W[] = {1, 2, 3, 4, 5, 6};
int i = get(1);
FOR(j, 0, 6) W[perms[i][j]] = j+1;
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 lambda function:
scales.cpp:42:52: warning: declaration of 'int i' shadows a parameter [-Wshadow]
sort(arr.begin(), arr.end(), [&p] (int i, int j) {return p[i] < p[j];});
^
scales.cpp:38:16: note: shadowed declaration is here
int median(int i, int A, int B, int C){
^
scales.cpp: In function 'int build(vi&, int, int)':
scales.cpp:68:13: warning: unused variable 'i' [-Wunused-variable]
for(int i : ps){
^
scales.cpp:89:56: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(max(division[0].size(), division[1].size()) <= pows[5-h] and division[2].size() <= pows[5-h]) {
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~
scales.cpp:89:92: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(max(division[0].size(), division[1].size()) <= pows[5-h] and division[2].size() <= pows[5-h]) {
~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~
scales.cpp:106:56: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(max(division[0].size(), division[1].size()) <= pows[5-h] and division[2].size() <= pows[5-h]) {
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~
scales.cpp:106:92: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(max(division[0].size(), division[1].size()) <= pows[5-h] and division[2].size() <= pows[5-h]) {
~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~
scales.cpp:123:56: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(max(division[0].size(), division[1].size()) <= pows[5-h] and division[2].size() <= pows[5-h]) {
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~
scales.cpp:123:92: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(max(division[0].size(), division[1].size()) <= pows[5-h] and division[2].size() <= pows[5-h]) {
~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~
scales.cpp:142:56: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(max(division[0].size(), division[1].size()) <= pows[5-h] and division[2].size() <= pows[5-h]) {
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~
scales.cpp:142:92: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(max(division[0].size(), division[1].size()) <= pows[5-h] and division[2].size() <= pows[5-h]) {
~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~
scales.cpp:80:21: warning: unused variable 'bestop' [-Wunused-variable]
vi bestars; int bestop;
^~~~~~
scales.cpp:81:12: warning: unused variable 'bestentropy' [-Wunused-variable]
double bestentropy = 0;
^~~~~~~~~~~
scales.cpp: In function 'int query(int, vi)':
scales.cpp:164:9: warning: declaration of 'int i' shadows a parameter [-Wshadow]
FOR(i, 0, 3) if(val == arg[i]) return i;
^
scales.cpp:7:28: note: in definition of macro 'FOR'
#define FOR(i,l,r) for(int i = (l); i < (r); i++)
^
scales.cpp:158:15: note: shadowed declaration is here
int query(int i, vi arg){
^
scales.cpp: In function 'void init(INT)':
scales.cpp:173:15: warning: unused parameter 'T' [-Wunused-parameter]
void init(INT T) {
^
scales.cpp: In function 'int heavy(int, int, int, int)':
scales.cpp:29:1: warning: control reaches end of non-void function [-Wreturn-type]
}
^
scales.cpp: In function 'int light(int, int, int, int)':
scales.cpp:36:1: warning: control reaches end of non-void function [-Wreturn-type]
}
^
scales.cpp: In function 'int median(int, int, int, int)':
scales.cpp:46:1: warning: control reaches end of non-void function [-Wreturn-type]
}
^
scales.cpp: In function 'int nextl(int, int, int, int, int)':
scales.cpp:58:1: warning: control reaches end of non-void function [-Wreturn-type]
}
^
scales.cpp: In function 'int query(int, vi)':
scales.cpp:165:1: warning: control reaches end of non-void function [-Wreturn-type]
}
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
14 ms |
504 KB |
Output is correct |
| 2 |
Correct |
15 ms |
616 KB |
Output is correct |
| 3 |
Correct |
14 ms |
684 KB |
Output is correct |
| 4 |
Correct |
16 ms |
684 KB |
Output is correct |
| 5 |
Correct |
15 ms |
684 KB |
Output is correct |
| 6 |
Correct |
13 ms |
708 KB |
Output is correct |
| 7 |
Correct |
14 ms |
708 KB |
Output is correct |
| 8 |
Correct |
15 ms |
708 KB |
Output is correct |
| 9 |
Correct |
14 ms |
776 KB |
Output is correct |
| 10 |
Correct |
17 ms |
776 KB |
Output is correct |
| 11 |
Correct |
15 ms |
776 KB |
Output is correct |
| 12 |
Correct |
16 ms |
776 KB |
Output is correct |
| 13 |
Correct |
15 ms |
776 KB |
Output is correct |
| 14 |
Correct |
18 ms |
776 KB |
Output is correct |
| 15 |
Correct |
17 ms |
776 KB |
Output is correct |
| 16 |
Correct |
15 ms |
816 KB |
Output is correct |
| 17 |
Correct |
15 ms |
816 KB |
Output is correct |
| 18 |
Correct |
16 ms |
816 KB |
Output is correct |
| 19 |
Correct |
13 ms |
816 KB |
Output is correct |
| 20 |
Correct |
14 ms |
816 KB |
Output is correct |
| 21 |
Correct |
14 ms |
816 KB |
Output is correct |
| 22 |
Correct |
15 ms |
816 KB |
Output is correct |
| 23 |
Correct |
15 ms |
816 KB |
Output is correct |
| 24 |
Correct |
16 ms |
892 KB |
Output is correct |
| 25 |
Correct |
15 ms |
892 KB |
Output is correct |
| 26 |
Correct |
16 ms |
892 KB |
Output is correct |
| 27 |
Correct |
15 ms |
892 KB |
Output is correct |
| 28 |
Correct |
23 ms |
892 KB |
Output is correct |
| 29 |
Correct |
14 ms |
892 KB |
Output is correct |
| 30 |
Correct |
14 ms |
892 KB |
Output is correct |
| 31 |
Correct |
14 ms |
892 KB |
Output is correct |
| 32 |
Correct |
14 ms |
892 KB |
Output is correct |
| 33 |
Correct |
15 ms |
892 KB |
Output is correct |
| 34 |
Correct |
15 ms |
892 KB |
Output is correct |
| 35 |
Correct |
15 ms |
892 KB |
Output is correct |
| 36 |
Correct |
14 ms |
892 KB |
Output is correct |
| 37 |
Correct |
17 ms |
892 KB |
Output is correct |
| 38 |
Correct |
15 ms |
892 KB |
Output is correct |
| 39 |
Correct |
14 ms |
892 KB |
Output is correct |
| 40 |
Correct |
14 ms |
892 KB |
Output is correct |
