Submission #1061849

#	Time	Username	Problem	Language	Result	Execution time	Memory
1061849		anango	Scales (IOI15_scales)	C++17	100 / 100	983 ms	856 KiB

scales

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

mt19937 rng;

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

vector<int> pow3 = {1,3,9,27,81,243,729};

bool workable(vector<vector<int>> poss, int depth) {
    //cout << "working " << poss.size() <<" " << depth << endl;
    if (poss.size()>pow3[depth]) return 0;
    if (depth<=1) return 1;
    int minrval=INF;
    for (auto operation:operations) {
        map<int,int> freq;
        map<int,vector<vector<int>>> S;
        for (auto j:poss) {
            int val = apply_operation(j,operation[0],operation[1],operation[2],operation[3],operation[4]);
            freq[val]++;
            S[val].push_back(j);
        }
        int mval = -1;
        for (auto j:freq) {
            mval=max(mval,j.second);
        }
        if (mval>pow3[depth-1]) {
            continue;
        }
        int fail = 0;
        for (auto j:S) {
            if (!workable(j.second,depth-1)) {
                fail=1;
            }
        }
        if (fail) continue;
        minrval = mval;
        break;
    }
    if (minrval==INF) return 0;
    return 1;
}

void orderCoins() {
    auto start = std::chrono::high_resolution_clock::now();
    /* ... */
    vector<vector<int>> poss(permutations.begin(), permutations.end());
    int depth = 5;
    while (poss.size()>1) {
        vector<vector<int>> minrops;
        vector<int> minrop;
        int minrval = INF; //minimise the maximum
        for (auto operation:operations) {
            map<int,int> freq;
            map<int,vector<vector<int>>> S;
            for (auto j:poss) {
                int val = apply_operation(j,operation[0],operation[1],operation[2],operation[3],operation[4]);
                freq[val]++;
                S[val].push_back(j);
            }
            int mval = -1;
            for (auto j:freq) {
                mval=max(mval,j.second);
            }
            if (mval>pow3[depth]) {
                continue;
            }
            int fail = 0;
            for (auto j:S) {
                if (!workable(j.second,depth)) {
                    fail=1;
                }
            }
            if (fail) continue;
            minrop = operation;
            minrops.push_back(minrop);
            minrval = mval;
            break;
        }
        
        //cout << "MINIMAL OPERATION" << " " << minrops.size() << endl;
        //prv(minrop);
        minrop = minrops[rng()%((int)minrops.size())];
        minrop = minrops[0];
        minrop = minrops[minrops.size()/2];
        int opans = operate(minrop);
        //cout << minrval << " " << opans << endl;
        //cout << "reducing " << minrval << endl;
        vector<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.push_back(j);
            }
        }
        poss=newposs;
        depth--;
    }
    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};
    auto end = std::chrono::high_resolution_clock::now();
    std::chrono::duration<double> duration = end - start;
    //std::cout << "Time taken: " << duration.count() << " seconds" << std::endl;
    answer(W);
}

Compilation message (stderr)

scales.cpp: In function 'bool workable(std::vector<std::vector<int> >, int)':
scales.cpp:95:20: warning: comparison of integer expressions of different signedness: 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} and '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} [-Wsign-compare]
   95 |     if (poss.size()>pow3[depth]) return 0;
scales.cpp: In function 'void orderCoins()':
scales.cpp:135:13: warning: variable 'minrval' set but not used [-Wunused-but-set-variable]
  135 |         int minrval = INF; //minimise the maximum
      |             ^~~~~~~

• Subtask 1: 100 / 100