#include <bits/stdc++.h>
#define db long double
#define II pair <ll,ll>
#define III pair <ll,II>
#define IV pair <vector <int>,vector <int> >
#define TII pair <treap*,treap*>
#define fst first
#define snd second
#define BIT(x,i) ((x>>i)&1)
#define pi acos(-1)
#define to_radian(x) (x*pi/180.0)
#define to_degree(x) (x*180.0/pi)
#define Log(x) (31-__builtin_clz((int)x))
#define LogLL(x) (63-__builtin_clzll((ll)x))
#include "scales.h"
using namespace std;
/*
struct Interactive
{
int a[7]={ 0,3,4,6,2,1,5 };
int Query(int type,int A,int B,int C,int D)
{
int val[4]={ 0,a[A],a[B],a[C] };
sort(val+1,val+4);
int k;
if(type<=3) k=val[type];
else if(val[3]<a[D]) k=val[1];
else
{
for(int i=3;i>=1;i--)
if(val[i]>a[D]) k=val[i];
}
if(a[A]==k) return A;
if(a[B]==k) return B;
if(a[C]==k) return C;
}
} IR;
int getLightest(int A,int B,int C) { return IR.Query(1,A,B,C,0); }
int getMedian(int A,int B,int C) { return IR.Query(2,A,B,C,0); }
int getHeaviest(int A,int B,int C) { return IR.Query(3,A,B,C,0); }
int getNextLightest(int A,int B,int C,int D) { return IR.Query(4,A,B,C,D); }
void answer(int w[])
{
for(int i=0;i<6;i++) cout<<w[i]<<" ";
}
*/
struct query { int type,A,B,C,D; };
vector <query> query_set;
map <vector <vector <int> >,query> opt;
int limit[6]={ 243,81,27,9,3,1 };
vector <vector <int> > Set;
int Encode_answer(vector <int> a,query q)
{
int val[4]={ 0,a[q.A-1],a[q.B-1],a[q.C-1] };
sort(val+1,val+4);
int k;
if(q.type<=3) k=val[q.type];
else if(val[3]<a[q.D-1]) k=val[1];
else
{
for(int i=3;i>=1;i--)
if(val[i]>a[q.D-1]) k=val[i];
}
if(a[q.A-1]==k) return 0;
if(a[q.B-1]==k) return 1;
if(a[q.C-1]==k) return 2;
}
bool check(vector <vector <int> > Set,int step)
{
if(Set.size()<2) return 1;
for(query q:query_set)
{
vector <vector <int> > split[3];
for(vector <int> x:Set)
split[Encode_answer(x,q)].push_back(x);
int lim=min(limit[step],(int)Set.size()-1);
if(split[0].size()<=lim && split[1].size()<=lim && split[2].size()<=lim)
{
if(check(split[0],step+1) && check(split[1],step+1) && check(split[2],step+1))
{
opt[Set]=q;
return 1;
}
}
}
return 0;
}
void init(int k)
{
for(int type=1;type<=4;type++)
for(int i=1;i<=6;i++)
for(int j=i+1;j<=6;j++)
for(int k=j+1;k<=6;k++)
if(type<4) query_set.push_back({ type,i,j,k,0 });
else
for(int h=1;h<=6;h++)
if(h!=i && h!=j && h!=k)
query_set.push_back({ type,i,j,k,h });
vector <int> vec;
for(int i=1;i<=6;i++) vec.push_back(i);
do
{
Set.push_back(vec);
}
while(next_permutation(vec.begin(),vec.end()));
check(Set,0);
}
vector <int> solve(vector <vector <int> > Set)
{
if(Set.size()==1) return Set[0];
query q=opt[Set];
vector <vector <int> > split[3];
for(vector <int> x:Set)
split[Encode_answer(x,q)].push_back(x);
int ok,num;
if(q.type==1) ok=getLightest(q.A,q.B,q.C);
if(q.type==2) ok=getMedian(q.A,q.B,q.C);
if(q.type==3) ok=getHeaviest(q.A,q.B,q.C);
if(q.type==4) ok=getNextLightest(q.A,q.B,q.C,q.D);
if(ok==q.A) num=0;
if(ok==q.B) num=1;
if(ok==q.C) num=2;
return solve(split[num]);
}
void orderCoins()
{
vector <int> vec=solve(Set);
int w[6];
for(int i=1;i<=6;i++)
for(int j=0;j<6;j++)
if(vec[j]==i) w[i-1]=j+1;
answer(w);
}
/*
int main()
{
freopen("scales.inp","r",stdin);
freopen("scales.out","w",stdout);
init(0);
orderCoins();
}
*/
Compilation message
scales.cpp: In function 'bool check(std::vector<std::vector<int> >, int)':
scales.cpp:71:35: warning: declaration of 'Set' shadows a global declaration [-Wshadow]
71 | bool check(vector <vector <int> > Set,int step)
| ~~~~~~~~~~~~~~~~~~~~~~~^~~
scales.cpp:52:24: note: shadowed declaration is here
52 | vector <vector <int> > Set;
| ^~~
scales.cpp:80:27: warning: comparison of integer expressions of different signedness: 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
80 | if(split[0].size()<=lim && split[1].size()<=lim && split[2].size()<=lim)
| ~~~~~~~~~~~~~~~^~~~~
scales.cpp:80:51: warning: comparison of integer expressions of different signedness: 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
80 | if(split[0].size()<=lim && split[1].size()<=lim && split[2].size()<=lim)
| ~~~~~~~~~~~~~~~^~~~~
scales.cpp:80:75: warning: comparison of integer expressions of different signedness: 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
80 | if(split[0].size()<=lim && split[1].size()<=lim && split[2].size()<=lim)
| ~~~~~~~~~~~~~~~^~~~~
scales.cpp: In function 'void init(int)':
scales.cpp:96:25: warning: declaration of 'int k' shadows a parameter [-Wshadow]
96 | for(int k=j+1;k<=6;k++)
| ^
scales.cpp:91:15: note: shadowed declaration is here
91 | void init(int k)
| ~~~~^
scales.cpp:91:15: warning: unused parameter 'k' [-Wunused-parameter]
scales.cpp: In function 'std::vector<int> solve(std::vector<std::vector<int> >)':
scales.cpp:115:43: warning: declaration of 'Set' shadows a global declaration [-Wshadow]
115 | vector <int> solve(vector <vector <int> > Set)
| ~~~~~~~~~~~~~~~~~~~~~~~^~~
scales.cpp:52:24: note: shadowed declaration is here
52 | vector <vector <int> > Set;
| ^~~
scales.cpp: In function 'int Encode_answer(std::vector<int>, query)':
scales.cpp:68:1: warning: control reaches end of non-void function [-Wreturn-type]
68 | }
| ^
scales.cpp:66:5: warning: 'k' may be used uninitialized in this function [-Wmaybe-uninitialized]
66 | if(a[q.B-1]==k) return 1;
| ^~
scales.cpp: In function 'std::vector<int> solve(std::vector<std::vector<int> >)':
scales.cpp:128:5: warning: 'ok' may be used uninitialized in this function [-Wmaybe-uninitialized]
128 | if(ok==q.B) num=1;
| ^~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
22 ms |
860 KB |
Output is correct |
| 2 |
Correct |
23 ms |
860 KB |
Output is correct |
| 3 |
Correct |
23 ms |
820 KB |
Output is correct |
| 4 |
Correct |
22 ms |
860 KB |
Output is correct |
| 5 |
Correct |
23 ms |
668 KB |
Output is correct |
| 6 |
Correct |
23 ms |
860 KB |
Output is correct |
| 7 |
Correct |
22 ms |
756 KB |
Output is correct |
| 8 |
Correct |
22 ms |
860 KB |
Output is correct |
| 9 |
Correct |
22 ms |
660 KB |
Output is correct |
| 10 |
Correct |
22 ms |
860 KB |
Output is correct |
| 11 |
Correct |
22 ms |
680 KB |
Output is correct |
| 12 |
Correct |
23 ms |
860 KB |
Output is correct |
| 13 |
Correct |
22 ms |
860 KB |
Output is correct |
| 14 |
Correct |
22 ms |
860 KB |
Output is correct |
| 15 |
Correct |
22 ms |
792 KB |
Output is correct |
| 16 |
Correct |
22 ms |
860 KB |
Output is correct |
| 17 |
Correct |
22 ms |
856 KB |
Output is correct |
| 18 |
Correct |
22 ms |
856 KB |
Output is correct |
| 19 |
Correct |
23 ms |
860 KB |
Output is correct |
| 20 |
Correct |
23 ms |
708 KB |
Output is correct |
| 21 |
Correct |
28 ms |
884 KB |
Output is correct |
| 22 |
Correct |
22 ms |
852 KB |
Output is correct |
| 23 |
Correct |
23 ms |
856 KB |
Output is correct |
| 24 |
Correct |
23 ms |
844 KB |
Output is correct |
| 25 |
Correct |
23 ms |
860 KB |
Output is correct |
| 26 |
Correct |
22 ms |
772 KB |
Output is correct |
| 27 |
Correct |
23 ms |
860 KB |
Output is correct |
| 28 |
Correct |
22 ms |
800 KB |
Output is correct |
| 29 |
Correct |
22 ms |
856 KB |
Output is correct |
| 30 |
Correct |
24 ms |
876 KB |
Output is correct |
| 31 |
Correct |
23 ms |
860 KB |
Output is correct |
| 32 |
Correct |
22 ms |
864 KB |
Output is correct |
| 33 |
Correct |
25 ms |
860 KB |
Output is correct |
| 34 |
Correct |
25 ms |
860 KB |
Output is correct |
| 35 |
Correct |
22 ms |
860 KB |
Output is correct |
| 36 |
Correct |
22 ms |
764 KB |
Output is correct |
| 37 |
Correct |
26 ms |
860 KB |
Output is correct |
| 38 |
Correct |
24 ms |
840 KB |
Output is correct |
| 39 |
Correct |
23 ms |
852 KB |
Output is correct |
| 40 |
Correct |
23 ms |
860 KB |
Output is correct |
