답안 #725810

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
725810	2023-04-18T06:18:33 Z	becaido	저울 (IOI15_scales)	C++17	100 / 100	7 ms	372 KB

scales

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,popcnt,sse4,abm")
#include <bits/stdc++.h>
using namespace std;

#ifndef WAIMAI
#include "scales.h"
#endif

#ifdef WAIMAI
#define debug(HEHE...) cout << "[" << #HEHE << "] : ", dout(HEHE)
void dout() {cout << '\n';}
template<typename T, typename...U>
void dout (T t, U...u) {cout << t << (sizeof... (u) ? ", " : ""), dout (u...);}
#else
#define debug(...) 7122
#endif

#define ll long long
#define Waimai ios::sync_with_stdio(false), cin.tie(0)
#define FOR(x,a,b) for (int x = a, I = b; x <= I; x++)
#define pb emplace_back
#define F first
#define S second

#ifdef WAIMAI
#define _MAXN 6
#define _MAX_ANSWER_CALLS 1

static int _realC[_MAXN];
static int _ind[_MAXN];
static int _numQueries;
static int _numAnswerCalls;

static int _getNumberOfTests() {
    int T;
    cin >> T;
    return T;
}

static void _initNewTest() {
    int i, ret;

    for (i = 0; i < _MAXN; i++) {
        cin >> _realC[i];
        _realC[i]--;
        _ind[_realC[i]] = i;
    }

    _numQueries = 0;
    _numAnswerCalls = 0;
}

void answer(int W[]) {
    int i;
    _numAnswerCalls++;
    if (_numAnswerCalls > _MAX_ANSWER_CALLS)
        return;
    for (i = 0; i < 6; i++) cout << W[i] << ' ';
    cout << "\n" << _numQueries << '\n';
}

static void _checkQuery(int A, int B, int C, int D) {
    if (D == -1) {
        if (A < 1 || A > 6 || B < 1 || B > 6 || C < 1 || C > 6)
            assert(0);
        if (A == B || B == C || A == C)
            assert(0);
    }
    else {
        if (A < 1 || A > 6 || B < 1 || B > 6 || C < 1 || C > 6 || D < 1 || D > 6)
            assert(0);
        if (A == B || A == C || A == D || B == C || B == D || C == D)
            assert(0);
    }
}

int getMedian(int A, int B, int C) {
    _numQueries++;
    _checkQuery(A, B, C, -1);

    A--; B--; C--;

    if (_ind[B] < _ind[A] && _ind[A] < _ind[C])
        return A + 1;

    if (_ind[C] < _ind[A] && _ind[A] < _ind[B])
        return A + 1;

    if (_ind[A] < _ind[B] && _ind[B] < _ind[C])
        return B + 1;

    if (_ind[C] < _ind[B] && _ind[B] < _ind[A])
        return B + 1;

    return C + 1;
}

int getHeaviest(int A, int B, int C) {
    _numQueries++;
    _checkQuery(A, B, C, -1);

    A--; B--; C--;

    if (_ind[A] > _ind[B] && _ind[A] > _ind[C])
        return A + 1;

    if (_ind[B] > _ind[A] && _ind[B] > _ind[C])
        return B + 1;

    return C + 1;
}

int getLightest(int A, int B, int C) {
    _numQueries++;
    _checkQuery(A, B, C, -1);

    A--; B--; C--;

    if (_ind[A] < _ind[B] && _ind[A] < _ind[C])
        return A + 1;

    if (_ind[B] < _ind[A] && _ind[B] < _ind[C])
        return B + 1;

    return C + 1;
}

int getNextLightest(int A, int B, int C, int D) {
    int allLess = 1;

    _numQueries++;
    _checkQuery(A, B, C, D);

    A--; B--; C--; D--;

    if (_ind[A] > _ind[D] || _ind[B] > _ind[D] || _ind[C] > _ind[D])
        allLess = 0;

    if (allLess == 1) {
        if (_ind[A] < _ind[B] && _ind[A] < _ind[C])
            return A + 1;

        if (_ind[B] < _ind[A] && _ind[B] < _ind[C])
            return B + 1;

        return C + 1;
    }

    if (_ind[A] > _ind[D]) {
        if ((_ind[A] < _ind[B] || _ind[B] < _ind[D]) && (_ind[A] < _ind[C] || _ind[C] < _ind[D]))
            return A + 1;
    }

    if (_ind[B] > _ind[D]) {
        if ((_ind[B] < _ind[A] || _ind[A] < _ind[D]) && (_ind[B] < _ind[C] || _ind[C] < _ind[D]))
            return B + 1;
    }

    return C + 1;
}
#endif

const int MAX = 720;

array<int, 6> P[MAX];
int pos[MAX][7];

struct Tree {
    int ty, a, b, c, d;
    Tree *nxt[3];
    Tree() {}
    Tree(int ty, int a, int b, int c, int d = 0) : ty(ty), a(a), b(b), c(c), d(d) {}
    tuple<int, int, int, int, int> id() {
        return {ty, a, b, c, d};
    }
};
Tree *root;

bool build(Tree *&t, vector<int> cur, int lim) {
    if (cur.size() <= 1) return 1;
    t = new Tree();
    FOR (ty, 1, 3) FOR (i, 1, 6) FOR (j, i + 1, 6) FOR (k, j + 1, 6) {
        *t = Tree(ty, i, j, k);
        vector<int> vi, vj, vk;
        bool f = 1;
        for (int id : cur) {
            int cp;
            if (ty == 1) cp = min({pos[id][i], pos[id][j], pos[id][k]});
            if (ty == 2) cp = max({pos[id][i], pos[id][j], pos[id][k]});
            if (ty == 3) cp = pos[id][i] + pos[id][j] + pos[id][k] - min({pos[id][i], pos[id][j], pos[id][k]}) - max({pos[id][i], pos[id][j], pos[id][k]});
            (pos[id][i] == cp ? vi : pos[id][j] == cp ? vj : vk).pb(id);
            if (max({vi.size(), vj.size(), vk.size()}) > lim) {
                f = 0;
                break;
            }
        }
        if (f) f &= build(t->nxt[0], vi, lim / 3);
        if (f) f &= build(t->nxt[1], vj, lim / 3);
        if (f) f &= build(t->nxt[2], vk, lim / 3);
        if (f) return 1;
    }
    FOR (d, 1, 6) FOR (i, 1, 6) if (i != d) FOR (j, i + 1, 6) if (j != d) FOR (k, j + 1, 6) if (k != d) {
        *t = Tree(4, i, j, k, d);
        vector<int> vi, vj, vk;
        bool f = 1;
        for (int id : cur) {
            int pi = pos[id][i], pj = pos[id][j], pk = pos[id][k], pd = pos[id][d], cp = 6;
            for (int xp : {pi, pj, pk}) if (xp > pd) cp = min(cp, xp);
            if (cp == 6) cp = min({pi, pj, pk});
            (pos[id][i] == cp ? vi : pos[id][j] == cp ? vj : vk).pb(id);
            if (max({vi.size(), vj.size(), vk.size()}) > lim) {
                f = 0;
                break;
            }
        }
        if (f) f &= build(t->nxt[0], vi, lim / 3);
        if (f) f &= build(t->nxt[1], vj, lim / 3);
        if (f) f &= build(t->nxt[2], vk, lim / 3);
        if (f) return 1;
    }
    delete(t);
    return 0;
}

void init(int T) {
    array<int, 6> a;
    iota(a.begin(), a.end(), 1);
    FOR (i, 0, MAX - 1) {
        P[i] = a;
        FOR (j, 0, 5) pos[i][a[j]] = j;
        next_permutation(a.begin(), a.end());
    }
    vector<int> all(MAX);
    iota(all.begin(), all.end(), 0);
    build(root, all, 243);
}

void orderCoins() {
    vector<int> all(MAX);
    iota(all.begin(), all.end(), 0);
    Tree *cur = root;
    while (all.size() > 1) {
        int result;
        auto [ty, a, b, c, d] = cur->id();
        if (ty == 1) result = getLightest(a, b, c);
        if (ty == 2) result = getHeaviest(a, b, c);
        if (ty == 3) result = getMedian(a, b, c);
        if (ty == 4) result = getNextLightest(a, b, c, d);
        vector<int> tmp;
        for (int id : all) {
            int pi = pos[id][a], pj = pos[id][b], pk = pos[id][c];
            if (ty == 1 && min({pi, pj, pk}) == pos[id][result]) tmp.pb(id);
            if (ty == 2 && max({pi, pj, pk}) == pos[id][result]) tmp.pb(id);
            if (ty == 3 && pi + pj + pk - min({pi, pj, pk}) - max({pi, pj, pk}) == pos[id][result]) tmp.pb(id);
            if (ty == 4) {
                int mn = 6;
                for (int xp : {pi, pj, pk}) if (xp > pos[id][d]) mn = min(mn, xp);
                if (mn == 6) mn = min({pi, pj, pk});
                if (mn == pos[id][result]) tmp.pb(id);
            }
        }
        all = tmp;
        cur = (result == a ? cur->nxt[0] : result == b ? cur->nxt[1] : cur->nxt[2]);
    }
    int ans[6];
    FOR (i, 0, 5) ans[i] = P[all[0]][i];
    answer(ans);
}

#ifdef WAIMAI
int main() {
    int T, i;

    T = _getNumberOfTests();
    init(T);

    for (i = 1; i <= T; i++) {
        _initNewTest();
        orderCoins();
    }

    return 0;
}
#endif

Compilation message

scales.cpp: In constructor 'Tree::Tree(int, int, int, int, int)':
scales.cpp:173:43: warning: declaration of 'd' shadows a member of 'Tree' [-Wshadow]
  173 |     Tree(int ty, int a, int b, int c, int d = 0) : ty(ty), a(a), b(b), c(c), d(d) {}
      |                                       ~~~~^~~~~
scales.cpp:170:22: note: shadowed declaration is here
  170 |     int ty, a, b, c, d;
      |                      ^
scales.cpp:173:36: warning: declaration of 'c' shadows a member of 'Tree' [-Wshadow]
  173 |     Tree(int ty, int a, int b, int c, int d = 0) : ty(ty), a(a), b(b), c(c), d(d) {}
      |                                ~~~~^
scales.cpp:170:19: note: shadowed declaration is here
  170 |     int ty, a, b, c, d;
      |                   ^
scales.cpp:173:29: warning: declaration of 'b' shadows a member of 'Tree' [-Wshadow]
  173 |     Tree(int ty, int a, int b, int c, int d = 0) : ty(ty), a(a), b(b), c(c), d(d) {}
      |                         ~~~~^
scales.cpp:170:16: note: shadowed declaration is here
  170 |     int ty, a, b, c, d;
      |                ^
scales.cpp:173:22: warning: declaration of 'a' shadows a member of 'Tree' [-Wshadow]
  173 |     Tree(int ty, int a, int b, int c, int d = 0) : ty(ty), a(a), b(b), c(c), d(d) {}
      |                  ~~~~^
scales.cpp:170:13: note: shadowed declaration is here
  170 |     int ty, a, b, c, d;
      |             ^
scales.cpp:173:14: warning: declaration of 'ty' shadows a member of 'Tree' [-Wshadow]
  173 |     Tree(int ty, int a, int b, int c, int d = 0) : ty(ty), a(a), b(b), c(c), d(d) {}
      |          ~~~~^~
scales.cpp:170:9: note: shadowed declaration is here
  170 |     int ty, a, b, c, d;
      |         ^~
scales.cpp: In constructor 'Tree::Tree(int, int, int, int, int)':
scales.cpp:173:43: warning: declaration of 'd' shadows a member of 'Tree' [-Wshadow]
  173 |     Tree(int ty, int a, int b, int c, int d = 0) : ty(ty), a(a), b(b), c(c), d(d) {}
      |                                       ~~~~^~~~~
scales.cpp:170:22: note: shadowed declaration is here
  170 |     int ty, a, b, c, d;
      |                      ^
scales.cpp:173:36: warning: declaration of 'c' shadows a member of 'Tree' [-Wshadow]
  173 |     Tree(int ty, int a, int b, int c, int d = 0) : ty(ty), a(a), b(b), c(c), d(d) {}
      |                                ~~~~^
scales.cpp:170:19: note: shadowed declaration is here
  170 |     int ty, a, b, c, d;
      |                   ^
scales.cpp:173:29: warning: declaration of 'b' shadows a member of 'Tree' [-Wshadow]
  173 |     Tree(int ty, int a, int b, int c, int d = 0) : ty(ty), a(a), b(b), c(c), d(d) {}
      |                         ~~~~^
scales.cpp:170:16: note: shadowed declaration is here
  170 |     int ty, a, b, c, d;
      |                ^
scales.cpp:173:22: warning: declaration of 'a' shadows a member of 'Tree' [-Wshadow]
  173 |     Tree(int ty, int a, int b, int c, int d = 0) : ty(ty), a(a), b(b), c(c), d(d) {}
      |                  ~~~~^
scales.cpp:170:13: note: shadowed declaration is here
  170 |     int ty, a, b, c, d;
      |             ^
scales.cpp:173:14: warning: declaration of 'ty' shadows a member of 'Tree' [-Wshadow]
  173 |     Tree(int ty, int a, int b, int c, int d = 0) : ty(ty), a(a), b(b), c(c), d(d) {}
      |          ~~~~^~
scales.cpp:170:9: note: shadowed declaration is here
  170 |     int ty, a, b, c, d;
      |         ^~
scales.cpp: In constructor 'Tree::Tree(int, int, int, int, int)':
scales.cpp:173:43: warning: declaration of 'd' shadows a member of 'Tree' [-Wshadow]
  173 |     Tree(int ty, int a, int b, int c, int d = 0) : ty(ty), a(a), b(b), c(c), d(d) {}
      |                                       ~~~~^~~~~
scales.cpp:170:22: note: shadowed declaration is here
  170 |     int ty, a, b, c, d;
      |                      ^
scales.cpp:173:36: warning: declaration of 'c' shadows a member of 'Tree' [-Wshadow]
  173 |     Tree(int ty, int a, int b, int c, int d = 0) : ty(ty), a(a), b(b), c(c), d(d) {}
      |                                ~~~~^
scales.cpp:170:19: note: shadowed declaration is here
  170 |     int ty, a, b, c, d;
      |                   ^
scales.cpp:173:29: warning: declaration of 'b' shadows a member of 'Tree' [-Wshadow]
  173 |     Tree(int ty, int a, int b, int c, int d = 0) : ty(ty), a(a), b(b), c(c), d(d) {}
      |                         ~~~~^
scales.cpp:170:16: note: shadowed declaration is here
  170 |     int ty, a, b, c, d;
      |                ^
scales.cpp:173:22: warning: declaration of 'a' shadows a member of 'Tree' [-Wshadow]
  173 |     Tree(int ty, int a, int b, int c, int d = 0) : ty(ty), a(a), b(b), c(c), d(d) {}
      |                  ~~~~^
scales.cpp:170:13: note: shadowed declaration is here
  170 |     int ty, a, b, c, d;
      |             ^
scales.cpp:173:14: warning: declaration of 'ty' shadows a member of 'Tree' [-Wshadow]
  173 |     Tree(int ty, int a, int b, int c, int d = 0) : ty(ty), a(a), b(b), c(c), d(d) {}
      |          ~~~~^~
scales.cpp:170:9: note: shadowed declaration is here
  170 |     int ty, a, b, c, d;
      |         ^~
scales.cpp: In function 'bool build(Tree*&, std::vector<int>, int)':
scales.cpp:21:36: warning: declaration of 'I' shadows a previous local [-Wshadow]
   21 | #define FOR(x,a,b) for (int x = a, I = b; x <= I; x++)
      |                                    ^
scales.cpp:183:20: note: in expansion of macro 'FOR'
  183 |     FOR (ty, 1, 3) FOR (i, 1, 6) FOR (j, i + 1, 6) FOR (k, j + 1, 6) {
      |                    ^~~
scales.cpp:21:36: note: shadowed declaration is here
   21 | #define FOR(x,a,b) for (int x = a, I = b; x <= I; x++)
      |                                    ^
scales.cpp:183:5: note: in expansion of macro 'FOR'
  183 |     FOR (ty, 1, 3) FOR (i, 1, 6) FOR (j, i + 1, 6) FOR (k, j + 1, 6) {
      |     ^~~
scales.cpp:21:36: warning: declaration of 'I' shadows a previous local [-Wshadow]
   21 | #define FOR(x,a,b) for (int x = a, I = b; x <= I; x++)
      |                                    ^
scales.cpp:183:34: note: in expansion of macro 'FOR'
  183 |     FOR (ty, 1, 3) FOR (i, 1, 6) FOR (j, i + 1, 6) FOR (k, j + 1, 6) {
      |                                  ^~~
scales.cpp:21:36: note: shadowed declaration is here
   21 | #define FOR(x,a,b) for (int x = a, I = b; x <= I; x++)
      |                                    ^
scales.cpp:183:20: note: in expansion of macro 'FOR'
  183 |     FOR (ty, 1, 3) FOR (i, 1, 6) FOR (j, i + 1, 6) FOR (k, j + 1, 6) {
      |                    ^~~
scales.cpp:21:36: warning: declaration of 'I' shadows a previous local [-Wshadow]
   21 | #define FOR(x,a,b) for (int x = a, I = b; x <= I; x++)
      |                                    ^
scales.cpp:183:52: note: in expansion of macro 'FOR'
  183 |     FOR (ty, 1, 3) FOR (i, 1, 6) FOR (j, i + 1, 6) FOR (k, j + 1, 6) {
      |                                                    ^~~
scales.cpp:21:36: note: shadowed declaration is here
   21 | #define FOR(x,a,b) for (int x = a, I = b; x <= I; x++)
      |                                    ^
scales.cpp:183:34: note: in expansion of macro 'FOR'
  183 |     FOR (ty, 1, 3) FOR (i, 1, 6) FOR (j, i + 1, 6) FOR (k, j + 1, 6) {
      |                                  ^~~
scales.cpp:193:56: warning: comparison of integer expressions of different signedness: 'long unsigned int' and 'int' [-Wsign-compare]
  193 |             if (max({vi.size(), vj.size(), vk.size()}) > lim) {
      |                 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
scales.cpp:21:36: warning: declaration of 'I' shadows a previous local [-Wshadow]
   21 | #define FOR(x,a,b) for (int x = a, I = b; x <= I; x++)
      |                                    ^
scales.cpp:203:19: note: in expansion of macro 'FOR'
  203 |     FOR (d, 1, 6) FOR (i, 1, 6) if (i != d) FOR (j, i + 1, 6) if (j != d) FOR (k, j + 1, 6) if (k != d) {
      |                   ^~~
scales.cpp:21:36: note: shadowed declaration is here
   21 | #define FOR(x,a,b) for (int x = a, I = b; x <= I; x++)
      |                                    ^
scales.cpp:203:5: note: in expansion of macro 'FOR'
  203 |     FOR (d, 1, 6) FOR (i, 1, 6) if (i != d) FOR (j, i + 1, 6) if (j != d) FOR (k, j + 1, 6) if (k != d) {
      |     ^~~
scales.cpp:21:36: warning: declaration of 'I' shadows a previous local [-Wshadow]
   21 | #define FOR(x,a,b) for (int x = a, I = b; x <= I; x++)
      |                                    ^
scales.cpp:203:45: note: in expansion of macro 'FOR'
  203 |     FOR (d, 1, 6) FOR (i, 1, 6) if (i != d) FOR (j, i + 1, 6) if (j != d) FOR (k, j + 1, 6) if (k != d) {
      |                                             ^~~
scales.cpp:21:36: note: shadowed declaration is here
   21 | #define FOR(x,a,b) for (int x = a, I = b; x <= I; x++)
      |                                    ^
scales.cpp:203:19: note: in expansion of macro 'FOR'
  203 |     FOR (d, 1, 6) FOR (i, 1, 6) if (i != d) FOR (j, i + 1, 6) if (j != d) FOR (k, j + 1, 6) if (k != d) {
      |                   ^~~
scales.cpp:21:36: warning: declaration of 'I' shadows a previous local [-Wshadow]
   21 | #define FOR(x,a,b) for (int x = a, I = b; x <= I; x++)
      |                                    ^
scales.cpp:203:75: note: in expansion of macro 'FOR'
  203 |     FOR (d, 1, 6) FOR (i, 1, 6) if (i != d) FOR (j, i + 1, 6) if (j != d) FOR (k, j + 1, 6) if (k != d) {
      |                                                                           ^~~
scales.cpp:21:36: note: shadowed declaration is here
   21 | #define FOR(x,a,b) for (int x = a, I = b; x <= I; x++)
      |                                    ^
scales.cpp:203:45: note: in expansion of macro 'FOR'
  203 |     FOR (d, 1, 6) FOR (i, 1, 6) if (i != d) FOR (j, i + 1, 6) if (j != d) FOR (k, j + 1, 6) if (k != d) {
      |                                             ^~~
scales.cpp:212:56: warning: comparison of integer expressions of different signedness: 'long unsigned int' and 'int' [-Wsign-compare]
  212 |             if (max({vi.size(), vj.size(), vk.size()}) > lim) {
      |                 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
scales.cpp: In function 'void init(int)':
scales.cpp:21:36: warning: declaration of 'I' shadows a previous local [-Wshadow]
   21 | #define FOR(x,a,b) for (int x = a, I = b; x <= I; x++)
      |                                    ^
scales.cpp:231:9: note: in expansion of macro 'FOR'
  231 |         FOR (j, 0, 5) pos[i][a[j]] = j;
      |         ^~~
scales.cpp:21:36: note: shadowed declaration is here
   21 | #define FOR(x,a,b) for (int x = a, I = b; x <= I; x++)
      |                                    ^
scales.cpp:229:5: note: in expansion of macro 'FOR'
  229 |     FOR (i, 0, MAX - 1) {
      |     ^~~
scales.cpp:226:15: warning: unused parameter 'T' [-Wunused-parameter]
  226 | void init(int T) {
      |           ~~~~^
scales.cpp: In function 'void orderCoins()':
scales.cpp:264:56: warning: 'result' may be used uninitialized in this function [-Wmaybe-uninitialized]
  264 |         cur = (result == a ? cur->nxt[0] : result == b ? cur->nxt[1] : cur->nxt[2]);
      |                                            ~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1

100.0 / 100.0

#	결과	실행 시간	메모리	Grader output
1	Correct	4 ms	340 KB	Output is correct
2	Correct	4 ms	340 KB	Output is correct
3	Correct	4 ms	340 KB	Output is correct
4	Correct	4 ms	372 KB	Output is correct
5	Correct	4 ms	340 KB	Output is correct
6	Correct	4 ms	340 KB	Output is correct
7	Correct	4 ms	340 KB	Output is correct
8	Correct	4 ms	340 KB	Output is correct
9	Correct	4 ms	340 KB	Output is correct
10	Correct	7 ms	352 KB	Output is correct
11	Correct	4 ms	340 KB	Output is correct
12	Correct	4 ms	340 KB	Output is correct
13	Correct	4 ms	340 KB	Output is correct
14	Correct	5 ms	304 KB	Output is correct
15	Correct	4 ms	300 KB	Output is correct
16	Correct	4 ms	340 KB	Output is correct
17	Correct	4 ms	340 KB	Output is correct
18	Correct	4 ms	304 KB	Output is correct
19	Correct	4 ms	340 KB	Output is correct
20	Correct	4 ms	340 KB	Output is correct
21	Correct	5 ms	340 KB	Output is correct
22	Correct	4 ms	308 KB	Output is correct
23	Correct	5 ms	340 KB	Output is correct
24	Correct	4 ms	340 KB	Output is correct
25	Correct	4 ms	340 KB	Output is correct
26	Correct	4 ms	340 KB	Output is correct
27	Correct	4 ms	344 KB	Output is correct
28	Correct	4 ms	340 KB	Output is correct
29	Correct	4 ms	340 KB	Output is correct
30	Correct	4 ms	304 KB	Output is correct
31	Correct	4 ms	340 KB	Output is correct
32	Correct	4 ms	340 KB	Output is correct
33	Correct	4 ms	364 KB	Output is correct
34	Correct	4 ms	300 KB	Output is correct
35	Correct	4 ms	340 KB	Output is correct
36	Correct	5 ms	340 KB	Output is correct
37	Correct	4 ms	304 KB	Output is correct
38	Correct	4 ms	308 KB	Output is correct
39	Correct	4 ms	304 KB	Output is correct
40	Correct	5 ms	308 KB	Output is correct