| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1057309 | MuhammadSaram | Scales (IOI15_scales) | C++17 | 0 ms | 0 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>
using namespace std;
#define perm array<int, 6>
#define state vector<perm>
#define qu array<int, 4>
map<state,qu> nxt;
int maxx(perm &p,qu &q)
{
return max(p[q[0]],max(p[q[1]],p[q[2]]));
}
int minn(perm &p,qu &q)
{
return min(p[q[0]],min(p[q[1]],p[q[2]]));
}
int answer(perm &p,qu q)
{
if (q[3]==-2)
{
int mx=maxx(p,q);
for (int i=0;i<3;i++)
if (mx==p[q[i]])
return q[i];
}
else if(q[3]==-1)
{
int md=-maxx(p,q)-minn(p,q)+p[q[0]]+p[q[1]]+p[q[2]];
for (int i=0;i<3;i++)
if (md==p[q[i]])
return q[i];
}
else if(!q[3])
{
int mn=minn(p,q);
for (int i=0;i<3;i++)
if (mn==p[q[i]])
return q[i];
}
else
{
if (maxx(p,q)<p[q[3]])
{
int mn=minn(p,q);
for (int i=0;i<3;i++)
if (p[q[i]]==mn)
return q[i];
}
int ans=7;
for (int i=0;i<3;i++)
if (p[q[i]]>p[q[3]])
ans=min(ans,p[q[i]]);
for (int i=0;i<3;i++)
if (p[q[i]]==ans)
return q[i];
}
}
state whatif(state &v,qu &q,int ans)
{
state res;
for (perm p:v)
{
if (answer(p,q)==ans)
res.push_back(p);
}
return res;
}
bool solve(state v,int cnt=729)
{
if (v.size()<=1)
return 1;
qu q;
for (q[0]=0;q[0]<6;q[0]++)
for (q[1]=q[0]+1;q[1]<6;q[1]++)
for (q[2]=q[1]+1;q[2]<6;q[2]++)
for (q[3]=-2;q[3]<6;q[3]++)
{
if (q[3]==q[0] or q[3]==q[1] or q[3]==q[2])
continue;
state v1=whatif(v,q,q[0]);
state v2=whatif(v,q,q[1]);
state v3=whatif(v,q,q[2]);
int mx=max(max(v2.size(),v3.size()),v1.size());
if (mx<=cnt/3)
{
bool b=solve(v1,cnt/3) && solve(v2,cnt/3) && solve(v3,cnt/3);
if (b)
{
nxt[v]=q;
return 1;
}
}
}
}
void init(int t)
{
perm a = {0,1,2,3,4,5};
state v;
do
{
v.push_back(a);
}while (next_permutation(a.begin(),a.end()));
solve(v);
}
void orderCoins()
{
perm a = {0,1,2,3,4,5};
state v;
do
{
v.push_back(a);
}while (next_permutation(a.begin(),a.end()));
for (int i=0;i<6;i++)
{
qu q=nxt[v];
if (q[3]==-2)
v=whatif(v,q,getHeaviest(q[0]+1,q[1]+1,q[2]+1)-1);
else if(q[3]==-1)
v=whatif(v,q,getMedian(q[0]+1,q[1]+1,q[2]+1)-1);
else if(!q[3])
v=whatif(v,q,getLightest(q[0]+1,q[1]+1,q[2]+1)-1);
else
{
int ans=getNextLightest(q[0]+1,q[1]+1,q[2]+1,q[3]+1)-1;
v=whatif(v,q,ans);
}
if (v.size()==1)
break;
}
int ans[6];
for (int i=0;i<6;i++)
for (int j=1;j<=6;j++)
if (v[0][j-1]==i)
ans[i]=j;
answer(ans);
}