답안 #562954

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
562954	2022-05-15T17:58:28 Z	hoanghq2004	저울 (IOI15_scales)	C++14	100 / 100	119 ms	468 KB

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) {
        for (int a = 0; a < 6; ++a)
        for (int b = a + 1; b < 6; ++b)
            for (int c = b + 1; c < 6; ++c) {
                    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) {
        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;
                }
                assert(max(cnt_a, cnt_b, 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;
                }
                assert(max(cnt_a, cnt_b, 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;
                }
                                assert(max(cnt_a, cnt_b, 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;
                }
                assert(max(cnt_a, cnt_b, 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

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:92:15: warning: conversion from 'time_t' {aka 'long int'} to 'unsigned int' may change value [-Wconversion]
   92 |     srand(time(nullptr));
      |           ~~~~^~~~~~~~~
scales.cpp:104:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  104 |             auto [a, b, c, d, type] = _;
      |                  ^
scales.cpp:166:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  166 |         auto [a, b, c, d, type] = best;
      |              ^
scales.cpp:169:32: warning: 'best.query::a' may be used uninitialized in this function [-Wmaybe-uninitialized]
  169 |             int x = getHeaviest(a + 1, b + 1, c + 1) - 1;
      |                     ~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~
scales.cpp:169:32: warning: 'best.query::b' may be used uninitialized in this function [-Wmaybe-uninitialized]
scales.cpp:169:32: warning: 'best.query::c' may be used uninitialized in this function [-Wmaybe-uninitialized]
scales.cpp:184:31: warning: 'best.query::d' may be used uninitialized in this function [-Wmaybe-uninitialized]
  184 |                 if (p[a] > p[d] && (y == -1 || p[a] < p[y])) y = a;
      |                               ^
scales.cpp:176:16: warning: 'best.query::type' may be used uninitialized in this function [-Wmaybe-uninitialized]
  176 |         } else if (type == 2) {
      |                ^~

Subtask #1

100.0 / 100.0

#	결과	실행 시간	메모리	Grader output
1	Correct	97 ms	444 KB	Output is correct
2	Correct	103 ms	444 KB	Output is correct
3	Correct	97 ms	444 KB	Output is correct
4	Correct	97 ms	460 KB	Output is correct
5	Correct	101 ms	448 KB	Output is correct
6	Correct	95 ms	440 KB	Output is correct
7	Correct	96 ms	444 KB	Output is correct
8	Correct	98 ms	340 KB	Output is correct
9	Correct	97 ms	460 KB	Output is correct
10	Correct	92 ms	340 KB	Output is correct
11	Correct	95 ms	444 KB	Output is correct
12	Correct	96 ms	340 KB	Output is correct
13	Correct	111 ms	340 KB	Output is correct
14	Correct	94 ms	340 KB	Output is correct
15	Correct	111 ms	468 KB	Output is correct
16	Correct	105 ms	444 KB	Output is correct
17	Correct	98 ms	340 KB	Output is correct
18	Correct	92 ms	456 KB	Output is correct
19	Correct	92 ms	444 KB	Output is correct
20	Correct	96 ms	340 KB	Output is correct
21	Correct	95 ms	444 KB	Output is correct
22	Correct	119 ms	444 KB	Output is correct
23	Correct	94 ms	444 KB	Output is correct
24	Correct	92 ms	340 KB	Output is correct
25	Correct	102 ms	444 KB	Output is correct
26	Correct	95 ms	440 KB	Output is correct
27	Correct	112 ms	340 KB	Output is correct
28	Correct	106 ms	340 KB	Output is correct
29	Correct	97 ms	440 KB	Output is correct
30	Correct	95 ms	440 KB	Output is correct
31	Correct	96 ms	340 KB	Output is correct
32	Correct	105 ms	444 KB	Output is correct
33	Correct	116 ms	444 KB	Output is correct
34	Correct	93 ms	444 KB	Output is correct
35	Correct	100 ms	340 KB	Output is correct
36	Correct	93 ms	444 KB	Output is correct
37	Correct	102 ms	444 KB	Output is correct
38	Correct	119 ms	444 KB	Output is correct
39	Correct	91 ms	448 KB	Output is correct
40	Correct	93 ms	440 KB	Output is correct