Submission #794272

#	Time	Username	Problem	Language	Result	Execution time	Memory
794272		Josia	Scales (IOI15_scales)	C++17	75.60 / 100	385 ms	460 KiB

scales

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


void init(int T) {
    /* ... */
}



int checkComp(vector<vector<int>> perms, vector<int> elems, int op) {
    if (op == 0) {  // min
        vector<vector<vector<int>>> smallPerms(3);
        for (int chosen = 0; chosen<3; chosen++) {
            for (int i = 0; i < perms.size(); i++) {
                if (perms[i][elems[chosen]] < perms[i][elems[(chosen+1)%3]] && perms[i][elems[chosen]] < perms[i][elems[(chosen+2)%3]]) {
                    smallPerms[chosen].push_back(perms[i]);
                }
            }
        }

        set<int> sizes = {(int)smallPerms[0].size(), (int)smallPerms[1].size(), (int)smallPerms[2].size()};

        return ((*sizes.rbegin())-(*sizes.begin()));
    }

    if (op == 1) {  // max
        vector<vector<vector<int>>> smallPerms(3);
        for (int chosen = 0; chosen<3; chosen++) {
            for (int i = 0; i < perms.size(); i++) {
                if (perms[i][elems[chosen]] > perms[i][elems[(chosen+1)%3]] && perms[i][elems[chosen]] > perms[i][elems[(chosen+2)%3]]) {
                    smallPerms[chosen].push_back(perms[i]);
                }
            }
        }

        set<int> sizes = {(int)smallPerms[0].size(), (int)smallPerms[1].size(), (int)smallPerms[2].size()};

        return ((*sizes.rbegin())-(*sizes.begin()));
    }

    if (op == 2) {  // med
        vector<vector<vector<int>>> smallPerms(3);
        for (int chosen = 0; chosen<3; chosen++) {
            for (int i = 0; i < perms.size(); i++) {
                if ((perms[i][elems[chosen]] > perms[i][elems[(chosen+1)%3]] && perms[i][elems[chosen]] < perms[i][elems[(chosen+2)%3]]) || (perms[i][elems[chosen]] < perms[i][elems[(chosen+1)%3]] && perms[i][elems[chosen]] > perms[i][elems[(chosen+2)%3]])) {
                    smallPerms[chosen].push_back(perms[i]);
                }
            }
        }

        set<int> sizes = {(int)smallPerms[0].size(), (int)smallPerms[1].size(), (int)smallPerms[2].size()};

        return ((*sizes.rbegin())-(*sizes.begin()));
    }

    if (op == 3) {  // weird
        // return 1e9;
        vector<vector<vector<int>>> smallPerms(3);
        for (int chosen = 0; chosen<3; chosen++) {
            for (int i = 0; i < perms.size(); i++) {
                int comp = perms[i][elems[3]];

                set<int> bigger;
                for (int j = 0; j<3; j++) if(perms[i][elems[j]]>comp) bigger.insert(perms[i][elems[j]]);
                if (bigger.empty()) for (int j = 0; j<3; j++) bigger.insert(perms[i][elems[j]]);
                if ((*bigger.begin()) == perms[i][elems[chosen]]) smallPerms[chosen].push_back(perms[i]);
            }
        }

        set<int> sizes = {(int)smallPerms[0].size(), (int)smallPerms[1].size(), (int)smallPerms[2].size()};

        return ((*sizes.rbegin())-(*sizes.begin()));
    }
}


void updatePerms(vector<vector<int>> &perms, vector<int> elems, int op, int res) {
if (op == 0) {  // min
        vector<vector<int>> smallPerms;
        int chosen = 0;
        if (res == elems[1]) chosen = 1;
        if (res == elems[2]) chosen = 2;
        for (int i = 0; i < perms.size(); i++) {
            if (perms[i][elems[chosen]] < perms[i][elems[(chosen+1)%3]] && perms[i][elems[chosen]] < perms[i][elems[(chosen+2)%3]]) {
                smallPerms.push_back(perms[i]);
            }
        }
        perms = smallPerms;
    }

    if (op == 1) {  // max
        vector<vector<int>> smallPerms;
        int chosen = 0;
        if (res == elems[1]) chosen = 1;
        if (res == elems[2]) chosen = 2;
        for (int i = 0; i < perms.size(); i++) {
            if (perms[i][elems[chosen]] > perms[i][elems[(chosen+1)%3]] && perms[i][elems[chosen]] > perms[i][elems[(chosen+2)%3]]) {
                smallPerms.push_back(perms[i]);
            }
        }
        perms = smallPerms;
    }

    if (op == 2) {  // med
        vector<vector<int>> smallPerms;
        int chosen = 0;
        if (res == elems[1]) chosen = 1;
        if (res == elems[2]) chosen = 2;
        for (int i = 0; i < perms.size(); i++) {
            if ((perms[i][elems[chosen]] > perms[i][elems[(chosen+1)%3]] && perms[i][elems[chosen]] < perms[i][elems[(chosen+2)%3]]) || (perms[i][elems[chosen]] < perms[i][elems[(chosen+1)%3]] && perms[i][elems[chosen]] > perms[i][elems[(chosen+2)%3]])) {
                smallPerms.push_back(perms[i]);
            }
        }
        perms = smallPerms;
    }

    if (op == 3) {  // weird
        vector<vector<int>> smallPerms;
        int chosen = 0;
        if (res == elems[1]) chosen = 1;
        if (res == elems[2]) chosen = 2;
        for (int i = 0; i < perms.size(); i++) {
            int comp = perms[i][elems[3]];

            set<int> bigger;
            for (int j = 0; j<3; j++) if(perms[i][elems[j]]>comp) bigger.insert(perms[i][elems[j]]);
            if (bigger.empty()) for (int j = 0; j<3; j++) bigger.insert(perms[i][elems[j]]);
            if ((*bigger.begin()) == perms[i][elems[chosen]]) smallPerms.push_back(perms[i]);
        }
        perms = smallPerms;
    }
}







void orderCoins() {
    
    vector<vector<int>> perms;

    vector<int> currPerm = {0,1,2,3,4,5};

    do {
        perms.push_back(currPerm);
    } while(next_permutation(currPerm.begin(), currPerm.end()));
    auto rng = std::default_random_engine {4};
    
    while (perms.size() > 1) {
        // cerr << perms.size() << "\n";
        int best = 1e9;
        vector<int> elems;
        int OP = -1;

        vector<int> I = {0,1,2,3,4,5}; shuffle(I.begin(), I.end(), rng);

        for (int i:I) {
            vector<int> J = {0,1,2,3,4,5}; shuffle(J.begin(), J.end(), rng);
            for (int j:J) {
                vector<int> K = {0,1,2,3,4,5}; shuffle(K.begin(), K.end(), rng);
                for (int k:K) {
                    if (i == j || j == k || i == k) continue;
                    vector<int> Op = {0,1,2}; shuffle(Op.begin(), Op.end(), rng);
                    for (int op:Op) {
                        if (checkComp(perms, {i,j,k}, op) < best) {elems = {i,j,k}; OP = op; best = checkComp(perms, {i,j,k}, op);}
                    }
                    vector<int> L = {0,1,2,3,4,5}; shuffle(L.begin(), L.end(), rng);
                    for (int l:L) {
                        if (i == j || j == k || i == k || l == i || l == j || l == k) continue;
                        if (checkComp(perms, {i,j,k,l}, 3) < best) {elems = {i,j,k,l}; OP = 3; best = checkComp(perms, {i,j,k,l}, 3);}
                    }
                    if (best < 1) break;
                }
                if (best < 1) break;
            }
            if (best < 1) break;
        }
        
        assert(OP != -1);

        // cerr << OP << "\n";


        if (OP==0) updatePerms(perms, elems, OP, getLightest(elems[0]+1, elems[1]+1, elems[2]+1)-1);
        if (OP==1) updatePerms(perms, elems, OP, getHeaviest(elems[0]+1, elems[1]+1, elems[2]+1)-1);
        if (OP==2) updatePerms(perms, elems, OP, getMedian(elems[0]+1, elems[1]+1, elems[2]+1)-1);
        if (OP==3) updatePerms(perms, elems, OP, getNextLightest(elems[0]+1, elems[1]+1, elems[2]+1, elems[3]+1)-1);

    }

    // cerr << perms.size() << "\n";

    int res[6];

    for (int i = 0; i<6; i++) {
        res[perms[0][i]] = i+1;
    }


    answer(res);
}

Compilation message (stderr)

scales.cpp: In function 'void init(int)':
scales.cpp:6:15: warning: unused parameter 'T' [-Wunused-parameter]
    6 | void init(int T) {
      |           ~~~~^
scales.cpp: In function 'int checkComp(std::vector<std::vector<int> >, std::vector<int>, int)':
scales.cpp:16:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   16 |             for (int i = 0; i < perms.size(); i++) {
      |                             ~~^~~~~~~~~~~~~~
scales.cpp:31:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |             for (int i = 0; i < perms.size(); i++) {
      |                             ~~^~~~~~~~~~~~~~
scales.cpp:46:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |             for (int i = 0; i < perms.size(); i++) {
      |                             ~~^~~~~~~~~~~~~~
scales.cpp:62:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |             for (int i = 0; i < perms.size(); i++) {
      |                             ~~^~~~~~~~~~~~~~
scales.cpp: In function 'void updatePerms(std::vector<std::vector<int> >&, std::vector<int>, int, int)':
scales.cpp:85:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   85 |         for (int i = 0; i < perms.size(); i++) {
      |                         ~~^~~~~~~~~~~~~~
scales.cpp:98:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   98 |         for (int i = 0; i < perms.size(); i++) {
      |                         ~~^~~~~~~~~~~~~~
scales.cpp:111:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  111 |         for (int i = 0; i < perms.size(); i++) {
      |                         ~~^~~~~~~~~~~~~~
scales.cpp:124:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  124 |         for (int i = 0; i < perms.size(); i++) {
      |                         ~~^~~~~~~~~~~~~~
scales.cpp: In function 'int checkComp(std::vector<std::vector<int> >, std::vector<int>, int)':
scales.cpp:76:1: warning: control reaches end of non-void function [-Wreturn-type]
   76 | }
      | ^

• Subtask 1: 75.595238 / 100