Submission #1165238

#	Time	Username	Problem	Language	Result	Execution time	Memory
1165238		SmuggingSpun	저울 (IOI15_scales)	C++20	72.92 / 100	475 ms	608 KiB

scales

#include<bits/stdc++.h>
#include "scales.h"
using namespace std;
void init(int T){}
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>>candidate){
    if(best.size() > candidate.size()){
        swap(best, candidate);
        return true;
    } 
    return false;
}
void update_max(vector<vector<int>>& best, vector<vector<int>>candidate){
    if(best.size() < candidate.size()){
        swap(best, candidate);
    } 
}
vector<vector<int>>get_min_query(vector<vector<int>>& perm, const vector<int>& index, const int r){
    vector<vector<int>>candidate;
    for(vector<int>& p : perm){
        bool flag;
        for(int& x : p){
            if(x == index[0] || x == index[1] || x == index[2]){
                flag = bool(x == index[r]);
                break;
            }
        }
        if(flag){
            candidate.emplace_back(p);
        }
    }
    return candidate;
}
vector<vector<int>>get_max_query(vector<vector<int>>& perm, const vector<int>& index, const int r){
    vector<vector<int>>candidate;
    for(vector<int>& p : perm){
        bool flag;
        for(int i = 5; i > -1; i--){
            if(p[i] == index[0] || p[i] == index[1] || p[i] == index[2]){
                flag = bool(p[i] == index[r]);
                break;
            }
        }
        if(flag){
            candidate.emplace_back(p);
        }
    }
    return candidate;
}
vector<vector<int>>get_median_query(vector<vector<int>>& perm, const vector<int>& index, const int r){
    vector<vector<int>>candidate;
    for(vector<int>& p : perm){
        bool flag;
        for(int& x : p){
            if(x == index[0] || x == index[1] || x == index[2]){
                flag = bool(x != index[r]);
                break;
            }
        }
        if(flag){
            for(int i = 5; i > -1; i--){
                if(p[i] == index[0] || p[i] == index[1] || p[i] == index[2]){
                    flag = bool(p[i] != index[r]);
                    break;
                }
            }
            if(flag){
                candidate.emplace_back(p);
            }
        }
    }
    return candidate;
}
vector<vector<int>>get_next_min_query(vector<vector<int>>& perm, const vector<int>& index, const int r){
    vector<vector<int>>candidate;
    for(vector<int>& p : perm){
        vector<int>ord;
        for(int& x : p){
            if(x == index[0] || x == index[1] || x == index[2] || x == index[3]){
                ord.emplace_back(x);
            }
        }
        for(int i = 0; i < 4; i++){
            if(index[3] == ord[i]){
                if((i == 3 && index[r] == ord[0]) || (i < 3 && index[r] == ord[i + 1])){
                    candidate.emplace_back(p);
                }
                break;
            }
        }
    }
    return candidate;
}
void orderCoins(){
    vector<int>_p(6);
    iota(_p.begin(), _p.end(), 1);
    vector<vector<int>>perm;
    do{
        perm.emplace_back(_p);
    } while(next_permutation(_p.begin(), _p.end()));
    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>index = {i, j, k};
                    vector<vector<int>>_max, _min, _median;
                    for(int r = 0; r < 3; r++){
                        update_max(_min, get_min_query(perm, index, r));
                        update_max(_max, get_max_query(perm, index, r));
                        update_max(_median, get_median_query(perm, index, r));
                    }
                    for(int t = k + 1; t < 7; t++){
                        vector<int>index = {i, j, k, t};
                        for(int _i = 0; _i < 4; _i++){
                            swap(index[_i], index[3]);
                            vector<vector<int>>_next_min;
                            for(int r = 0; r < 3; r++){
                                update_max(_next_min, get_next_min_query(perm, index, r));
                            }
                            if(update_min(best, _next_min)){
                                query = make_pair(index, 3);
                            }
                            swap(index[_i], index[3]);
                        }
                    }
                    if(update_min(best, _min)){
                        query = make_pair(index, 0);
                    }
                    if(update_min(best, _max)){
                        query = make_pair(index, 1);
                    }
                    if(update_min(best, _median)){
                        query = make_pair(index, 2);
                    }
                }
            }
        }
        if(query.second == 0){
            int x = getLightest(query.first[0], query.first[1], query.first[2]);
            perm = get_min_query(perm, query.first, x == query.first[0] ? 0 : (x == query.first[1] ? 1 : 2));
        }
        else if(query.second == 1){
            int x = getHeaviest(query.first[0], query.first[1], query.first[2]);
            perm = get_max_query(perm, query.first, x == query.first[0] ? 0 : (x == query.first[1] ? 1 : 2));
        }
        else if(query.second == 2){
            int x = getMedian(query.first[0], query.first[1], query.first[2]);
            perm = get_median_query(perm, query.first, x == query.first[0] ? 0 : (x == query.first[1] ? 1 : 2));
        }
        else{
            int x = getNextLightest(query.first[0], query.first[1], query.first[2], query.first[3]);
            perm = get_next_min_query(perm, query.first, x == query.first[0] ? 0 : (x == query.first[1] ? 1 : 2));
        }
    }
    __answer(perm[0]);
}

• Subtask 1: 72.9167 / 100