제출 #1165220

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1165220		SmuggingSpun	Scales (IOI15_scales)	C++20	71.43 / 100	95 ms	584 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;
}
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));
                    }
                    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{
            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));
        }
    }
    __answer(perm[0]);
}

• Subtask 1: 71.4286 / 100