Submission #1165290

#	Time	Username	Problem	Language	Result	Execution time	Memory
1165290		SmuggingSpun	Scales (IOI15_scales)	C++20	100 / 100	655 ms	41600 KiB

scales

#include<bits/stdc++.h>
#include "scales.h"
using namespace std;
template<class T>bool minimize(T& a, T b){
    if(a > b){
        a = b;
        return true;
    }
    return false;
}
template<class T>void maximize(T& a, T b){
    if(a < b){
        a = b;
    }
}
map<vector<vector<int>>, pair<vector<int>, int>>dp;
vector<vector<int>>cd;
void get_min_query(vector<vector<int>>& perm, const vector<int>& id, const int r){
    cd.clear();
    for(vector<int>& p : perm){
        bool flag;
        for(int& x : p){
            if(x == id[0] || x == id[1] || x == id[2]){
                flag = bool(x == id[r]);
                break;
            }
        }
        if(flag){
            cd.emplace_back(p);
        }
    }
}
void get_max_query(vector<vector<int>>& perm, const vector<int>& id, const int r){
    cd.clear();
    for(vector<int>& p : perm){
        bool flag;
        for(int i = 5; i > -1; i--){
            if(p[i] == id[0] || p[i] == id[1] || p[i] == id[2]){
                flag = bool(p[i] == id[r]);
                break;
            }
        }
        if(flag){
            cd.emplace_back(p);
        }
    }
}
void get_median_query(vector<vector<int>>& perm, const vector<int>& id, const int r){
    cd.clear();
    for(vector<int>& p : perm){
        bool flag;
        for(int& x : p){
            if(x == id[0] || x == id[1] || x == id[2]){
                flag = bool(x != id[r]);
                break;
            }
        }
        if(flag){
            for(int i = 5; i > -1; i--){
                if(p[i] == id[0] || p[i] == id[1] || p[i] == id[2]){
                    flag = bool(p[i] != id[r]);
                    break;
                }
            }
            if(flag){
                cd.emplace_back(p);
            }
        }
    }
}
void get_next_min_query(vector<vector<int>>& perm, const vector<int>& id, const int r){
    cd.clear();
    for(vector<int>& p : perm){
        vector<int>ord;
        for(int& x : p){
            if(x == id[0] || x == id[1] || x == id[2] || x == id[3]){
                ord.emplace_back(x);
            }
        }
        for(int i = 0; i < 4; i++){
            if(id[3] == ord[i]){
                if((i == 3 && id[r] == ord[0]) || (i < 3 && id[r] == ord[i + 1])){
                    cd.emplace_back(p);
                }
                break;
            }
        }
    }
}
int dfs(vector<vector<int>>perm){
    int theory_optimal = 0;
    for(int i = 1; i < perm.size(); i *= 3){
        theory_optimal++;
    }
    if(theory_optimal < 4){
        return theory_optimal;
    }
    auto it = dp.find(perm);
    if(it != dp.end()){
        return (it->second).second;
    }
    int ans = 8;
    vector<int>query;
    for(int i = 1; i < 7 && ans > theory_optimal; i++){
        for(int j = i + 1; j < 7 && ans > theory_optimal; j++){
            for(int k = j + 1; k < 7 && ans > theory_optimal; k++){
                vector<int>id = {i, j, k};
                vector<vector<int>>_max, _min, _median;
                int max_min = 0, max_max = 0, max_median = 0;
                for(int r = 0; r < 3; r++){
                    if(max_min + 1 < ans){
                        get_min_query(perm, id, r);
                        maximize(max_min, cd.size() == perm.size() ? 10 : (cd.empty() ? 0 : dfs(cd))); 
                    }
                    if(max_max + 1 < ans){                   
                        get_max_query(perm, id, r);
                        maximize(max_max, cd.size() == perm.size() ? 10 : (cd.empty() ? 0 : dfs(cd)));
                    }
                    if(max_median + 1 < ans){
                        get_median_query(perm, id, r);
                        maximize(max_median, cd.size() == perm.size() ? 10 : (cd.empty() ? 0 : dfs(cd)));
                    }
                }
                if(minimize(ans, max_min + 1)){
                    query = id;
                    query.emplace_back(i);
                }
                if(minimize(ans, max_max + 1)){
                    query = id;
                    query.emplace_back(j);
                }
                if(minimize(ans, max_median + 1)){
                    query = id;
                    query.emplace_back(k);
                }
                for(int t = k + 1; t < 7; t++){
                    vector<int>id = {i, j, k, t};
                    for(int _i = 0; _i < 4 && ans > theory_optimal; _i++){
                        swap(id[_i], id[3]);
                        int max_next_min = 0;
                        for(int r = 0; r < 3 && max_next_min + 1 < ans; r++){
                            get_next_min_query(perm, id, r);
                            maximize(max_next_min, cd.size() == perm.size() ? 10 : (cd.empty() ? 0 : dfs(cd)));
                        }
                        if(minimize(ans, max_next_min + 1)){
                            query = id;
                        }
                        swap(id[_i], id[3]);
                    }
                }
            }
        }
    }
    dp[perm] = make_pair(query, ans);
    return ans;
}
vector<vector<int>>__perm;
void init(int T){
    vector<int>_p(6);
    iota(_p.begin(), _p.end(), 1);
    do{
        __perm.emplace_back(_p);
    } while(next_permutation(_p.begin(), _p.end()));
    dfs(__perm);
}
int W_ans[6];
void __answer(const vector<int>& ans){
    for(int i = 0; i < 6; i++){
        W_ans[i] = ans[i];
    }
    answer(W_ans);
}
bool update_min(vector<vector<int>>& best, vector<vector<int>>cd){
    if(best.size() >= cd.size()){
        swap(best, cd);
        return true;
    } 
    return false;
}
void update_max(vector<vector<int>>& best, vector<vector<int>>cd){
    if(best.size() < cd.size()){
        swap(best, cd);
    } 
}
void orderCoins(){
    vector<vector<int>>perm = __perm;
    while(perm.size() > 27){
        vector<int>& id = dp[perm].first;
        if(id[0] == id[3]){
            int x = getLightest(id[0], id[1], id[2]);
            get_min_query(perm, id, x == id[0] ? 0 : (x == id[1] ? 1 : 2));
            swap(perm, cd);
        }
        else if(id[1] == id[3]){
            int x = getHeaviest(id[0], id[1], id[2]);
            get_max_query(perm, id, x == id[0] ? 0 : (x == id[1] ? 1 : 2));
            swap(perm, cd);
        }
        else if(id[2] == id[3]){
            int x = getMedian(id[0], id[1], id[2]);
            get_median_query(perm, id, x == id[0] ? 0 : (x == id[1] ? 1 : 2));
            swap(perm, cd);
        }
        else{
            int x = getNextLightest(id[0], id[1], id[2], id[3]);
            get_next_min_query(perm, id, x == id[0] ? 0 : (x == id[1] ? 1 : 2));
            swap(perm, cd);
        }
    }
    while(perm.size() > 1){
        vector<vector<int>>best = perm;
        pair<vector<int>, int>query;
        for(int i = 1; i < 7; i++){
            for(int j = i + 1; j < 7; j++){
                for(int k = j + 1; k < 7; k++){
                    vector<int>id = {i, j, k};
                    vector<vector<int>>_max, _min, _median;
                    for(int r = 0; r < 3; r++){
                        get_min_query(perm, id, r);
                        update_max(_min, cd);
                        get_max_query(perm, id, r);
                        update_max(_max, cd);
                        get_median_query(perm, id, r);
                        update_max(_median, cd);
                    }
                    for(int t = k + 1; t < 7; t++){
                        vector<int>id = {i, j, k, t};
                        for(int _i = 0; _i < 4; _i++){
                            swap(id[_i], id[3]);
                            vector<vector<int>>_next_min;
                            for(int r = 0; r < 3; r++){
                                get_next_min_query(perm, id, r);
                                update_max(_next_min, cd);
                            }
                            if(update_min(best, _next_min)){
                                query = make_pair(id, 3);
                            }
                            swap(id[_i], id[3]);
                        }
                    }
                    if(update_min(best, _min)){
                        query = make_pair(id, 0);
                    }
                    if(update_min(best, _max)){
                        query = make_pair(id, 1);
                    }
                    if(update_min(best, _median)){
                        query = make_pair(id, 2);
                    }
                }
            }
        }
        if(query.second == 0){
            int x = getLightest(query.first[0], query.first[1], query.first[2]);
            get_min_query(perm, query.first, x == query.first[0] ? 0 : (x == query.first[1] ? 1 : 2));
            perm = cd;
        }
        else if(query.second == 1){
            int x = getHeaviest(query.first[0], query.first[1], query.first[2]);
            get_max_query(perm, query.first, x == query.first[0] ? 0 : (x == query.first[1] ? 1 : 2));
            perm = cd;
        }
        else if(query.second == 2){
            int x = getMedian(query.first[0], query.first[1], query.first[2]);
            get_median_query(perm, query.first, x == query.first[0] ? 0 : (x == query.first[1] ? 1 : 2));
            perm = cd;
        }
        else{
            int x = getNextLightest(query.first[0], query.first[1], query.first[2], query.first[3]);
            get_next_min_query(perm, query.first, x == query.first[0] ? 0 : (x == query.first[1] ? 1 : 2));
            perm = cd;
        }
    }
    __answer(perm[0]);
}

• Subtask 1: 100 / 100