#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
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 Build(int&, std::vector<int>)':
scales.cpp:130:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(j=0;j<all.size();j++)
~^~~~~~~~~~~
scales.cpp:133:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(i=0;i<tr.size();i++) tmp[all[j].Get(tr[i])].pb(tr[i]);
~^~~~~~~~~~
scales.cpp:134:23: warning: conversion to 'int' from 'std::vector<int>::size_type {aka long unsigned int}' may alter its value [-Wconversion]
if(mymax(tmp[0].size(),tmp[1].size(),tmp[2].size())-mymin(tmp[0].size(),tmp[1].size(),tmp[2].size())<=1)
~~~~~~~~~~~^~
scales.cpp:134:37: warning: conversion to 'int' from 'std::vector<int>::size_type {aka long unsigned int}' may alter its value [-Wconversion]
if(mymax(tmp[0].size(),tmp[1].size(),tmp[2].size())-mymin(tmp[0].size(),tmp[1].size(),tmp[2].size())<=1)
~~~~~~~~~~~^~
scales.cpp:134:51: warning: conversion to 'int' from 'std::vector<int>::size_type {aka long unsigned int}' may alter its value [-Wconversion]
if(mymax(tmp[0].size(),tmp[1].size(),tmp[2].size())-mymin(tmp[0].size(),tmp[1].size(),tmp[2].size())<=1)
~~~~~~~~~~~^~
scales.cpp:134:72: warning: conversion to 'int' from 'std::vector<int>::size_type {aka long unsigned int}' may alter its value [-Wconversion]
if(mymax(tmp[0].size(),tmp[1].size(),tmp[2].size())-mymin(tmp[0].size(),tmp[1].size(),tmp[2].size())<=1)
~~~~~~~~~~~^~
scales.cpp:134:86: warning: conversion to 'int' from 'std::vector<int>::size_type {aka long unsigned int}' may alter its value [-Wconversion]
if(mymax(tmp[0].size(),tmp[1].size(),tmp[2].size())-mymin(tmp[0].size(),tmp[1].size(),tmp[2].size())<=1)
~~~~~~~~~~~^~
scales.cpp:134:100: warning: conversion to 'int' from 'std::vector<int>::size_type {aka long unsigned int}' may alter its value [-Wconversion]
if(mymax(tmp[0].size(),tmp[1].size(),tmp[2].size())-mymin(tmp[0].size(),tmp[1].size(),tmp[2].size())<=1)
~~~~~~~~~~~^~
scales.cpp: In function 'void init(int)':
scales.cpp:160:15: warning: unused parameter 't' [-Wunused-parameter]
void init(int t)
^
scales.cpp: In member function 'int Query::Get(int)':
scales.cpp:105:2: warning: control reaches end of non-void function [-Wreturn-type]
}
^
scales.cpp: In member function 'int Query::Ask()':
scales.cpp:116:2: warning: control reaches end of non-void function [-Wreturn-type]
}
^
scales.cpp: In function 'int Solve(int)':
scales.cpp:115:3: warning: 'ans' may be used uninitialized in this function [-Wmaybe-uninitialized]
if(ans==c) return 2;
^~
scales.cpp:108:7: note: 'ans' was declared here
int ans;
^~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
19 ms |
632 KB |
Output is correct |
2 |
Correct |
20 ms |
632 KB |
Output is correct |
3 |
Correct |
18 ms |
776 KB |
Output is correct |
4 |
Correct |
18 ms |
776 KB |
Output is correct |
5 |
Correct |
20 ms |
1028 KB |
Output is correct |
6 |
Correct |
18 ms |
1028 KB |
Output is correct |
7 |
Correct |
18 ms |
1028 KB |
Output is correct |
8 |
Correct |
21 ms |
1028 KB |
Output is correct |
9 |
Correct |
21 ms |
1028 KB |
Output is correct |
10 |
Correct |
19 ms |
1028 KB |
Output is correct |
11 |
Correct |
19 ms |
1028 KB |
Output is correct |
12 |
Correct |
21 ms |
1028 KB |
Output is correct |
13 |
Correct |
20 ms |
1028 KB |
Output is correct |
14 |
Correct |
20 ms |
1028 KB |
Output is correct |
15 |
Correct |
19 ms |
1028 KB |
Output is correct |
16 |
Correct |
19 ms |
1028 KB |
Output is correct |
17 |
Correct |
19 ms |
1028 KB |
Output is correct |
18 |
Correct |
21 ms |
1028 KB |
Output is correct |
19 |
Correct |
18 ms |
1028 KB |
Output is correct |
20 |
Correct |
20 ms |
1028 KB |
Output is correct |
21 |
Correct |
25 ms |
1028 KB |
Output is correct |
22 |
Correct |
18 ms |
1028 KB |
Output is correct |
23 |
Correct |
19 ms |
1028 KB |
Output is correct |
24 |
Correct |
23 ms |
1028 KB |
Output is correct |
25 |
Correct |
20 ms |
1028 KB |
Output is correct |
26 |
Correct |
19 ms |
1028 KB |
Output is correct |
27 |
Correct |
18 ms |
1028 KB |
Output is correct |
28 |
Correct |
21 ms |
1028 KB |
Output is correct |
29 |
Correct |
18 ms |
1028 KB |
Output is correct |
30 |
Correct |
20 ms |
1028 KB |
Output is correct |
31 |
Correct |
21 ms |
1028 KB |
Output is correct |
32 |
Correct |
18 ms |
1028 KB |
Output is correct |
33 |
Correct |
19 ms |
1028 KB |
Output is correct |
34 |
Correct |
18 ms |
1028 KB |
Output is correct |
35 |
Correct |
21 ms |
1028 KB |
Output is correct |
36 |
Correct |
20 ms |
1028 KB |
Output is correct |
37 |
Correct |
17 ms |
1028 KB |
Output is correct |
38 |
Correct |
18 ms |
1028 KB |
Output is correct |
39 |
Correct |
20 ms |
1028 KB |
Output is correct |
40 |
Correct |
20 ms |
1028 KB |
Output is correct |