Submission #1276984

#	Time	Username	Problem	Language	Result	Execution time	Memory
1276984		papaulo	Scales (IOI15_scales)	C++20	71.73 / 100	5 ms	808 KiB

scales

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

int perms[720][7];
int pos[720][7];
int ops[120][4];
int res[120][720];

int exec(int i, int j) {
    int o = ops[i][0];
    int is[7];
    memset(is, 0, sizeof(is));
    for(int k=1;k<4;k++) is[pos[j][ops[i][k]]]=k;
    if(o<3) {
        for(int k=1;k<=6;k++) {
            if(is[k]) {
                if(!o) return is[k]-1;
                --o;
            }
        }
    } else {
        o-=3;
        int d=0;
        int id[7];
        memset(id, 0, sizeof(id));
        for(int k=1;k<4;k++) id[ops[i][k]]=k;
        for(int k=1;k<=6;k++) {
            if(!id[k]) {
                if(!o) {
                    d=k;
                    break;
                }
                --o;
            }
        }
        d=pos[j][d];
        for(int k=d+1;k<=6;k++) {
            if(is[k]) return is[k]-1;
        }
        for(int k=1;k<=6;k++) {
            if(is[k]) return is[k]-1;
        }
    }
    return 0;
}

void init(int T) {
    int p1[6]={1, 2, 3, 4, 5, 6};
    int p2[7];
    int p3[7];
    int j=0;
    do {
        for(int i=0;i<6;i++) p2[i+1]=p1[i];
        for(int i=1;i<=6;i++) p3[p2[i]]=i;
        for(int i=1;i<=6;i++) perms[j][i]=p2[i];
        for(int i=1;i<=6;i++) pos[j][i]=p3[i];
        ++j;
    } while(next_permutation(p1, p1+6));
    int id=0;
    for(int o=0;o<6;o++) {
        for(int i=1;i<=6;i++) {
            for(int j=i+1;j<=6;j++) {
                for(int k=j+1;k<=6;k++) {
                    ops[id][0]=o;
                    ops[id][1]=i;
                    ops[id][2]=j;
                    ops[id][3]=k;
                    ++id;
                }
            }
        }
    }
    for(int i=0;i<120;i++) {
        for(int j=0;j<720;j++) res[i][j]=exec(i, j);
    }
}

int doOp(int i) {
    int id[7];
    memset(id, 0, sizeof(id));
    for(int k=1;k<4;k++) id[ops[i][k]]=k;
    int o=ops[i][0], a=ops[i][1], b=ops[i][2], c=ops[i][3];
    if(o==0) return id[getLightest(a, b, c)]-1;
    if(o==1) return id[getMedian(a, b, c)]-1;
    if(o==2) return id[getHeaviest(a, b, c)]-1;
    o-=3;
    int d=0;
    for(int k=1;k<=6;k++) {
        if(!id[k]) {
            if(!o) {
                d=k;
                break;
            }
            --o;
        }
    }
    return id[getNextLightest(a, b, c, d)]-1;
}

void orderCoins() {
    int W[6];
    vector<int> ps;
    for(int i=0;i<720;i++) ps.push_back(i);
    while(ps.size()>1) {
        int bstI=-1, bstV=1e9;
        for(int i=0;i<120;i++) {
            int cur[3]={0, 0, 0};
            for(auto p : ps) cur[res[i][p]]++;
            int curV=0;
            for(int i=0;i<3;i++) curV=max(curV, cur[i]);
            if(curV<bstV) {
                bstV=curV;
                bstI=i;
            }
        }
        int v=doOp(bstI);
        vector<int> nps;
        for(auto p : ps) {
            if(res[bstI][p]==v) nps.push_back(p);
        }
        ps=nps;
    }
    for(int i=0;i<6;i++) W[i]=perms[ps[0]][i+1];
    answer(W);
}

• Subtask 1: 71.7262 / 100