| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 886683 | HuyQuang_re_Zero | Scales (IOI15_scales) | C++14 | 27 ms | 1104 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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=0;i<6;i++) w[i]=vec[i];
answer(w);
}
/*
int main()
{
freopen("scales.inp","r",stdin);
freopen("scales.out","w",stdout);
init(0);
orderCoins();
}
*/
Compilation message (stderr)
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| Fetching results... | ||||