Submission #830805

#	Time	Username	Problem	Language	Result	Execution time	Memory
830805		drdilyor	Scales (IOI15_scales)	C++17	71.73 / 100	24 ms	756 KiB

scales

#include<bits/stdc++.h>
#include "scales.h"
using namespace std;
using ll = long long;
#define sz(x) int((x).size())

ll pw3[30];
const int n = 6;
const int inf = 1e9;

using st = array<int, 6>;
using op = tuple<int,int,int,int,int>;

map<vector<st>, op> usedop;

array<vector<st>, 3> getNext(vector<st> cur, op op) {
    auto [t, a, b, c, d] = op;
    array<vector<st>, 3> next{{}};
    if (t == 0) {
        for (auto& i : cur) {
            int mn = min({i[a], i[b], i[c]});
            if (i[a] == mn)
                next[0].push_back(i);
            else if (i[b] == mn)
                next[1].push_back(i);
            else
                next[2].push_back(i);
        }
    } else if (t == 1) {
        for (auto& i : cur) {
            int mx = max({i[a], i[b], i[c]});
            if (i[a] == mx)
                next[0].push_back(i);
            else if (i[b] == mx)
                next[1].push_back(i);
            else
                next[2].push_back(i);
        }
    } else if (t == 2) {
        for (auto& i : cur) {
            array cur{i[a], i[b], i[c]};
            sort(cur.begin(), cur.end());
            if (i[a] == cur[1])
                next[0].push_back(i);
            else if (i[b] == cur[1])
                next[1].push_back(i);
            else
                next[2].push_back(i);
        }
    } else {
        for (auto& i : cur) {
            array cur{i[a], i[b], i[c]};
            sort(cur.begin(), cur.end());
            int ans = -1;
            for (int j : cur) {
                if (j > i[d]) {
                    ans = j;
                    break;
                }
            }

            if (ans == -1) ans = cur[0];

            if (i[a] == ans)
                next[0].push_back(i);
            else if (i[b] == ans)
                next[1].push_back(i);
            else
                next[2].push_back(i);
        }
    }
    return next;
}

int cost(array<vector<st>, 3> pos) {
    return max({pos[0].size(), pos[1].size(), pos[2].size()});
}

int rec(vector<st> pos, int qleft) {
    if (pw3[qleft] < sz(pos)) return false;
    if (pos.size() <= 1) return true;
    array<vector<st>, 3> best;
    int bestx = inf;
    op bestq;

    auto tryAccept =[&](op op) {
        auto next = getNext(pos, op);
        int mx = max({next[0].size(), next[1].size(), next[2].size()});
        if (mx < bestx) {
            bestx = mx;
            best = next;
            bestq = op;
        }
    };

    for (int a = 0; a < n; a++) {
        for (int b = a+1; b < n; b++) {
            for (int c = b+1; c < n; c++) {
                tryAccept({0, a, b, c, -1});
                tryAccept({1, a, b, c, -1});
                tryAccept({2, a, b, c, -1});
                for (int d = 0; d < n; d++) {
                    if (d == a || d == b || d == c) continue;
                    tryAccept({3, a, b, c, d});
                }
            }
        }
    }

    assert(bestx != inf);

    if (!rec(best[0], qleft-1)) return false;
    if (!rec(best[1], qleft-1)) return false;
    if (!rec(best[2], qleft-1)) return false;
    usedop[pos] = bestq;
    return true;
}

void init(int T) {
    pw3[0] = 1;
    for (int i = 1; i < 30; i++)
        pw3[i] = pw3[i-1] * 3;

    vector<st> pos;
    st cur;
    iota(cur.begin(), cur.end(), 0);
    do {
        pos.push_back(cur);
    } while (next_permutation(cur.begin(), cur.end()));

    cerr << rec(pos, 7) << endl;
    // cout << rec(pos, 8) << endl;
}

void orderCoins() {
    vector<st> pos;{
    st cur;
    iota(cur.begin(), cur.end(), 0);
    do {
        pos.push_back(cur);
    } while (next_permutation(cur.begin(), cur.end()));}

    while (pos.size() > 1) {
        // cout << "pos.size()=" << pos.size() << endl;
        assert(usedop.count(pos));
        auto op = usedop[pos];
        auto[t, a, b, c, d] = op;
        auto next = getNext(pos, op);
        a++;b++;c++; d++;
        if (t == 0) {
            int ans = getLightest(a, b, c);
            if (ans == a) pos = next[0];
            if (ans == b) pos = next[1];
            if (ans == c) pos = next[2];
        } else if (t == 1) {
            int ans = getHeaviest(a, b, c);
            if (ans == a) pos = next[0];
            if (ans == b) pos = next[1];
            if (ans == c) pos = next[2];
        } else if (t == 2) {
            int ans = getMedian(a, b, c);
            if (ans == a) pos = next[0];
            if (ans == b) pos = next[1];
            if (ans == c) pos = next[2];
        } else {
            int ans = getNextLightest(a, b, c, d);
            if (ans == a) pos = next[0];
            if (ans == b) pos = next[1];
            if (ans == c) pos = next[2];
        }
    }
    assert(pos.size() == 1);
    int w[6];
    for (int i = 0; i < 6; i++) {
        w[pos[0][i]] = i+1;
    }
    answer(w);
}

Compilation message (stderr)

scales.cpp: In function 'std::array<std::vector<std::array<int, 6> >, 3> getNext(std::vector<std::array<int, 6> >, op)':
scales.cpp:16:49: warning: declaration of 'op' shadows a global declaration [-Wshadow]
   16 | array<vector<st>, 3> getNext(vector<st> cur, op op) {
      |                                              ~~~^~
scales.cpp:12:7: note: shadowed declaration is here
   12 | using op = tuple<int,int,int,int,int>;
      |       ^~
scales.cpp:41:19: warning: declaration of 'array<...auto...> cur' shadows a parameter [-Wshadow]
   41 |             array cur{i[a], i[b], i[c]};
      |                   ^~~
scales.cpp:16:41: note: shadowed declaration is here
   16 | array<vector<st>, 3> getNext(vector<st> cur, op op) {
      |                              ~~~~~~~~~~~^~~
scales.cpp:52:19: warning: declaration of 'array<...auto...> cur' shadows a parameter [-Wshadow]
   52 |             array cur{i[a], i[b], i[c]};
      |                   ^~~
scales.cpp:16:41: note: shadowed declaration is here
   16 | array<vector<st>, 3> getNext(vector<st> cur, op op) {
      |                              ~~~~~~~~~~~^~~
scales.cpp: In function 'int cost(std::array<std::vector<std::array<int, 6> >, 3>)':
scales.cpp:76:15: warning: conversion from 'long unsigned int' to 'int' may change value [-Wconversion]
   76 |     return max({pos[0].size(), pos[1].size(), pos[2].size()});
      |            ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
scales.cpp: In lambda function:
scales.cpp:86:28: warning: declaration of 'op' shadows a global declaration [-Wshadow]
   86 |     auto tryAccept =[&](op op) {
      |                         ~~~^~
scales.cpp:12:7: note: shadowed declaration is here
   12 | using op = tuple<int,int,int,int,int>;
      |       ^~
scales.cpp:88:21: warning: conversion from 'long unsigned int' to 'int' may change value [-Wconversion]
   88 |         int mx = max({next[0].size(), next[1].size(), next[2].size()});
      |                  ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
scales.cpp: In function 'void init(int)':
scales.cpp:119:15: warning: unused parameter 'T' [-Wunused-parameter]
  119 | void init(int T) {
      |           ~~~~^
scales.cpp: In function 'void orderCoins()':
scales.cpp:146:14: warning: declaration of 'op' shadows a global declaration [-Wshadow]
  146 |         auto op = usedop[pos];
      |              ^~
scales.cpp:12:7: note: shadowed declaration is here
   12 | using op = tuple<int,int,int,int,int>;
      |       ^~

• Subtask 1: 71.72619 / 100