Submission #68664

#	Time	Username	Problem	Language	Result	Execution time	Memory
68664		FLDutchman	Scales (IOI15_scales)	C++14	79.17 / 100	35 ms	992 KiB

scales

#include "scales.h"
#include <bits/stdc++.h>
using namespace std;

typedef int INT;

#define FOR(i,l,r) for(int i = (l); i < (r); i++)
#define fst first
#define snd second
#define pb push_back

typedef vector<int> vi;
typedef pair<int,int> ii;
typedef vector<ii> vii;
typedef vector<vi> vvi;

vi op;
vvi args;
// this corresponds to the relative weight of the coins
vvi perms;
vi ans;
int pows[] = {1,3,9,27,81,243,729};

int heavy(int i, int A, int B, int C){
    vi &p = perms[i];
    if(p[A] > p[B] and p[A] > p[C]) return 0;
    if(p[B] > p[A] and p[B] > p[C]) return 1;
    if(p[C] > p[B] and p[C] > p[A]) return 2;
}

int light(int i, int A, int B, int C){
    vi &p = perms[i];
    if(p[A] < p[B] and p[A] < p[C]) return 0;
    if(p[B] < p[A] and p[B] < p[C]) return 1;
    if(p[C] < p[B] and p[C] < p[A]) return 2;
}

int median(int i, int A, int B, int C){
    vi &p = perms[i];
    vi arr(3, 0);
    arr[0] = A; arr[1] = B; arr[2] = C;
    sort(arr.begin(), arr.end(), [&p] (int i, int j) {return p[i] < p[j];});
    if(arr[1] == A) return 0;
    if(arr[1] == B) return 1;
    if(arr[1] == C) return 2;
}

int nextl(int i, int A, int B, int C, int D){
    vi &p = perms[i];
    int l = 100;
    if(p[A] > p[D] and p[A] < l) l = p[A];
    if(p[B] > p[D] and p[B] < l) l = p[B];
    if(p[C] > p[D] and p[C] < l) l = p[C];
    if(l == 100) return light(i, A, B, C);
    if(l == p[A]) return 0;
    if(l == p[B]) return 1;
    if(l == p[C]) return 2;
}
int maxh = 0;
int leafcnt = 0;
void build(vi &ps, int n, int h){
    maxh = max(h, maxh);
    //if(h < 5) return;
    //cout << ps.size() << " " << n << " " << h  << endl;
    for(int i : ps){ 
        //for(int k : perms[i]) cout << k << " ";
        //cout << endl;
    }
    //cout<<endl;
    if(ps.size() == 0) return;
    if(ps.size() == 1){
        leafcnt++;
        ans[n] = ps[0];
        return;
    }
    vi bestars; int bestop;
    double bestentropy = 0;
    // All must be <= |ps|/3


    FOR(a, 0, 4) FOR(b, a+1, 5) FOR(c, b+1, 6){
        vi division(3);
        for(int i : ps) division[light(i, a, b, c)]++;
        //cerr << max(division[0].size(), max(division[1].size(), division[2].size())) << endl;
        double entr = 0;
        FOR(i, 0, 3){
            double p0 = (double)division[i]/(double)ps.size();
            if(p0!=0)entr -= p0 * log(p0);
        }
        //double entr = max(division[0], max(division[1], division[2]));
        if(entr > bestentropy) {
            bestars.clear();
            bestars.pb(a); bestars.pb(b); bestars.pb(c);
            bestop = 0;
            bestentropy = entr;
        } 
    }
    
    FOR(a, 0, 4) FOR(b, a+1, 5) FOR(c, b+1, 6){
        vi division(3);
        for(int i : ps) division[heavy(i, a, b, c)]++;
        //cerr << max(division[0].size(), max(division[1].size(), division[2].size())) << endl;
        double entr = 0;
        FOR(i, 0, 3){
            double p0 = (double)division[i]/(double)ps.size();
            if(p0!=0)entr -= p0 * log(p0);
        }
        //double entr = max(division[0], max(division[1], division[2]));
        if(entr > bestentropy) {
            bestars.clear();
            bestars.pb(a); bestars.pb(b); bestars.pb(c);
            bestop = 1;
            bestentropy = entr;
        } 
    }
    
    FOR(a, 0, 4) FOR(b, a+1, 5) FOR(c, b+1, 6){
        vi division(3);
        for(int i : ps) division[median(i, a, b, c)]++;
        //cerr << max(division[0].size(), max(division[1].size(), division[2].size())) << endl;
        double entr = 0;
        FOR(i, 0, 3){
            double p0 = (double)division[i]/(double)ps.size();
            if(p0!=0)entr -= p0 * log(p0);
        }
        //double entr = max(division[0], max(division[1], division[2]));
        if(entr > bestentropy) {
            bestars.clear();
            bestars.pb(a); bestars.pb(b); bestars.pb(c);
            bestop = 2;
            bestentropy = entr;
        } 
    }
    
    FOR(d, 0, 6) FOR(a, 0, 4) FOR(b, a+1, 5) FOR(c, b+1, 6){
        if(d != a and d != b and d != c);
        vi division(3, 0);
        for(int i : ps) division[nextl(i, a, b, c, d)]++;
        //cerr << max(division[0].size(), max(division[1].size(), division[2].size())) << endl;
        double entr = 0;
        FOR(i, 0, 3){
            double p0 = (double)division[i]/(double)ps.size();
            if(p0!=0)entr -= p0 * log(p0);
        }
        //double entr = max(division[0], max(division[1], division[2]));
        if(entr > bestentropy) {
            bestars.clear();
            bestars.pb(a); bestars.pb(b); bestars.pb(c); bestars.pb(d);
            bestop = 3;
            bestentropy = entr;
        } 
    }
    
    //cout << D[0].size() << " " <<D[1].size()<<" "<<D[2].size()<<endl;
    args[n] = bestars;
    op[n] = bestop;
    vvi D(3);
    if(bestop == 0) for(int i : ps) D[light(i, bestars[0], bestars[1], bestars[2])].pb(i);
    if(bestop == 1) for(int i : ps) D[heavy(i, bestars[0], bestars[1], bestars[2])].pb(i);
    if(bestop == 2) for(int i : ps) D[median(i, bestars[0], bestars[1], bestars[2])].pb(i);
    if(bestop == 3) for(int i : ps) D[nextl(i, bestars[0], bestars[1], bestars[2], bestars[3])].pb(i);
    FOR(i, 0, 3){   
        build(D[i], 3*n+i-1, h+1);
    }
}

int query(int i, vi arg){
    int val = -1;
    if(i == 0) val = getLightest(arg[0]+1, arg[1]+1, arg[2]+1)-1;
    if(i == 1) val = getHeaviest(arg[0]+1, arg[1]+1, arg[2]+1)-1;
    if(i == 2) val = getMedian(arg[0]+1, arg[1]+1, arg[2]+1)-1;
    if(i == 3) val = getNextLightest(arg[0]+1, arg[1]+1, arg[2]+1, arg[3]+1)-1;
    FOR(i, 0, 3) if(val == arg[i]) return i;
}

int get(int n){
    //cout<<n<<endl;
    if(ans[n] != -1) return ans[n];
    return get( 3*n-1 + query(op[n], args[n]) );
}

void init(INT T) {
    op.assign(5000, -1);
    args.resize(5000);
    ans.assign(5000, -1);
    vi p;
    FOR(i,0,6) p.pb(i);
    do {
        perms.pb(p);
    } while(next_permutation(p.begin(), p.end()));
    //cerr<<perms.size()<<endl;
    //for(int w : perms[100]) cout << w << " ";
    //cout<<endl;
    //cerr<< median(100, 2, 5, 3) << endl;
    vi all;
    FOR(i, 0, 720)all.pb(i);
    build(all, 1, 0);
    //cout<<"initialized"<<endl;
    //cout<<maxh<<endl;
    /*cout<<leafcnt<<endl;
    FOR(i, 0, 720){
        for(int k : perms[i]) cout << k+1 << " ";
        cout<<endl;
    }*/
}

void orderCoins() {
    /* ... */
    INT W[] = {1, 2, 3, 4, 5, 6};
    int i = get(1);
    FOR(j, 0, 6) W[perms[i][j]] = j+1;
    answer(W);
}

Compilation message (stderr)

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 lambda function:
scales.cpp:42:52: warning: declaration of 'int i' shadows a parameter [-Wshadow]
     sort(arr.begin(), arr.end(), [&p] (int i, int j) {return p[i] < p[j];});
                                                    ^
scales.cpp:38:16: note: shadowed declaration is here
 int median(int i, int A, int B, int C){
                ^
scales.cpp: In function 'void build(vi&, int, int)':
scales.cpp:65:13: warning: unused variable 'i' [-Wunused-variable]
     for(int i : ps){ 
             ^
scales.cpp:136:41: warning: suggest braces around empty body in an 'if' statement [-Wempty-body]
         if(d != a and d != b and d != c);
                                         ^
scales.cpp: In function 'int query(int, vi)':
scales.cpp:173:9: warning: declaration of 'int i' shadows a parameter [-Wshadow]
     FOR(i, 0, 3) if(val == arg[i]) return i;
         ^
scales.cpp:7:28: note: in definition of macro 'FOR'
 #define FOR(i,l,r) for(int i = (l); i < (r); i++)
                            ^
scales.cpp:167:15: note: shadowed declaration is here
 int query(int i, vi arg){
               ^
scales.cpp: In function 'void init(INT)':
scales.cpp:182:15: warning: unused parameter 'T' [-Wunused-parameter]
 void init(INT T) {
               ^
scales.cpp: In function 'int heavy(int, int, int, int)':
scales.cpp:29:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^
scales.cpp: In function 'int light(int, int, int, int)':
scales.cpp:36:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^
scales.cpp: In function 'int median(int, int, int, int)':
scales.cpp:46:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^
scales.cpp: In function 'int nextl(int, int, int, int, int)':
scales.cpp:58:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^
scales.cpp: In function 'int query(int, vi)':
scales.cpp:174:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

• Subtask 1: 79.166667 / 100