#include<bits/stdc++.h>
#include "scales.h"
using namespace std;
vector< vector<int> > active;
vector<int> all;
map< vector< vector<int> >,bool > seen[15];
int maxi(int a,int b,int c)
{
return max(max(a,b),c);
}
int mini(int a,int b,int c)
{
return min(min(a,b),c);
}
int lim[10]={1,3,9,27,81,243,729,2187,6561};
bool can(int tests,vector< vector<int> > &now)
{
//cout<<tests<<" "<<now.size()<<endl;
if(now.size()<=1)return 1;
if(lim[tests]<now.size())return 0;
if(seen[tests].count(now))return seen[tests][now];
for(int i=0;i<6;i++)
for(int j=i+1;j<6;j++)
for(int p=j+1;p<6;p++)
{
vector< vector<int> > a1={},a2={},a3={};
for(auto k:now)
{
if(k[i]>k[j]&&k[i]>k[p])a1.push_back(k);
if(k[j]>k[p]&&k[j]>k[i])a2.push_back(k);
if(k[p]>k[i]&&k[p]>k[j])a3.push_back(k);
}
if(lim[tests-1]<a1.size()||lim[tests-1]<a2.size()||lim[tests-1]<a3.size())continue;
//if(maxi(a1.size(),a2.size(),a3.size())-mini(a1.size(),a2.size(),a3.size())>1)continue;
if(can(tests-1,a1)&&can(tests-1,a2)&&can(tests-1,a3)){seen[tests][now]=1;return 1;}
}
for(int i=0;i<6;i++)
for(int j=i+1;j<6;j++)
for(int p=j+1;p<6;p++)
{
vector< vector<int> > a1={},a2={},a3={};
for(auto k:now)
{
if(k[i]<k[j]&&k[i]<k[p])a1.push_back(k);
if(k[j]<k[p]&&k[j]<k[i])a2.push_back(k);
if(k[p]<k[i]&&k[p]<k[j])a3.push_back(k);
}
if(lim[tests-1]<a1.size()||lim[tests-1]<a2.size()||lim[tests-1]<a3.size())continue;
//if(maxi(a1.size(),a2.size(),a3.size())-mini(a1.size(),a2.size(),a3.size())>1)continue;
if(can(tests-1,a1)&&can(tests-1,a2)&&can(tests-1,a3)){seen[tests][now]=1;return 1;}
}
for(int i=0;i<6;i++)
for(int j=i+1;j<6;j++)
for(int p=j+1;p<6;p++)
{
vector< vector<int> > a1={},a2={},a3={};
for(auto k:now)
{
if((k[i]<k[j])^(k[i]<k[p]))a1.push_back(k);
if((k[j]<k[p])^(k[j]<k[i]))a2.push_back(k);
if((k[p]<k[i])^(k[p]<k[j]))a3.push_back(k);
}
if(lim[tests-1]<a1.size()||lim[tests-1]<a2.size()||lim[tests-1]<a3.size())continue;
//if(maxi(a1.size(),a2.size(),a3.size())-mini(a1.size(),a2.size(),a3.size())>1)continue;
if(can(tests-1,a1)&&can(tests-1,a2)&&can(tests-1,a3)){seen[tests][now]=1;return 1;}
}
for(int i=0;i<6;i++)
for(int j=i+1;j<6;j++)
for(int p=j+1;p<6;p++)
for(int q=0;q<6;q++)
{
if(i==q||j==q||p==q)continue;
vector< vector<int> > a1={},a2={},a3={};
for(auto k:now)
{
int ans=-1;
bool spec=0;
if(k[q]>k[i]&&k[q]>k[j]&&k[q]>k[p])spec=1;
if(spec||k[q]<k[i])
{
if(ans==-1||k[ans]>k[i])ans=i;
}
if(spec||k[q]<k[j])
{
if(ans==-1||k[ans]>k[j])ans=j;
}
if(spec||k[q]<k[p])
{
if(ans==-1||k[ans]>k[p])ans=p;
}
if(ans==i)a1.push_back(k);
if(ans==j)a2.push_back(k);
if(ans==p)a3.push_back(k);
}
if(lim[tests-1]<a1.size()||lim[tests-1]<a2.size()||lim[tests-1]<a3.size())continue;
//if(maxi(a1.size(),a2.size(),a3.size())-mini(a1.size(),a2.size(),a3.size())>1)continue;
if(can(tests-1,a1)&&can(tests-1,a2)&&can(tests-1,a3)){seen[tests][now]=1;return 1;}
}
seen[tests][now]=0;
return 0;
}
int output[6];
void write(int tests,vector< vector<int> > &now)
{
//cout<<tests<<" "<<now.size()<<endl;
if(now.size()<=1)
{
assert(now.size()==1);
for(int i=0;i<6;i++)
{
output[now[0][i]]=i+1;
}
return;
}
//if(seen[tests].count(now))return seen[tests][now];
for(int i=0;i<6;i++)
for(int j=i+1;j<6;j++)
for(int p=j+1;p<6;p++)
{
vector< vector<int> > a1={},a2={},a3={};
for(auto k:now)
{
if(k[i]>k[j]&&k[i]>k[p])a1.push_back(k);
if(k[j]>k[p]&&k[j]>k[i])a2.push_back(k);
if(k[p]>k[i]&&k[p]>k[j])a3.push_back(k);
}
if(lim[tests-1]<a1.size()||lim[tests-1]<a2.size()||lim[tests-1]<a3.size())continue;
//if(maxi(a1.size(),a2.size(),a3.size())-mini(a1.size(),a2.size(),a3.size())>1)continue;
if(can(tests-1,a1)&&can(tests-1,a2)&&can(tests-1,a3))
{
int ans=getHeaviest(i+1,j+1,p+1)-1;
if(i==ans)write(tests-1,a1);
if(j==ans)write(tests-1,a2);
if(p==ans)write(tests-1,a3);
return;
}
}
for(int i=0;i<6;i++)
for(int j=i+1;j<6;j++)
for(int p=j+1;p<6;p++)
{
vector< vector<int> > a1={},a2={},a3={};
for(auto k:now)
{
if(k[i]<k[j]&&k[i]<k[p])a1.push_back(k);
if(k[j]<k[p]&&k[j]<k[i])a2.push_back(k);
if(k[p]<k[i]&&k[p]<k[j])a3.push_back(k);
}
if(lim[tests-1]<a1.size()||lim[tests-1]<a2.size()||lim[tests-1]<a3.size())continue;
//if(maxi(a1.size(),a2.size(),a3.size())-mini(a1.size(),a2.size(),a3.size())>1)continue;
if(can(tests-1,a1)&&can(tests-1,a2)&&can(tests-1,a3))
{
int ans=getLightest(i+1,j+1,p+1)-1;
if(i==ans)write(tests-1,a1);
if(j==ans)write(tests-1,a2);
if(p==ans)write(tests-1,a3);
return;
}
}
for(int i=0;i<6;i++)
for(int j=i+1;j<6;j++)
for(int p=j+1;p<6;p++)
{
vector< vector<int> > a1={},a2={},a3={};
for(auto k:now)
{
if((k[i]<k[j])^(k[i]<k[p]))a1.push_back(k);
if((k[j]<k[p])^(k[j]<k[i]))a2.push_back(k);
if((k[p]<k[i])^(k[p]<k[j]))a3.push_back(k);
}
if(lim[tests-1]<a1.size()||lim[tests-1]<a2.size()||lim[tests-1]<a3.size())continue;
//if(maxi(a1.size(),a2.size(),a3.size())-mini(a1.size(),a2.size(),a3.size())>1)continue;
if(can(tests-1,a1)&&can(tests-1,a2)&&can(tests-1,a3))
{
int ans=getMedian(i+1,j+1,p+1)-1;
if(i==ans)write(tests-1,a1);
if(j==ans)write(tests-1,a2);
if(p==ans)write(tests-1,a3);
return;
}
}
for(int i=0;i<6;i++)
for(int j=i+1;j<6;j++)
for(int p=j+1;p<6;p++)
for(int q=0;q<6;q++)
{
if(i==q||j==q||p==q)continue;
vector< vector<int> > a1={},a2={},a3={};
for(auto k:now)
{
int ans=-1;
bool spec=0;
if(k[q]>k[i]&&k[q]>k[j]&&k[q]>k[p])spec=1;
if(spec||k[q]<k[i])
{
if(ans==-1||k[ans]>k[i])ans=i;
}
if(spec||k[q]<k[j])
{
if(ans==-1||k[ans]>k[j])ans=j;
}
if(spec||k[q]<k[p])
{
if(ans==-1||k[ans]>k[p])ans=p;
}
if(ans==i)a1.push_back(k);
if(ans==j)a2.push_back(k);
if(ans==p)a3.push_back(k);
}
if(lim[tests-1]<a1.size()||lim[tests-1]<a2.size()||lim[tests-1]<a3.size())continue;
//if(maxi(a1.size(),a2.size(),a3.size())-mini(a1.size(),a2.size(),a3.size())>1)continue;
if(can(tests-1,a1)&&can(tests-1,a2)&&can(tests-1,a3))
{
int ans=getNextLightest(i+1,j+1,p+1,q+1)-1;
if(i==ans)write(tests-1,a1);
if(j==ans)write(tests-1,a2);
if(p==ans)write(tests-1,a3);
return;
}
}
assert(0==1);
}
void init(int T)
{
all={};
for(int i=0;i<=5;i++)
all.push_back(i);
active={};
do
{
active.push_back(all);
}
while(next_permutation(all.begin(),all.end()));
//assert(can(7,active));
assert(can(6,active));
}
void orderCoins()
{
all={};
for(int i=0;i<=5;i++)
all.push_back(i);
active={};
do
{
active.push_back(all);
}
while(next_permutation(all.begin(),all.end()));
write(6,active);
answer(output);
//write(8,active);
}
/*
int main()
{
init(12);
orderCoins();
}
*/
Compilation message
In file included from grader.c:2:0:
graderlib.c: In function 'void answer(int*)':
graderlib.c:53:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
if (_ghksjhdfkae19ga_ > 1)
^~
graderlib.c:56:2: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
for (i = 0; i < 6; i++) {
^~~
scales.cpp: In function 'bool can(int, std::vector<std::vector<int> >&)':
scales.cpp:22:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(lim[tests]<now.size())return 0;
~~~~~~~~~~^~~~~~~~~~~
scales.cpp:36:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(lim[tests-1]<a1.size()||lim[tests-1]<a2.size()||lim[tests-1]<a3.size())continue;
~~~~~~~~~~~~^~~~~~~~~~
scales.cpp:36:48: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(lim[tests-1]<a1.size()||lim[tests-1]<a2.size()||lim[tests-1]<a3.size())continue;
~~~~~~~~~~~~^~~~~~~~~~
scales.cpp:36:72: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(lim[tests-1]<a1.size()||lim[tests-1]<a2.size()||lim[tests-1]<a3.size())continue;
~~~~~~~~~~~~^~~~~~~~~~
scales.cpp:52:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(lim[tests-1]<a1.size()||lim[tests-1]<a2.size()||lim[tests-1]<a3.size())continue;
~~~~~~~~~~~~^~~~~~~~~~
scales.cpp:52:48: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(lim[tests-1]<a1.size()||lim[tests-1]<a2.size()||lim[tests-1]<a3.size())continue;
~~~~~~~~~~~~^~~~~~~~~~
scales.cpp:52:72: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(lim[tests-1]<a1.size()||lim[tests-1]<a2.size()||lim[tests-1]<a3.size())continue;
~~~~~~~~~~~~^~~~~~~~~~
scales.cpp:68:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(lim[tests-1]<a1.size()||lim[tests-1]<a2.size()||lim[tests-1]<a3.size())continue;
~~~~~~~~~~~~^~~~~~~~~~
scales.cpp:68:48: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(lim[tests-1]<a1.size()||lim[tests-1]<a2.size()||lim[tests-1]<a3.size())continue;
~~~~~~~~~~~~^~~~~~~~~~
scales.cpp:68:72: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(lim[tests-1]<a1.size()||lim[tests-1]<a2.size()||lim[tests-1]<a3.size())continue;
~~~~~~~~~~~~^~~~~~~~~~
scales.cpp:103:28: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(lim[tests-1]<a1.size()||lim[tests-1]<a2.size()||lim[tests-1]<a3.size())continue;
~~~~~~~~~~~~^~~~~~~~~~
scales.cpp:103:52: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(lim[tests-1]<a1.size()||lim[tests-1]<a2.size()||lim[tests-1]<a3.size())continue;
~~~~~~~~~~~~^~~~~~~~~~
scales.cpp:103:76: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(lim[tests-1]<a1.size()||lim[tests-1]<a2.size()||lim[tests-1]<a3.size())continue;
~~~~~~~~~~~~^~~~~~~~~~
scales.cpp:73:1: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
for(int i=0;i<6;i++)
^~~
scales.cpp:108:5: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
seen[tests][now]=0;
^~~~
scales.cpp: In function 'void write(int, std::vector<std::vector<int> >&)':
scales.cpp:138:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(lim[tests-1]<a1.size()||lim[tests-1]<a2.size()||lim[tests-1]<a3.size())continue;
~~~~~~~~~~~~^~~~~~~~~~
scales.cpp:138:48: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(lim[tests-1]<a1.size()||lim[tests-1]<a2.size()||lim[tests-1]<a3.size())continue;
~~~~~~~~~~~~^~~~~~~~~~
scales.cpp:138:72: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(lim[tests-1]<a1.size()||lim[tests-1]<a2.size()||lim[tests-1]<a3.size())continue;
~~~~~~~~~~~~^~~~~~~~~~
scales.cpp:161:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(lim[tests-1]<a1.size()||lim[tests-1]<a2.size()||lim[tests-1]<a3.size())continue;
~~~~~~~~~~~~^~~~~~~~~~
scales.cpp:161:48: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(lim[tests-1]<a1.size()||lim[tests-1]<a2.size()||lim[tests-1]<a3.size())continue;
~~~~~~~~~~~~^~~~~~~~~~
scales.cpp:161:72: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(lim[tests-1]<a1.size()||lim[tests-1]<a2.size()||lim[tests-1]<a3.size())continue;
~~~~~~~~~~~~^~~~~~~~~~
scales.cpp:184:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(lim[tests-1]<a1.size()||lim[tests-1]<a2.size()||lim[tests-1]<a3.size())continue;
~~~~~~~~~~~~^~~~~~~~~~
scales.cpp:184:48: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(lim[tests-1]<a1.size()||lim[tests-1]<a2.size()||lim[tests-1]<a3.size())continue;
~~~~~~~~~~~~^~~~~~~~~~
scales.cpp:184:72: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(lim[tests-1]<a1.size()||lim[tests-1]<a2.size()||lim[tests-1]<a3.size())continue;
~~~~~~~~~~~~^~~~~~~~~~
scales.cpp:226:28: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(lim[tests-1]<a1.size()||lim[tests-1]<a2.size()||lim[tests-1]<a3.size())continue;
~~~~~~~~~~~~^~~~~~~~~~
scales.cpp:226:52: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(lim[tests-1]<a1.size()||lim[tests-1]<a2.size()||lim[tests-1]<a3.size())continue;
~~~~~~~~~~~~^~~~~~~~~~
scales.cpp:226:76: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(lim[tests-1]<a1.size()||lim[tests-1]<a2.size()||lim[tests-1]<a3.size())continue;
~~~~~~~~~~~~^~~~~~~~~~
scales.cpp: In function 'void init(int)':
scales.cpp:241:15: warning: unused parameter 'T' [-Wunused-parameter]
void init(int T)
^
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
126 ms |
760 KB |
Output is correct |
2 |
Correct |
104 ms |
1004 KB |
Output is correct |
3 |
Correct |
115 ms |
1004 KB |
Output is correct |
4 |
Correct |
122 ms |
1004 KB |
Output is correct |
5 |
Correct |
105 ms |
1120 KB |
Output is correct |
6 |
Correct |
120 ms |
1120 KB |
Output is correct |
7 |
Correct |
104 ms |
1120 KB |
Output is correct |
8 |
Correct |
130 ms |
1120 KB |
Output is correct |
9 |
Correct |
119 ms |
1120 KB |
Output is correct |
10 |
Correct |
113 ms |
1120 KB |
Output is correct |
11 |
Correct |
121 ms |
1120 KB |
Output is correct |
12 |
Correct |
115 ms |
1120 KB |
Output is correct |
13 |
Correct |
117 ms |
1120 KB |
Output is correct |
14 |
Correct |
118 ms |
1120 KB |
Output is correct |
15 |
Correct |
119 ms |
1120 KB |
Output is correct |
16 |
Correct |
117 ms |
1120 KB |
Output is correct |
17 |
Correct |
109 ms |
1120 KB |
Output is correct |
18 |
Correct |
112 ms |
1120 KB |
Output is correct |
19 |
Correct |
119 ms |
1120 KB |
Output is correct |
20 |
Correct |
122 ms |
1120 KB |
Output is correct |
21 |
Correct |
119 ms |
1120 KB |
Output is correct |
22 |
Correct |
125 ms |
1120 KB |
Output is correct |
23 |
Correct |
102 ms |
1120 KB |
Output is correct |
24 |
Correct |
141 ms |
1120 KB |
Output is correct |
25 |
Correct |
128 ms |
1120 KB |
Output is correct |
26 |
Correct |
118 ms |
1120 KB |
Output is correct |
27 |
Correct |
125 ms |
1120 KB |
Output is correct |
28 |
Correct |
120 ms |
1120 KB |
Output is correct |
29 |
Correct |
129 ms |
1132 KB |
Output is correct |
30 |
Correct |
130 ms |
1132 KB |
Output is correct |
31 |
Correct |
130 ms |
1132 KB |
Output is correct |
32 |
Correct |
116 ms |
1132 KB |
Output is correct |
33 |
Correct |
107 ms |
1132 KB |
Output is correct |
34 |
Correct |
107 ms |
1132 KB |
Output is correct |
35 |
Correct |
112 ms |
1132 KB |
Output is correct |
36 |
Correct |
116 ms |
1132 KB |
Output is correct |
37 |
Correct |
118 ms |
1132 KB |
Output is correct |
38 |
Correct |
137 ms |
1132 KB |
Output is correct |
39 |
Correct |
108 ms |
1132 KB |
Output is correct |
40 |
Correct |
126 ms |
1132 KB |
Output is correct |