#include "scales.h"
#include <stdio.h>
#include <algorithm>
#include <vector>
#define M 6
using namespace std;
struct TestCase{
int a[M+1];
} t[720];
struct Node{
vector<TestCase> cd;
Node *chi[3];
int ct,cp[4];
} *rt;
int tn;
void makeTestCase(int lev,int ch,int x[]){
if(lev>=M){
int i;
for(i=0;i<M;i++){
t[tn].a[x[i]]=i;
}
tn++;
}else{
int i;
for(i=1;i<=M;i++){
if(!(ch&(1<<i))){
x[lev]=i;
makeTestCase(lev+1,ch+(1<<i),x);
}
}
}
}
int mget(int fn,TestCase tc,int x,int y,int z){
if(fn==0){
if(tc.a[x]>tc.a[y] && tc.a[x]>tc.a[z]) return x;
if(tc.a[y]>tc.a[z]) return y;
return z;
}else if(fn==1){
if(tc.a[x]<tc.a[y] && tc.a[x]<tc.a[z]) return x;
if(tc.a[y]<tc.a[z]) return y;
return z;
}else if(fn==2){
return x+y+z-mget(0,tc,x,y,z)-mget(1,tc,x,y,z);
}
}
int m4th(TestCase tc,int x,int y,int z,int w){
if(tc.a[x]>tc.a[y]) swap(x,y);
if(tc.a[y]>tc.a[z]) swap(y,z);
if(tc.a[x]>tc.a[y]) swap(x,y);
if(tc.a[w]<tc.a[x]) return x;
if(tc.a[w]<tc.a[y]) return y;
if(tc.a[w]<tc.a[z]) return z;
return x;
}
bool makeTestTree(Node *no){
int i,j,k,m,in,jn,kn,p;
if(no->cd.size()<=1) return true;
for(i=1;i<=M-2;i++){
for(j=i+1;j<=M-1;j++){
for(k=j+1;k<=M;k++){
for(p=0;p<3;p++){
in=jn=kn=0;
for(m=0;m<no->cd.size();m++){
int ret=mget(p,no->cd[m],i,j,k);
if(ret==i){
in++;
}else if(ret==j){
jn++;
}else{
kn++;
}
}
if(abs(in-jn)<2 && abs(jn-kn)<2 && abs(kn-in)<2){
for(m=0;m<3;m++) no->chi[m]=new Node();
for(m=0;m<no->cd.size();m++){
int ret=mget(p,no->cd[m],i,j,k);
if(ret==i){
no->chi[0]->cd.push_back(no->cd[m]);
}else if(ret==j){
no->chi[1]->cd.push_back(no->cd[m]);
}else{
no->chi[2]->cd.push_back(no->cd[m]);
}
}
for(m=0;m<3;m++) if(!makeTestTree(no->chi[m])) break;
if(m==3){
no->ct=p;
no->cp[0]=i;
no->cp[1]=j;
no->cp[2]=k;
return true;
}
}
}
for(p=1;p<=M;p++){
if(p!=i && p!=j && p!=k){
in=jn=kn=0;
for(m=0;m<no->cd.size();m++){
int ret=m4th(no->cd[m],i,j,k,p);
if(ret==i){
in++;
}else if(ret==j){
jn++;
}else{
kn++;
}
}
if(abs(in-jn)<2 && abs(jn-kn)<2 && abs(kn-in)<2){
for(m=0;m<3;m++) no->chi[m]=new Node();
for(m=0;m<no->cd.size();m++){
int ret=m4th(no->cd[m],i,j,k,p);
if(ret==i){
no->chi[0]->cd.push_back(no->cd[m]);
}else if(ret==j){
no->chi[1]->cd.push_back(no->cd[m]);
}else{
no->chi[2]->cd.push_back(no->cd[m]);
}
}
for(m=0;m<3;m++) if(!makeTestTree(no->chi[m])) break;
if(m==3){
no->ct=3;
no->cp[0]=i;
no->cp[1]=j;
no->cp[2]=k;
no->cp[3]=p;
return true;
}
}
}
}
}
}
}
return false;
}
void init(int T) {
int x[6]={0,0,0,0,0,0};
makeTestCase(0,0,x);
rt=new Node();
for(int i=0;i<720;i++) rt->cd.push_back(t[i]);
makeTestTree(rt);
}
void findAnswer(Node *rt){
if(rt->cd.size()==1){
int i,w[6];
for(i=1;i<=M;i++) w[rt->cd[0].a[i]]=i;
answer(w);
}else{
int ret;
if(rt->ct==0){
ret=getHeaviest(rt->cp[0],rt->cp[1],rt->cp[2]);
}else if(rt->ct==1){
ret=getLightest(rt->cp[0],rt->cp[1],rt->cp[2]);
}else if(rt->ct==2){
ret=getMedian(rt->cp[0],rt->cp[1],rt->cp[2]);
}else{
ret=getNextLightest(rt->cp[0],rt->cp[1],rt->cp[2],rt->cp[3]);
}
if(ret==rt->cp[0]){
findAnswer(rt->chi[0]);
}else if(ret==rt->cp[1]){
findAnswer(rt->chi[1]);
}else{
findAnswer(rt->chi[2]);
}
}
}
void orderCoins() {
findAnswer(rt);
}
Compilation message
scales.cpp: In function 'bool makeTestTree(Node*)':
scales.cpp:73:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(m=0;m<no->cd.size();m++){
^
scales.cpp:85:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(m=0;m<no->cd.size();m++){
^
scales.cpp:108:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(m=0;m<no->cd.size();m++){
^
scales.cpp:120:38: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(m=0;m<no->cd.size();m++){
^
scales.cpp: At global scope:
scales.cpp:150:15: warning: unused parameter 'T' [-Wunused-parameter]
void init(int T) {
^
scales.cpp: In function 'void findAnswer(Node*)':
scales.cpp:160:25: warning: declaration of 'rt' shadows a global declaration [-Wshadow]
void findAnswer(Node *rt){
^
scales.cpp:17:4: note: shadowed declaration is here
} *rt;
^
scales.cpp: In function 'int mget(int, TestCase, int, int, int)':
scales.cpp:51:1: warning: control reaches end of non-void function [-Wreturn-type]
}
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
13 ms |
2124 KB |
Output is correct |
| 2 |
Correct |
6 ms |
2124 KB |
Output is correct |
| 3 |
Correct |
13 ms |
2124 KB |
Output is correct |
| 4 |
Correct |
9 ms |
2124 KB |
Output is correct |
| 5 |
Correct |
9 ms |
2124 KB |
Output is correct |
| 6 |
Correct |
13 ms |
2124 KB |
Output is correct |
| 7 |
Correct |
9 ms |
2124 KB |
Output is correct |
| 8 |
Correct |
9 ms |
2124 KB |
Output is correct |
| 9 |
Correct |
9 ms |
2124 KB |
Output is correct |
| 10 |
Correct |
9 ms |
2124 KB |
Output is correct |
| 11 |
Correct |
9 ms |
2124 KB |
Output is correct |
| 12 |
Correct |
9 ms |
2124 KB |
Output is correct |
| 13 |
Correct |
9 ms |
2124 KB |
Output is correct |
| 14 |
Correct |
6 ms |
2124 KB |
Output is correct |
| 15 |
Correct |
9 ms |
2124 KB |
Output is correct |
| 16 |
Correct |
9 ms |
2124 KB |
Output is correct |
| 17 |
Correct |
13 ms |
2124 KB |
Output is correct |
| 18 |
Correct |
9 ms |
2124 KB |
Output is correct |
| 19 |
Correct |
9 ms |
2124 KB |
Output is correct |
| 20 |
Correct |
9 ms |
2124 KB |
Output is correct |
| 21 |
Correct |
9 ms |
2124 KB |
Output is correct |
| 22 |
Correct |
9 ms |
2124 KB |
Output is correct |
| 23 |
Correct |
9 ms |
2124 KB |
Output is correct |
| 24 |
Correct |
9 ms |
2124 KB |
Output is correct |
| 25 |
Correct |
9 ms |
2124 KB |
Output is correct |
| 26 |
Correct |
9 ms |
2124 KB |
Output is correct |
| 27 |
Correct |
9 ms |
2124 KB |
Output is correct |
| 28 |
Correct |
9 ms |
2124 KB |
Output is correct |
| 29 |
Correct |
9 ms |
2124 KB |
Output is correct |
| 30 |
Correct |
9 ms |
2124 KB |
Output is correct |
| 31 |
Correct |
9 ms |
2124 KB |
Output is correct |
| 32 |
Correct |
9 ms |
2124 KB |
Output is correct |
| 33 |
Correct |
9 ms |
2124 KB |
Output is correct |
| 34 |
Correct |
9 ms |
2124 KB |
Output is correct |
| 35 |
Correct |
9 ms |
2124 KB |
Output is correct |
| 36 |
Correct |
9 ms |
2124 KB |
Output is correct |
| 37 |
Correct |
9 ms |
2124 KB |
Output is correct |
| 38 |
Correct |
9 ms |
2124 KB |
Output is correct |
| 39 |
Correct |
9 ms |
2124 KB |
Output is correct |
| 40 |
Correct |
9 ms |
2124 KB |
Output is correct |
