| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 341262 | ogibogi2004 | Scales (IOI15_scales) | C++14 | 29 ms | 1516 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<bits/stdc++.h>
using namespace std;
#define prior safdsf
struct queryL
{
int a,b,c;
};
struct queryH
{
int a,b,c;
};
struct queryM
{
int a,b,c;
};
struct queryS
{
int a,b,c,d;
};
struct perm
{
vector<int>p;
vector<int>answers;
bool operator<(perm const& other)const
{
for(int j=0;j<p.size();j++)
{
if(p[j]!=other.p[j])return p[j]<other.p[j];
}
return 1;
}
};
vector<perm>ivan;
vector<queryL>vl;
vector<queryH>vh;
vector<queryM>vm;
vector<queryS>vs;
set<perm>ico,hristo;
int all_queries;
int ask(queryL q)
{
return getLightest(q.a+1,q.b+1,q.c+1);
}
int ask(queryH q)
{
return getHeaviest(q.a+1,q.b+1,q.c+1);
}
int ask(queryM q)
{
return getMedian(q.a+1,q.b+1,q.c+1);
}
int ask(queryS q)
{
return getNextLightest(q.a+1,q.b+1,q.c+1,q.d+1);
}
vector<int> calc(vector<int> p)
{
vector<int>ret;
for(int i=0;i<vl.size();i++)
{
if(p[vl[i].a]>p[vl[i].b]&&p[vl[i].c]>p[vl[i].b])
{
ret.push_back(vl[i].b);
}
else if(p[vl[i].a]>p[vl[i].c]&&p[vl[i].b]>p[vl[i].c])
{
ret.push_back(vl[i].c);
}
else if(p[vl[i].b]>p[vl[i].a]&&p[vl[i].c]>p[vl[i].a])
{
ret.push_back(vl[i].a);
}
}
for(int i=0;i<vh.size();i++)
{
if(p[vh[i].a]<p[vh[i].b]&&p[vh[i].c]<p[vh[i].b])
{
ret.push_back(vh[i].b);
}
else if(p[vh[i].a]<p[vh[i].c]&&p[vh[i].b]<p[vh[i].c])
{
ret.push_back(vh[i].c);
}
else if(p[vh[i].b]<p[vh[i].a]&&p[vh[i].c]<p[vh[i].a])
{
ret.push_back(vh[i].a);
}
}
for(int i=0;i<vm.size();i++)
{
if((p[vm[i].a]<p[vm[i].b])^(p[vm[i].c]<p[vm[i].b]))
{
ret.push_back(vm[i].b);
}
else if((p[vm[i].a]<p[vm[i].c])^(p[vm[i].b]<p[vm[i].c]))
{
ret.push_back(vm[i].c);
}
else if((p[vm[i].b]<p[vm[i].a])^(p[vm[i].c]<p[vm[i].a]))
{
ret.push_back(vm[i].a);
}
}
for(int i=0;i<vs.size();i++)
{
vector<pair<int,int> >f;
f.push_back({p[vs[i].a],vs[i].a});
f.push_back({p[vs[i].b],vs[i].b});
f.push_back({p[vs[i].c],vs[i].c});
sort(f.begin(),f.end());
bool flag=0;
for(int j=0;j<f.size();j++)
{
if(f[j].first>p[vs[i].d])
{
ret.push_back(f[j].second);
flag=1;
break;
}
}
if(!flag)
{
ret.push_back(f[0].second);
}
}
return ret;
}
void init(int T) {
/* ... */
for(int i1=0;i1<6;i1++)
{
for(int i2=i1+1;i2<6;i2++)
{
for(int i3=i2+1;i3<6;i3++)
{
vl.push_back({i1,i2,i3});
vh.push_back({i1,i2,i3});
vm.push_back({i1,i2,i3});
all_queries+=3;
for(int j=0;j<6;j++)
{
if(j==i1)continue;
if(j==i2)continue;
if(j==i3)continue;
vs.push_back({i1,i2,i3,j});
all_queries++;
}
}
}
}
//cout<<vl.size()<<" "<<vh.size()<<" "<<vm.size()<<" "<<vs.size()<<endl;
vector<int>p;
p={1,2,3,4,5,6};
do
{
vector<int>answers=calc(p);
ivan.push_back({p,answers});
}while(next_permutation(p.begin(),p.end()));
}
int cnt[1024][8];
vector<int>prior;
void orderCoins() {
srand(32432);
/* ... */
ico.clear();
prior.clear();
for(int i=0;i<all_queries;i++)prior.push_back(i);
for(auto oof:ivan)
{
ico.insert(oof);
}
while(ico.size()>1)
{
random_shuffle(prior.begin(),prior.end());
/*cout<<ico.size()<<endl;
if(ico.size()==3)
{
for(auto xd:ico)
{
for(int j=0;j<xd.p.size();j++)cout<<xd.p[j]<<" ";
cout<<endl;
for(int j=0;j<xd.answers.size();j++)
{
cout<<xd.answers[j];
}
cout<<endl;
for(int j=0;j<vl.size();j++)
{
cout<<vl[j].a<<" "<<vl[j].b<<" "<<vl[j].c<<" "<<xd.answers[j]<<endl;
}
}
}
if(ico.size()==6)break;*/
hristo.clear();
memset(cnt,0,sizeof(cnt));
for(auto xd:ico)
{
for(int j=0;j<xd.answers.size();j++)
{
cnt[j][xd.answers[j]]++;
}
}
pair<int,int> minmax={10000,100000};
for(int j=0;j<all_queries;j++)
{
int t=0;
t=max(cnt[j][0],t);
t=max(cnt[j][1],t);
t=max(cnt[j][2],t);
t=max(cnt[j][3],t);
t=max(cnt[j][4],t);
t=max(cnt[j][5],t);
t=max(cnt[j][6],t);
minmax=min(minmax,{t,prior[j]});
}
int i=0;
bool flag=0;
for(int j=0;j<vl.size();j++)
{
int t=0;
t=max(cnt[i][0],t);
t=max(cnt[i][1],t);
t=max(cnt[i][2],t);
t=max(cnt[i][3],t);
t=max(cnt[i][4],t);
t=max(cnt[i][5],t);
t=max(cnt[i][6],t);
if(make_pair(t,prior[i])==minmax)
{
int r=ask(vl[j])-1;
for(auto xd:ico)
{
if(xd.answers[i]==r)
{
hristo.insert(xd);
}
}
ico=hristo;
flag=1;
break;
}
i++;
}
if(flag)continue;
for(int j=0;j<vh.size();j++)
{
int t=0;
t=max(cnt[i][0],t);
t=max(cnt[i][1],t);
t=max(cnt[i][2],t);
t=max(cnt[i][3],t);
t=max(cnt[i][4],t);
t=max(cnt[i][5],t);
t=max(cnt[i][6],t);
if(make_pair(t,prior[i])==minmax)
{
int r=ask(vh[j])-1;
for(auto xd:ico)
{
if(xd.answers[i]==r)
{
hristo.insert(xd);
}
}
ico=hristo;
flag=1;
break;
}
i++;
}
if(flag)continue;
for(int j=0;j<vm.size();j++)
{
int t=0;
t=max(cnt[i][0],t);
t=max(cnt[i][1],t);
t=max(cnt[i][2],t);
t=max(cnt[i][3],t);
t=max(cnt[i][4],t);
t=max(cnt[i][5],t);
t=max(cnt[i][6],t);
if(make_pair(t,prior[i])==minmax)
{
int r=ask(vm[j])-1;
for(auto xd:ico)
{
if(xd.answers[i]==r)
{
hristo.insert(xd);
}
}
ico=hristo;
flag=1;
break;
}
i++;
}
if(flag)continue;
for(int j=0;j<vs.size();j++)
{
int t=0;
t=max(cnt[i][0],t);
t=max(cnt[i][1],t);
t=max(cnt[i][2],t);
t=max(cnt[i][3],t);
t=max(cnt[i][4],t);
t=max(cnt[i][5],t);
t=max(cnt[i][6],t);
if(make_pair(t,prior[i])==minmax)
{
int r=ask(vs[j])-1;
for(auto xd:ico)
{
if(xd.answers[i]==r)
{
hristo.insert(xd);
}
}
ico=hristo;
flag=1;
break;
}
i++;
}
if(flag)continue;
}
//cout<<ico.size()<<endl;
int W[6];
for(int i=0;i<(*ico.begin()).p.size();i++)
{
//cout<<(*ico.begin()).p[i]<<" ";
W[(*ico.begin()).p[i]-1]=i+1;
}
//cout<<endl;
//for(int i=0;i<6;i++)cout<<W[i]<<" ";
//cout<<endl;
answer(W);
}
Compilation message (stderr)
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| Fetching results... | ||||