Submission #16759

#	Time	Username	Problem	Language	Result	Execution time	Memory
16759		CodingBug	Scales (IOI15_scales)	C++98	100 / 100	13 ms	2124 KiB

scales

#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 (stderr)

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]
 }
 ^

• Subtask 1: 100 / 100