Submission #729094

#	Time	Username	Problem	Language	Result	Execution time	Memory
729094		kirakaminski968	Scales (IOI15_scales)	C++17	100 / 100	74 ms	632 KiB

scales

#include "scales.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5;
vector<vector<int>> allPerm;
vector<pair<int, vector<int>>> OP;
int ask[MAXN];
int nxt[MAXN][4];
int done[MAXN];
int timer = 0;
bool init(int cur, int sz, vector<int> index) {
        if (index.size() <= 1) {
            if (index.size() == 1) {
                done[cur] = 1;
                ask[cur] = index[0];
            }
            return 1;
        }
        for (int z = 0; z < OP.size(); z++) {
                int op = OP[z].first;
                vector<int> ques = OP[z].second;
                bool ok = 1;
                vector<int> ans[3];
                for (int id : index) {
                        int a[3], b[6];
                        for (int i = 0; i < 3; i++) a[i] = allPerm[id][ques[i]];
                        sort(a, a + 3);
                        for (int i = 0; i < 3; i++) b[allPerm[id][ques[i]]] = i;
                        if (op == 0) {  // min
                                ans[b[a[0]]].emplace_back(id);
                        } else if (op == 1) {  // med
                                ans[b[a[1]]].emplace_back(id);
                        } else if (op == 2) {  // max
                                ans[b[a[2]]].emplace_back(id);
                        } else {  // spec
                                if (allPerm[id][ques[3]] < a[0]) {
                                        ans[b[a[0]]].emplace_back(id);
                                } else if (allPerm[id][ques[3]] < a[1]) {
                                        ans[b[a[1]]].emplace_back(id);
                                } else if (allPerm[id][ques[3]] < a[2]) {
                                        ans[b[a[2]]].emplace_back(id);
                                } else {
                                        ans[b[a[0]]].emplace_back(id);
                                }
                        }
                }
                if (ans[0].size() > sz / 3) continue;
                if (ans[1].size() > sz / 3) continue;
                if (ans[2].size() > sz / 3) continue;
                for (int i = 0; i < 3; i++) {
                        nxt[cur][i] = timer++;
                        ok &= init(nxt[cur][i], sz / 3, ans[i]);
                }
                if (ok) return ask[cur] = z, 1;
        }
        return 0;
}

void init(int T) {
        vector<int> a(6);
        iota(a.begin(), a.end(), 0);
        do {
                allPerm.emplace_back(a);
        } while (next_permutation(a.begin(), a.end()));
        vector<int> index(720);
        iota(index.begin(), index.end(), 0);
        for (int i = 0; i < 1 << 6;++i) {
                if (__builtin_popcount(i) == 3) {
                        vector<int> ques;
                        for (int j = 0;j < 6;++j){
                                if (i >> j & 1) ques.emplace_back(j);
                        }
                        for (int j = 0; j < 3; j++) OP.emplace_back(j, ques);
                        for (int j = 0; j < 6; j++) {
                                if (i >> j & 1 ^ 1) {
                                        ques.emplace_back(j);
                                        OP.emplace_back(3, ques);
                                        ques.pop_back();
                                }
                        }
                }
        }
        assert(init(timer++, 729, index));
}

int F(int cur) {
    if (done[cur]) return ask[cur];
    int op = OP[ask[cur]].first;
    vector<int> ques = OP[ask[cur]].second; int answer = -1;
    if(op == 0) { answer = getLightest(ques[0] + 1, ques[1] + 1, ques[2] + 1);}
    else if (op == 1) {answer = getMedian(ques[0] + 1, ques[1] + 1, ques[2] + 1);}
    else if (op == 2) {answer = getHeaviest(ques[0] + 1, ques[1] + 1, ques[2] + 1);}
    else{answer = getNextLightest(ques[0] + 1, ques[1] + 1, ques[2] + 1, ques[3] + 1);}
    for(int i = 0;i<3;++i){
        if(answer == ques[i] + 1) return F(nxt[cur][i]);
    }
    return assert(0),-1;
}

void orderCoins() {
    int id = F(0), W[6];
    for (int i = 0;i < 6;++i) W[allPerm[id][i]] = i + 1;
    answer(W);
}

Compilation message (stderr)

scales.cpp: In function 'bool init(int, int, std::vector<int>)':
scales.cpp:19:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::vector<int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 |         for (int z = 0; z < OP.size(); z++) {
      |                         ~~^~~~~~~~~~~
scales.cpp:47:35: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   47 |                 if (ans[0].size() > sz / 3) continue;
      |                     ~~~~~~~~~~~~~~^~~~~~~~
scales.cpp:48:35: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   48 |                 if (ans[1].size() > sz / 3) continue;
      |                     ~~~~~~~~~~~~~~^~~~~~~~
scales.cpp:49:35: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   49 |                 if (ans[2].size() > sz / 3) continue;
      |                     ~~~~~~~~~~~~~~^~~~~~~~
scales.cpp: In function 'void init(int)':
scales.cpp:75:44: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
   75 |                                 if (i >> j & 1 ^ 1) {
      |                                     ~~~~~~~^~~
scales.cpp:59:15: warning: unused parameter 'T' [-Wunused-parameter]
   59 | void init(int T) {
      |           ~~~~^

• Subtask 1: 100 / 100