Submission #551658

#	Time	Username	Problem	Language	Result	Execution time	Memory
551658		hoanghq2004	Scales (IOI15_scales)	C++14	0 / 100	1086 ms	404 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 a, int b, int c) {
//    cout << "0 " << a << ' ' << b << ' ' << c << endl;
//    int x;
//    cin >> x;
//    return x;
//}
//int getLightest(int a, int b, int c) {
//    cout << "1 " << a << ' ' << b << ' ' << c << endl;
//    int x;
//    cin >> x;
//    return x;
//}
//int getMedian(int a, int b, int c) {
//    cout << "2 " << a << ' ' << b << ' ' << c << endl;
//    int x;
//    cin >> x;
//    return x;
//}
//int getNextLightest(int a, int b, int c, int d) {
//    cout << "3 " << a << ' ' << b << ' ' << c << ' ' << d << endl;
//    int x;
//    cin >> x;
//    return x;
//}

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 answer(int W[]) {
//    for (int i = 0; i < 6; ++i) cout << W[i] << ' ';
//    exit(0);
//}

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);
//    init(1);
//    orderCoins();
//}

Compilation message (stderr)

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

• Subtask 1: 0 / 100