#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)
{
/*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));
random_shuffle(prior.begin(),prior.end());
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
scales.cpp: In member function 'bool perm::operator<(const perm&) const':
scales.cpp:27:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
27 | for(int j=0;j<p.size();j++)
| ~^~~~~~~~~
scales.cpp: In function 'std::vector<int> calc(std::vector<int>)':
scales.cpp:60:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<queryL>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
60 | for(int i=0;i<vl.size();i++)
| ~^~~~~~~~~~
scales.cpp:76:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<queryH>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
76 | for(int i=0;i<vh.size();i++)
| ~^~~~~~~~~~
scales.cpp:92:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<queryM>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
92 | for(int i=0;i<vm.size();i++)
| ~^~~~~~~~~~
scales.cpp:108:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<queryS>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
108 | for(int i=0;i<vs.size();i++)
| ~^~~~~~~~~~
scales.cpp:116:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
116 | for(int j=0;j<f.size();j++)
| ~^~~~~~~~~
scales.cpp: In function 'void init(int)':
scales.cpp:133:15: warning: unused parameter 'T' [-Wunused-parameter]
133 | void init(int T) {
| ~~~~^
scales.cpp: In function 'void orderCoins()':
scales.cpp:203:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
203 | for(int j=0;j<xd.answers.size();j++)
| ~^~~~~~~~~~~~~~~~~~
scales.cpp:223:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<queryL>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
223 | for(int j=0;j<vl.size();j++)
| ~^~~~~~~~~~
scales.cpp:250:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<queryH>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
250 | for(int j=0;j<vh.size();j++)
| ~^~~~~~~~~~
scales.cpp:277:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<queryM>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
277 | for(int j=0;j<vm.size();j++)
| ~^~~~~~~~~~
scales.cpp:304:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<queryS>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
304 | for(int j=0;j<vs.size();j++)
| ~^~~~~~~~~~
scales.cpp:334:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
334 | for(int i=0;i<(*ico.begin()).p.size();i++)
| ~^~~~~~~~~~~~~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
27 ms |
1388 KB |
Output is correct |
2 |
Correct |
33 ms |
1388 KB |
Output is correct |
3 |
Partially correct |
27 ms |
1388 KB |
Output is partially correct |
4 |
Correct |
27 ms |
1388 KB |
Output is correct |
5 |
Correct |
28 ms |
1536 KB |
Output is correct |
6 |
Correct |
28 ms |
1388 KB |
Output is correct |
7 |
Correct |
27 ms |
1388 KB |
Output is correct |
8 |
Correct |
28 ms |
1516 KB |
Output is correct |
9 |
Correct |
28 ms |
1388 KB |
Output is correct |
10 |
Correct |
28 ms |
1388 KB |
Output is correct |
11 |
Correct |
28 ms |
1388 KB |
Output is correct |
12 |
Partially correct |
28 ms |
1388 KB |
Output is partially correct |
13 |
Correct |
27 ms |
1388 KB |
Output is correct |
14 |
Correct |
28 ms |
1388 KB |
Output is correct |
15 |
Partially correct |
27 ms |
1388 KB |
Output is partially correct |
16 |
Partially correct |
28 ms |
1388 KB |
Output is partially correct |
17 |
Correct |
27 ms |
1388 KB |
Output is correct |
18 |
Correct |
27 ms |
1388 KB |
Output is correct |
19 |
Partially correct |
28 ms |
1388 KB |
Output is partially correct |
20 |
Partially correct |
27 ms |
1388 KB |
Output is partially correct |
21 |
Partially correct |
28 ms |
1388 KB |
Output is partially correct |
22 |
Partially correct |
28 ms |
1388 KB |
Output is partially correct |
23 |
Partially correct |
27 ms |
1388 KB |
Output is partially correct |
24 |
Correct |
28 ms |
1388 KB |
Output is correct |
25 |
Correct |
27 ms |
1516 KB |
Output is correct |
26 |
Correct |
28 ms |
1388 KB |
Output is correct |
27 |
Partially correct |
28 ms |
1388 KB |
Output is partially correct |
28 |
Correct |
27 ms |
1388 KB |
Output is correct |
29 |
Correct |
28 ms |
1388 KB |
Output is correct |
30 |
Correct |
29 ms |
1516 KB |
Output is correct |
31 |
Correct |
28 ms |
1388 KB |
Output is correct |
32 |
Correct |
27 ms |
1388 KB |
Output is correct |
33 |
Partially correct |
28 ms |
1388 KB |
Output is partially correct |
34 |
Correct |
27 ms |
1388 KB |
Output is correct |
35 |
Partially correct |
28 ms |
1388 KB |
Output is partially correct |
36 |
Partially correct |
28 ms |
1388 KB |
Output is partially correct |
37 |
Correct |
27 ms |
1388 KB |
Output is correct |
38 |
Partially correct |
28 ms |
1388 KB |
Output is partially correct |
39 |
Partially correct |
28 ms |
1388 KB |
Output is partially correct |
40 |
Partially correct |
28 ms |
1388 KB |
Output is partially correct |