| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 59582 | TadijaSebez | Scales (IOI15_scales) | C++11 | 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 "scales.h"
#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;
#define pb push_back
int per[720][6],id[7];
int max(int a, int b){ return a>b?a:b;}
int min(int a, int b){ return a>b?b:a;}
int max(int a, int b, int c){ return max(a,max(b,c));}
int min(int a, int b, int c){ return min(a,min(b,c));}
struct Query
{
int t,a,b,c,d;
Query(){}
Query(int _t, int _a, int _b, int _c, int _d){ t=_t,a=_a,b=_b,c=_c,d=_d;}
int Get(int j)
{
int i;
for(i=0;i<7;i++) id[per[j][i]]=i;
if(t==1) //getHeaviest();
{
if(id[a]>id[b] && id[a]>id[c]) return 0;
if(id[b]>id[a] && id[b]>id[c]) return 1;
if(id[c]>id[a] && id[c]>id[b]) return 2;
}
else if(t==2) //getLightest();
{
if(id[a]<id[b] && id[a]<id[c]) return 0;
if(id[b]<id[a] && id[b]<id[c]) return 1;
if(id[c]<id[a] && id[c]<id[b]) return 2;
}
else if(t==3) //getMedian();
{
if(id[a]>min(id[b],id[c]) && id[a]<max(id[b],id[c])) return 0;
if(id[b]>min(id[a],id[c]) && id[b]<max(id[a],id[c])) return 1;
if(id[c]>min(id[a],id[b]) && id[c]<max(id[a],id[b])) return 2;
}
else if(t==4) //getNextLightest();
{
if(id[a]>id[d] && (id[d]>id[b] || id[b]>id[a]) && (id[d]>id[c] || id[c]>id[a])) return 0;
if(id[b]>id[d] && (id[d]>id[a] || id[a]>id[b]) && (id[d]>id[c] || id[c]>id[b])) return 1;
if(id[c]>id[d] && (id[d]>id[a] || id[a]>id[c]) && (id[d]>id[b] || id[b]>id[c])) return 2;
if(id[a]>id[b] && id[a]>id[c]) return 0;
if(id[b]>id[a] && id[b]>id[c]) return 1;
if(id[c]>id[a] && id[c]>id[b]) return 2;
}
}
int Ask()
{
int ans;
if(t==1) ans=getHeaviest(a,b,c);
if(t==2) ans=getLightest(a,b,c);
if(t==3) ans=getMedian(a,b,c);
if(t==4) ans=getNextLightest(a,b,c,d);
if(ans==a) return 0;
if(ans==b) return 1;
if(ans==c) return 2;
}
};
vector<Query> all;
const int N=10050;
int go[N][3],tsz,root;
Query my[N];
vector<int> work[N];
bool Build(int &c, vector<int> tr)
{
c=++tsz;
work[c]=tr;
if(tr.size()<=1) return 1;
int i,j;
vector<int> tmp[3];
for(j=0;j<all.size();j++)
{
tmp[0].clear();tmp[1].clear();tmp[2].clear();
for(i=0;i<tr.size();i++) tmp[all[j].Get(tr[i])].pb(tr[i]);
if(max(tmp[0].size(),tmp[1].size(),tmp[2].size())-min(tmp[0].size(),tmp[1].size(),tmp[2].size())<=1)
{
if(Build(go[c][0],tmp[0]) && Build(go[c][1],tmp[1]) && Build(go[c][2],tmp[2]))
{
my[c]=all[j];
return 1;
}
else tsz=c;
}
}
return 0;
}
int Solve(int c)
{
if(work[c].size()<=1) return work[c][0];
return Solve(go[c][my[c].Ask()]);
}
void init(int t)
{
int i,j,k,l;
for(i=0;i<6;i++) per[0][i]=i+1;
for(j=1;j<720;j++)
{
for(i=0;i<6;i++) per[j][i]=per[j-1][i];
next_permutation(per[j],per[j]+6);
}
for(i=1;i<=6;i++)
{
for(j=i+1;j<=6;j++)
{
for(k=j+1;k<=6;k++)
{
all.pb(Query(1,i,j,k,0));
all.pb(Query(2,i,j,k,0));
all.pb(Query(3,i,j,k,0));
for(l=1;l<=6;l++)
{
if(l!=i && l!=j && l!=k)
{
all.pb(Query(4,i,j,k,l));
}
}
}
}
}
vector<int> tmp;
for(i=0;i<720;i++) tmp.pb(i);
Build(root,tmp);
}
int ret[6];
void orderCoins()
{
int p=Solve(root);
for(int i=0;i<6;i++) ret[i]=per[p][i];
answer(ret);
}