Submission #1276988

#	Time	Username	Problem	Language	Result	Execution time	Memory
1276988		papaulo	Scales (IOI15_scales)	C++20	100 / 100	3 ms	592 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 opt[7][720];
int lim[7];

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;
}

int can(int i, int v, vector<int> &ps) {
    if(i==6) return 1;
    int bstV=1e9;
    vector<int> bsts;
    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;
            bsts.clear();
        }
        if(curV==bstV) bsts.push_back(i);
    }
    if(bstV>lim[i+1]) return 0;
    if(bsts.size()==120) {
        bsts.clear();
        for(int i=0;i<4;i++) bsts.push_back(20*i);
    }

    for(auto o : bsts) {
        vector<int> pn[3];
        for(auto p : ps) {
            pn[res[o][p]].push_back(p);
        }
        int could=1;
        for(int j=0;j<3;j++) {
            if(!can(i+1, v*3+j, pn[j])) {
                could = 0;
                break;
            }
        }
        if(could) {
            opt[i][v]=o;
            return 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);
    }
    vector<int> ps;
    for(int i=0;i<720;i++) ps.push_back(i);
    lim[6]=1;
    for(int i=5;i>=0;i--) lim[i]=lim[i+1]*3;
    can(0, 0, ps);
}

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);
    int i=0, m=0;
    while(ps.size()>1) {
        int o=opt[i][m];
        int v=doOp(o);
        m=m*3+v;
        vector<int> nps;
        for(auto p : ps) {
            if(res[o][p]==v) nps.push_back(p);
        }
        ps=nps;
        i++;
    }
    for(int i=0;i<6;i++) W[i]=perms[ps[0]][i+1];
    answer(W);
}

• Subtask 1: 100 / 100