#include "scales.h"
#include <bits/stdc++.h>
#pragma GCC optimize("O2")
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
#define debug(x) {cerr<<#x<<"="<<x<<"\n";}
#define debug2(x, y) {cerr<<#x<<", "<<#y<<"="<<x<<", "<<y<<"\n";}
#define debugp(p) {cerr<<#p<<"={"<<p.first<<", "<<p.second<<"}\n";}
#define all(x) x.begin(), x.end()
#define pb push_back
typedef array<bool, 720> state;
int n, m;
vi perms[720];
vi opers[120];
int tmp[7], out[6], tav[7];
bool mark[720];
int prep[720][120];
map<state, int> DP[7];
state all1, curr;
int Ask(vi &oper){
if (oper[0]==1) return getLightest(oper[1], oper[2], oper[3]);
if (oper[0]==2) return getMedian(oper[1], oper[2], oper[3]);
if (oper[0]==3) return getHeaviest(oper[1], oper[2], oper[3]);
return getNextLightest(oper[1], oper[2], oper[3], oper[4]);
}
int _Ask(vi &perm, vi oper){
for (int i=0; i<6; i++) tmp[perm[i]]=i;
sort(oper.begin()+1, oper.begin()+4, [](int i, int j){
return tmp[i]<tmp[j];
});
if (oper[0]<=3) return oper[oper[0]];
int a=oper[1], b=oper[2], c=oper[3], d=oper[4];
if (tmp[d]<tmp[a]) return a;
if (tmp[d]<tmp[b]) return b;
if (tmp[d]<tmp[c]) return c;
return a;
}
bool BT(state st, int cnt){
int t1=0;
for (int j=0; j<720; j++) t1+=st[j];
// debug2(cnt, t1)
if (t1<=1) return 1;
if (t1>tav[cnt]) return 0;
if (DP[cnt].count(st)) return (DP[cnt][st]!=-1);
for (int i=0; i<120; i++){
int ta=0, tb=0, tc=0;
int a=opers[i][1], b=opers[i][2], c=opers[i][3];
state Sa, Sb, Sc;
for (int j=0; j<720; j++) Sa[j]=Sb[j]=Sc[j]=0;
for (int j=0; j<720; j++) if (st[j]){
int tmp=prep[j][i];
if (tmp==a) ta++, Sa[j]=1;
if (tmp==b) tb++, Sb[j]=1;
if (tmp==c) tc++, Sc[j]=1;
}
if (max({ta, tb, tc})>tav[cnt-1]) continue ;
if (BT(Sa, cnt-1) && BT(Sb, cnt-1) && BT(Sc, cnt-1)){
DP[cnt][st]=i;
return 1;
}
}
DP[cnt][st]=-1;
return 0;
}
void init(int T){
T=T; // dont warn :)
vi shit={1, 2, 3, 4, 5, 6};
do{
perms[n++]=shit;
} while(next_permutation(all(shit)));
for (int a=1; a<=6; a++) for (int b=a+1; b<=6; b++) for (int c=b+1; c<=6; c++){
opers[m++]={1, a, b, c};
opers[m++]={2, a, b, c};
opers[m++]={3, a, b, c};
for (int d=1; d<=6; d++) if (d!=a && d!=b && d!=c) opers[m++]={4, a, b, c, d};
}
assert(n==720 && m==120);
for (int i=0; i<n; i++) for (int j=0; j<m; j++)
prep[i][j]=_Ask(perms[i], opers[j]);
for (int i=0; i<720; i++) all1[i]=1;
tav[0]=1;
for (int i=1; i<=6; i++) tav[i]=tav[i-1]*3;
assert(BT(all1, 6));
}
void orderCoins(){
curr=all1;
for (int cnt=6; cnt; cnt--){
int opid=DP[cnt][curr];
assert(opid!=-1);
int res=Ask(opers[opid]), ted=0;
for (int i=0; i<n; i++) if (curr[i]){
if (prep[i][opid]==res) ted++;
else curr[i]=0;
}
if (ted==1) break ;
}
for (int i=0; i<n; i++) if (curr[i]){
for (int j=0; j<6; j++) out[j]=perms[i][j];
}
answer(out);
// debug("done")
}
Compilation message
scales.cpp: In function 'bool BT(state, int)':
scales.cpp:56:8: warning: declaration of 'tmp' shadows a global declaration [-Wshadow]
56 | int tmp=prep[j][i];
| ^~~
scales.cpp:19:5: note: shadowed declaration is here
19 | int tmp[7], out[6], tav[7];
| ^~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
72 ms |
1092 KB |
Output is correct |
2 |
Correct |
74 ms |
1220 KB |
Output is correct |
3 |
Correct |
72 ms |
1120 KB |
Output is correct |
4 |
Correct |
74 ms |
1092 KB |
Output is correct |
5 |
Correct |
72 ms |
1152 KB |
Output is correct |
6 |
Correct |
72 ms |
1120 KB |
Output is correct |
7 |
Correct |
72 ms |
1044 KB |
Output is correct |
8 |
Correct |
86 ms |
1092 KB |
Output is correct |
9 |
Correct |
84 ms |
1136 KB |
Output is correct |
10 |
Correct |
78 ms |
1104 KB |
Output is correct |
11 |
Correct |
72 ms |
1048 KB |
Output is correct |
12 |
Correct |
72 ms |
1140 KB |
Output is correct |
13 |
Correct |
78 ms |
1140 KB |
Output is correct |
14 |
Correct |
72 ms |
1132 KB |
Output is correct |
15 |
Correct |
72 ms |
1068 KB |
Output is correct |
16 |
Correct |
72 ms |
1136 KB |
Output is correct |
17 |
Correct |
72 ms |
1120 KB |
Output is correct |
18 |
Correct |
72 ms |
1092 KB |
Output is correct |
19 |
Correct |
81 ms |
1068 KB |
Output is correct |
20 |
Correct |
85 ms |
1164 KB |
Output is correct |
21 |
Correct |
72 ms |
1128 KB |
Output is correct |
22 |
Correct |
72 ms |
1108 KB |
Output is correct |
23 |
Correct |
72 ms |
1092 KB |
Output is correct |
24 |
Correct |
72 ms |
1072 KB |
Output is correct |
25 |
Correct |
74 ms |
1040 KB |
Output is correct |
26 |
Correct |
72 ms |
1140 KB |
Output is correct |
27 |
Correct |
73 ms |
1160 KB |
Output is correct |
28 |
Correct |
85 ms |
1136 KB |
Output is correct |
29 |
Correct |
87 ms |
1152 KB |
Output is correct |
30 |
Correct |
74 ms |
1072 KB |
Output is correct |
31 |
Correct |
73 ms |
1092 KB |
Output is correct |
32 |
Correct |
72 ms |
1092 KB |
Output is correct |
33 |
Correct |
72 ms |
1088 KB |
Output is correct |
34 |
Correct |
72 ms |
1160 KB |
Output is correct |
35 |
Correct |
72 ms |
1124 KB |
Output is correct |
36 |
Correct |
72 ms |
1220 KB |
Output is correct |
37 |
Correct |
74 ms |
1116 KB |
Output is correct |
38 |
Correct |
72 ms |
1092 KB |
Output is correct |
39 |
Correct |
73 ms |
1096 KB |
Output is correct |
40 |
Correct |
72 ms |
1148 KB |
Output is correct |