| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 59586 | TadijaSebez | Scales (IOI15_scales) | C++11 | 25 ms | 1028 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 mymax(int a, int b, int c){ return max(a,max(b,c));}
int mymin(int a, int b, int c){ return min(a,min(b,c));}
//-------------------------//
/*
int S[6];
int getHeaviest(int a, int b, int c)
{
printf("1 %i %i %i\n",a,b,c);
for(int i=0;i<6;i++) id[S[i]]=i;
if(id[a]>id[b] && id[a]>id[c]) return a;
return id[b]>id[c]?b:c;
}
int getLightest(int a, int b, int c)
{
printf("2 %i %i %i\n",a,b,c);
for(int i=0;i<6;i++) id[S[i]]=i;
if(id[a]<id[b] && id[a]<id[c]) return a;
return id[b]<id[c]?b:c;
}
int getMedian(int a, int b, int c)
{
printf("3 %i %i %i\n",a,b,c);
for(int i=0;i<6;i++) id[S[i]]=i;
if(id[a]<id[b])
{
if(id[c]<id[a]) return a;
return id[b]<id[c]?b:c;
}
else
{
if(id[c]>id[a]) return a;
return id[b]>id[c]?b:c;
}
}
int getNextLightest(int a, int b, int c, int d)
{
printf("4 %i %i %i %i\n",a,b,c,d);
for(int i=0;i<6;i++) id[S[i]]=i;
if(id[a]<id[d]) id[a]+=7;
if(id[b]<id[d]) id[b]+=7;
if(id[c]<id[d]) id[c]+=7;
if(id[a]<id[b] && id[a]<id[c]) return a;
return id[b]<id[c]?b:c;
}
void answer(int a[])
{
bool ok=1;
int i;
for(i=0;i<6;i++) if(a[i]!=S[i]) ok=0;
if(ok) printf("OK\n");
else printf("WA\n");
for(i=0;i<6;i++) printf("%i ",a[i]);
}
*/
//-------------------------//
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<6;i++) id[per[j][i]]=i;
if(t==1) //getHeaviest();
{
if(id[a]>id[b] && id[a]>id[c]) return 0;
return id[b]>id[c]?1:2;
}
else if(t==2) //getLightest();
{
if(id[a]<id[b] && id[a]<id[c]) return 0;
return id[b]<id[c]?1:2;
}
else if(t==3) //getMedian();
{
if(id[a]<id[b])
{
if(id[c]<id[a]) return 0;
return id[b]<id[c]?1:2;
}
else
{
if(id[c]>id[a]) return 0;
return id[b]>id[c]?1:2;
}
}
else if(t==4) //getNextLightest();
{
if(id[a]<id[d]) id[a]+=7;
if(id[b]<id[d]) id[b]+=7;
if(id[c]<id[d]) id[c]+=7;
if(id[a]<id[b] && id[a]<id[c]) return 0;
return id[b]<id[c]?1: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,cnt;
Query my[N];
vector<int> work[N];
bool Build(int &c, vector<int> tr)
{
c=++tsz;
if(tr.size()<=1){ work[c]=tr;return 1;}
cnt++;
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(mymax(tmp[0].size(),tmp[1].size(),tmp[2].size())-mymin(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];
work[c]=tr;
return 1;
}
else tsz=c;
}
}
return 0;
}
int Solve(int c)
{
/*printf("Node: %i\n",c);
for(int i=0;i<work[c].size();i++)
{
for(int j=0;j<6;j++) printf("%i ",per[work[c][i]][j]);
printf("\n");
}*/
if(work[c].size()<=1) return work[c][0];
int nxt=my[c].Ask();
//printf("%i\n",nxt);
return Solve(go[c][nxt]);
}
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);
if(!Build(root,tmp)) printf("???\n");
}
int ret[6];
void orderCoins()
{
int p=Solve(root);
for(int i=0;i<6;i++) ret[i]=per[p][i];
answer(ret);
}
//-------------------------//
/*
int main()
{
init(1);
int i;
for(i=0;i<6;i++) scanf("%i",&S[i]);
orderCoins();
return 0;
}
*/
//-------------------------//
Compilation message (stderr)
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| Fetching results... | ||||