Submission #1061521

#	Time	Username	Problem	Language	Result	Execution time	Memory
1061521		anango	Scales (IOI15_scales)	C++17	71.43 / 100	152 ms	560 KiB

scales

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

int INF = 1<<30;
int testcases;
vector<vector<int>> permutations = {{1,2,3,4,5,6}};
vector<vector<int>> combvals={{1,2,3},{1,2,4},{1,2,5},{1,2,6},{1,3,4},{1,3,5},{1,3,6},{1,4,5},{1,4,6},{1,5,6},{2,3,4},{2,4,5},{2,3,5},{2,3,6},{2,4,6},{2,5,6},{3,4,5},{3,5,6},{3,4,6},{4,5,6}};
vector<vector<int>> combvals2={{1,2,3,4},{1,2,3,5},{1,2,3,6},{1,2,4,5},{1,2,4,6},{1,2,5,6},{1,3,4,5},{1,3,5,6},{1,3,4,6},{1,4,5,6},{2,3,4,5},{2,3,4,6},{2,3,5,6},{2,4,5,6},{3,4,5,6}};
vector<vector<int>> operations;


void init(int T) {
    for (int i=0; i<719; i++) {
        permutations.push_back(permutations.back());
        next_permutation(permutations.back().begin(), permutations.back().end());
    }
    assert(permutations.size()==720);
    assert(combvals.size()==20);
    assert(combvals2.size()==15);
    /* ... */
    //initialise operations, each operation is id,a,b,c,d
    for (int id=1; id<=3; id++) {
        for (auto j:combvals) {
            operations.push_back({id,j[0],j[1],j[2],-1});
        }
    }
    for (auto j:combvals2) {
        operations.push_back({4,j[0],j[1],j[2],j[3]});
    }
    testcases = T;
}

int apply_operation(vector<int> perm, int id, int a, int b, int c, int d) {
    vector<int> pos(7); for (int i=0; i<6; i++) pos[perm[i]] = i;
    vector<int> val = {a,b,c};
    if (id==1) {
        sort(val.begin(), val.end(), [&](const int i1, const int i2) {
            return pos[i1]>pos[i2];
        });
        return val[0];
    }
    else if (id==2) {
        sort(val.begin(), val.end(), [&](const int i1, const int i2) {
            return pos[i1]<pos[i2];
        });
        return val[0];
    }
    else if (id==3) {
        sort(val.begin(), val.end(), [&](const int i1, const int i2) {
            return pos[i1]<pos[i2];
        });
        return val[1];
    }
    else if (id==4) {
        sort(val.begin(), val.end(), [&](const int i1, const int i2) {
            return (pos[i1]<pos[i2] && !(pos[i1]<pos[d] && pos[d]<pos[i2])) || (pos[i1]>pos[d] && pos[d]>pos[i2]);
        });
        return val[0];
    }
    return 88888888;
}

void prv(vector<int> v) {
    for (auto i:v) {
        cout << i <<" ";
    }
    cout << endl;
}

int operate(vector<int> v) {
    if (v[0]==1) {
        return getHeaviest(v[1],v[2],v[3]);
    }
    if (v[0]==2) {
        return getLightest(v[1],v[2],v[3]);
    }
    if (v[0]==3) {
        return getMedian(v[1],v[2],v[3]);
    }
    if (v[0]==4) {
        return getNextLightest(v[1],v[2],v[3],v[4]);
    }
    return 88888888;
    
}

void orderCoins() {
    /* ... */
    set<vector<int>> poss(permutations.begin(), permutations.end());
    while (poss.size()>1) {
        vector<int> minrop;
        int minrval = INF; //minimise the maximum
        for (auto operation:operations) {
            map<int,int> freq;
            for (auto j:poss) {
                int val = apply_operation(j,operation[0],operation[1],operation[2],operation[3],operation[4]);
                freq[val]++;
            }
            int mval = -1;
            for (auto j:freq) {
                mval=max(mval,j.second);
            }
            if (mval<minrval) {
                minrop = operation;
                minrval = mval;
            }
        }
        //cout << "MINIMAL OPERATION" << endl;
        //prv(minrop);
        int opans = operate(minrop);
        //cout << minrval << " " << opans << endl;
        set<vector<int>> newposs;
        for (auto j:poss) {
            int val = apply_operation(j,minrop[0],minrop[1],minrop[2],minrop[3],minrop[4]);
            if (val==opans) {
                newposs.insert(j);
            }
        }
        poss=newposs;
    }
    vector<int> ans = *poss.begin(); 
    int a = ans[0]; int b = ans[1]; int c = ans[2]; int d = ans[3]; int e = ans[4]; int f = ans[5];
    int W[6] = {a,b,c,d,e,f};
    answer(W);
}

• Subtask 1: 71.428571 / 100