Submission #1217776

#	Time	Username	Problem	Language	Result	Execution time	Memory
1217776		HappyCapybara	Scales (IOI15_scales)	C++17	100 / 100	482 ms	460 KiB

scales

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

vector<int> v = {0, 1, 2, 3, 4, 5};
unordered_set<int> us;
vector<vector<int>> aq;

int query(int t, int a, int b, int c, int d=-1){
    if (t == 0){
        if (v[a] > v[b] && v[a] > v[c]) return a;
        else if (v[b] > v[a] && v[b] > v[c]) return b;
        else return c;
    }
    if (t == 1){
        if (v[a] < v[b] && v[a] < v[c]) return a;
        else if (v[b] < v[a] && v[b] < v[c]) return b;
        else return c;
    }
    if (t == 2){
        if (v[a] > min(v[b], v[c]) && v[a] < max(v[b], v[c])) return a;
        else if (v[b] > min(v[a], v[c]) && v[b] < max(v[a], v[c])) return b;
        else return c;
    }
    if (t == 3){
        if (v[a] > v[d] && (v[b] > v[a] || v[b] < v[d]) && (v[c] > v[a] || v[c] < v[d])) return a;
        else if (v[b] > v[d] && (v[a] > v[b] || v[a] < v[d]) && (v[c] > v[b] || v[c] < v[d])) return b;
        else if (v[c] > v[d] && (v[a] > v[c] || v[a] < v[d]) && (v[b] > v[c] || v[b] < v[d])) return c;
        else return query(1, a, b, c);
    }
}

int cnt(vector<vector<int>>& qs, vector<int> ans, bool b = false){
    int res = 0;
    vector<int> tbe;
    for (int x : us){
        v = {x%10, (x/10)%10, (x/100)%10, (x/1000)%10, (x/10000)%10, x/100000};
        bool valid = true;
        for (int i=0; i<qs.size(); i++){
            if (query(qs[i][0], qs[i][1], qs[i][2], qs[i][3], qs[i][4]) != ans[i]){
                valid = false;
                if (b) tbe.push_back(x);
            }
        }
        if (valid) res++;
    }
    for (int x : tbe) us.erase(x);
    return res;
}

void init(int T){
    for (int i=0; i<4; i++){
        for (int j=i+1; j<5; j++){
            for (int k=j+1; k<6; k++){
                for (int l=0; l<3; l++) aq.push_back({l, i, j, k, -1});
                for (int l=0; l<6; l++){
                    if (l == i || l == j || l == k) continue;
                    aq.push_back({3, i, j, k, l});
                }
            }
        }
    }
}

void orderCoins(){
    us.clear();
    vector<int> w = {0, 1, 2, 3, 4, 5};
    while (true){
        us.insert(w[0]+w[1]*10+w[2]*100+w[3]*1000+w[4]*10000+w[5]*100000);
        if (!next_permutation(w.begin(), w.end())) break;
    }
    int bruh = 5;
    while (true){
        //cout << bruh << endl;
        int bsf = 1000;
        vector<int> bq;
        if (bruh == 5) bq = {0, 0, 1, 2, -1};
        else if (bruh == 4) bq = {2, 3, 4, 5, -1};
        else {
            vector<vector<int>> gq;
            for (vector<int> pq : aq){
                int cur = 0;
                vector<vector<int>> huh = {pq};
                for (int i=1; i<=3; i++) cur = max(cur, cnt(huh, {pq[i]}));
                if (cur <= pow(3, bruh)){
                    gq.push_back(pq);
                }
            }
            for (vector<int> pq : gq){
                int cur = 0;
                for (int i=1; i<=3; i++){
                    int cur2 = 1000;
                    for (vector<int> pq2 : aq){
                        int cur3 = 0;
                        vector<vector<int>> huh = {pq, pq2};
                        for (int j=1; j<=3; j++) cur3 = max(cur3, cnt(huh, {pq[i], pq2[j]}));
                        cur2 = min(cur2, cur3);
                    }
                    cur = max(cur, cur2);
                }
                if (cur < bsf){
                    bsf = cur;
                    bq = pq;
                }
            }
        }
        int ans;
        if (bq[0] == 0) ans = getHeaviest(bq[1]+1, bq[2]+1, bq[3]+1);
        if (bq[0] == 1) ans = getLightest(bq[1]+1, bq[2]+1, bq[3]+1);
        if (bq[0] == 2) ans = getMedian(bq[1]+1, bq[2]+1, bq[3]+1);
        if (bq[0] == 3) ans = getNextLightest(bq[1]+1, bq[2]+1, bq[3]+1, bq[4]+1);
        //cout << bq[0] << " " << bq[1] << " " << bq[2] << " " << bq[3] << " " << bq[4] << endl;
        vector<vector<int>> huh = {bq};
        if (cnt(huh, {ans-1}, true) == 1) break;
        bruh--;
    }
    int x = *us.begin();
    v = {x%10, (x/10)%10, (x/100)%10, (x/1000)%10, (x/10000)%10, x/100000};
    int arr[6];
    for (int i=0; i<6; i++) arr[v[i]] = i+1;
    answer(arr);
}

Compilation message (stderr)

scales.cpp: In function 'int query(int, int, int, int, int)':
scales.cpp:31:1: warning: control reaches end of non-void function [-Wreturn-type]
   31 | }
      | ^

• Subtask 1: 100 / 100