제출 #551635

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
551635		hoanghq2004	저울 (IOI15_scales)	C++14	0 / 100	1099 ms	468 KiB

scales

#include <bits/stdc++.h>
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include "scales.h"

using namespace __gnu_pbds;
using namespace std;

template <typename T>
using ordered_set = tree <T, null_type, less <T>, rb_tree_tag, tree_order_statistics_node_update>;

mt19937 gen(std :: chrono :: system_clock :: now().time_since_epoch().count());
//
//int getHeaviest() {
//
//}
//int getLightest() {
//
//}
//int getMedian() {
//
//}
//int getNextLightest() {
//
//}

set <vector <int> > cands;

void init(int T) {
    vector <int> p;
    for (int i = 0; i < 6; ++i) p.push_back(i);
    do {
        cands.insert(p);
    } while (next_permutation(p.begin(), p.end()));
}

struct query {
    int a, b, c, d, type;
};

vector <query> Q;

#define max(a, b, c) max({a, b, c})
#define min(a, b, c) min({a, b, c})

void orderCoins() {
    while (1) {
        if (cands.size() == 1) {
            int W[6];
            for (int i = 0; i < 6; ++i) W[i] = (*cands.begin())[i] + 1;
            answer(W);
        }
        Q.clear();
        int cur = 1e9;
        for (int a = 0; a < 6; ++a)
            for (int b = a + 1; b < 6; ++b)
                for (int c = b + 1; c < 6; ++c) {
                    // type 0
                    int cnt_a = 0, cnt_b = 0, cnt_c = 0;
                    for (auto p: cands) {
                        if (max(p[a], p[b], p[c]) == p[a]) ++cnt_a;
                        if (max(p[a], p[b], p[c]) == p[b]) ++cnt_b;
                        if (max(p[a], p[b], p[c]) == p[c]) ++cnt_c;
                    }
                    if (max(cnt_a, cnt_b, cnt_c) < cur) {
                        cur = max(cnt_a, cnt_b, cnt_c);
                        Q = {{a, b, c, 0, 0}};
                    } else if (max(cnt_a, cnt_b, cnt_c) == cur) Q.push_back({a, b, c, 0, 0});
                    // type 1
                    cnt_a = 0, cnt_b = 0, cnt_c = 0;
                    for (auto p: cands) {
                        if (min(p[a], p[b], p[c]) == p[a]) ++cnt_a;
                        if (min(p[a], p[b], p[c]) == p[b]) ++cnt_b;
                        if (min(p[a], p[b], p[c]) == p[c]) ++cnt_c;
                    }
                    if (max(cnt_a, cnt_b, cnt_c) < cur) {
                        cur = max(cnt_a, cnt_b, cnt_c);
                        Q = {{a, b, c, 0, 1}};
                    } else if (max(cnt_a, cnt_b, cnt_c) == cur) Q.push_back({a, b, c, 0, 1});
                    // type 2
                    cnt_a = 0, cnt_b = 0, cnt_c = 0;
                    for (auto p: cands) {
                        if (min(p[a], p[b], p[c]) != p[a] && max(p[a], p[b], p[c]) != p[a]) ++cnt_a;
                        if (min(p[a], p[b], p[c]) != p[b] && max(p[a], p[b], p[c]) != p[b]) ++cnt_b;
                        if (min(p[a], p[b], p[c]) != p[c] && max(p[a], p[b], p[c]) != p[c]) ++cnt_c;
                    }
                    if (max(cnt_a, cnt_b, cnt_c) < cur) {
                        cur = max(cnt_a, cnt_b, cnt_c);
                        Q = {{a, b, c, 0, 2}};
                    } else if (max(cnt_a, cnt_b, cnt_c) == cur) Q.push_back({a, b, c, 0, 2});
                    // type 3

                    for (int d = 0; d < 6; ++d) {
                        if (d == a || d == b || d == c) continue;
                        cnt_a = 0, cnt_b = 0, cnt_c = 0;
                        for (auto p: cands) {
                            int x = -1;
                            if (p[a] > p[d] && (x == -1 || p[a] < p[x])) x = a;
                            if (p[b] > p[d] && (x == -1 || p[b] < p[x])) x = b;
                            if (p[c] > p[d] && (x == -1 || p[c] < p[x])) x = c;
                            if (x == -1) {
                                x = a;
                                if (p[b] < p[x]) x = b;
                                if (p[c] < p[x]) x = c;
                            }
                            if (x == a) ++cnt_a;
                            if (x == b) ++cnt_b;
                            if (x == c) ++cnt_c;
                        }
                        if (max(cnt_a, cnt_b, cnt_c) < cur) {
                            cur = max(cnt_a, cnt_b, cnt_c);
                            Q = {{a, b, c, d, 3}};
                        } else if (max(cnt_a, cnt_b, cnt_c) == cur) Q.push_back({a, b, c, d, 3});
                    }

                }
        auto [a, b, c, d, type] = Q[gen() % Q.size()];
        set <vector <int> > ncands;
        if (type == 0) {
            int x = getHeaviest(a + 1, b + 1, c + 1) - 1;
            for (auto p: cands)
                if (max(p[a], p[b], p[c]) == p[x]) ncands.insert(p);
        } else if (type == 1) {
            int x = getLightest(a + 1, b + 1, c + 1) - 1;
            for (auto p: cands)
                if (min(p[a], p[b], p[c]) == p[x]) ncands.insert(p);
        } else if (type == 2) {
            int x = getMedian(a + 1, b + 1, c + 1) - 1;
            for (auto p: cands)
                if (max(p[a], p[b], p[c]) != p[x] && min(p[a], p[b], p[c]) != p[x]) ncands.insert(p);
        } else {
            int x = getNextLightest(a + 1, b + 1, c + 1, d + 1) - 1;
            for (auto p: cands) {
                int y = -1;
                if (p[a] > p[d] && (y == -1 || p[a] < p[y])) y = a;
                if (p[b] > p[d] && (y == -1 || p[b] < p[y])) y = b;
                if (p[c] > p[d] && (y == -1 || p[c] < p[y])) y = c;
                if (y == -1) {
                    y = a;
                    if (p[b] < p[y]) y = b;
                    if (p[c] < p[y]) y = c;
                }
                if (x == y) ncands.insert(p);
            }
        }
        swap(cands, ncands);
    }

}



//int main() {
//    ios :: sync_with_stdio(0); cin.tie(0);
//
//}

컴파일 시 표준 에러 (stderr) 메시지

scales.cpp: In function 'void init(int)':
scales.cpp:31:15: warning: unused parameter 'T' [-Wunused-parameter]
   31 | void init(int T) {
      |           ~~~~^
scales.cpp: In function 'void orderCoins()':
scales.cpp:119:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  119 |         auto [a, b, c, d, type] = Q[gen() % Q.size()];
      |              ^

• Subtask 1: 0 / 100