Submission #562939

#	Time	Username	Problem	Language	Result	Execution time	Memory
562939		hoanghq2004	Scales (IOI15_scales)	C++14	72.92 / 100	95 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 A[6];
//
//int getHeaviest(int a, int b, int c) {
//    if (A[a] > A[b] && A[a] > A[c]) return a;
//    if (A[b] > A[a] && A[b] > A[c]) return b;
//    return c;
//}
//
//int getLightest(int a, int b, int c) {
//    if (A[a] < A[b] && A[a] < A[c]) return a;
//    if (A[b] < A[a] && A[b] < A[c]) return b;
//    return c;
//}
//int getMedian(int a, int b, int c) {
//    if (A[a] > A[b] && A[a] < A[c]) return a;
//    if (A[a] > A[c] && A[a] < A[b]) return a;
//    if (A[b] > A[a] && A[b] < A[c]) return b;
//    if (A[b] > A[c] && A[b] < A[a]) return b;
//    return c;
//}
//
//int getNextLightest(int a, int b, int c, int d) {
//    int x = -1;
//    if (A[a] > A[d] && (x == -1 || A[a] < A[x])) x = a;
//    if (A[b] > A[d] && (x == -1 || A[b] < A[x])) x = b;
//    if (A[c] > A[d] && (x == -1 || A[c] < A[x])) x = c;
//    if (x != -1) return x;
//    return getLightest(a, b, c);
//}

set <vector <int> > s;

struct query {
    int a, b, c, d, type;
    int operator < (const query& other) const {
        return make_tuple(a, b, c, d, type) < make_tuple(other.a, other.b, other.c, other.d, other.type);
    }
};

vector <query> ask;

void init(int T) {
    vector <int> p;
    for (int i = 0; i < 6; ++i) p.push_back(i);
    do {
        s.insert(p);
    } while (next_permutation(p.begin(), p.end()));
    for (int a = 0; a < 6; ++a)
        for (int b = a + 1; b < 6; ++b)
            for (int c = b + 1; c < 6; ++c) {
                ask.push_back({a, b, c, 0, 0});
                ask.push_back({a, b, c, 0, 1});
                ask.push_back({a, b, c, 0, 2});
                for (int d = 0; d < 6; ++d) {
                    if (a == d || b == d || c == d) continue;
                    ask.push_back({a, b, c, d, 3});
                }
            }
}


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) assert(W[i] == A[i + 1]), cout << W[i] << ' ';
//    cout << endl;
//}

void orderCoins() {
    srand(time(nullptr));
    set <vector <int> > cands = s;
    while (1) {
        random_shuffle(ask.begin(), ask.end());
        if (cands.size() == 1) {
            int W[6];
            for (int i = 0; i < 6; ++i) W[(*cands.begin())[i]] = i + 1;
            answer(W);
            return;
        }
        query best;
        int cur = 1e9;
        for (auto _: ask) {
            auto [a, b, c, d, type] = _;
            if (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 (cur > max(cnt_a, cnt_b, cnt_c)) {
                    cur = max(cnt_a, cnt_b, cnt_c);
                    best = _;
                }
            } else if (type == 1) {
                int 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 (cur > max(cnt_a, cnt_b, cnt_c)) {
                    cur = max(cnt_a, cnt_b, cnt_c);
                    best = _;
                }
            } else if (type == 2) {
                int 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 (cur > max(cnt_a, cnt_b, cnt_c)) {
                    cur = max(cnt_a, cnt_b, cnt_c);
                    best = _;
                }
            } else {
                int 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 (cur > max(cnt_a, cnt_b, cnt_c)) {
                    cur = max(cnt_a, cnt_b, cnt_c);
                    best = _;
                }
            }
        }
        auto [a, b, c, d, type] = best;
        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);
//    int T;
//    cin >> T;
//    init(T);
//    for (int i = 1; i <= T; ++i) {
//        for (int j = 1; j <= 6; ++j) cin >> A[j];
//        orderCoins();
//    }
////    orderCoins();
//}

Compilation message (stderr)

scales.cpp: In function 'void init(int)':
scales.cpp:57:15: warning: unused parameter 'T' [-Wunused-parameter]
   57 | void init(int T) {
      |           ~~~~^
scales.cpp: In function 'void orderCoins()':
scales.cpp:88:15: warning: conversion from 'time_t' {aka 'long int'} to 'unsigned int' may change value [-Wconversion]
   88 |     srand(time(nullptr));
      |           ~~~~^~~~~~~~~
scales.cpp:101:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  101 |             auto [a, b, c, d, type] = _;
      |                  ^
scales.cpp:157:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  157 |         auto [a, b, c, d, type] = best;
      |              ^
scales.cpp:160:32: warning: 'best.query::a' may be used uninitialized in this function [-Wmaybe-uninitialized]
  160 |             int x = getHeaviest(a + 1, b + 1, c + 1) - 1;
      |                     ~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~
scales.cpp:160:32: warning: 'best.query::b' may be used uninitialized in this function [-Wmaybe-uninitialized]
scales.cpp:160:32: warning: 'best.query::c' may be used uninitialized in this function [-Wmaybe-uninitialized]
scales.cpp:175:31: warning: 'best.query::d' may be used uninitialized in this function [-Wmaybe-uninitialized]
  175 |                 if (p[a] > p[d] && (y == -1 || p[a] < p[y])) y = a;
      |                               ^
scales.cpp:167:16: warning: 'best.query::type' may be used uninitialized in this function [-Wmaybe-uninitialized]
  167 |         } else if (type == 2) {
      |                ^~

• Subtask 1: 72.916667 / 100