Submission #429106

#	Time	Username	Problem	Language	Result	Execution time	Memory
429106		timmyfeng	Scales (IOI15_scales)	C++17	100 / 100	660 ms	7852 KiB

scales

#include <bits/stdc++.h>
using namespace std;

#include "scales.h"

const int N = 6, M = 720, P[] = {1, 3, 9, 27, 81, 243, 729};

map<vector<int>, array<int, 4>> compare;
vector<int> perm[M], inv[M];
int ans[N];

void sort(vector<int> &p, int &i, int &j, int &k) {
    if (p[i] > p[j]) {
        swap(i, j);
    }
    if (p[j] > p[k]) {
        swap(j, k);
    }
    if (p[i] > p[j]) {
        swap(i, j);
    }
}

int lightest(vector<int> &p, int i, int j, int k) {
    sort(p, i, j, k);
    return i;
}

int heaviest(vector<int> &p, int i, int j, int k) {
    sort(p, i, j, k);
    return k;
}

int median(vector<int> &p, int i, int j, int k) {
    sort(p, i, j, k);
    return j;
}

int next(vector<int> &p, int i, int j, int k, int l) {
    sort(p, i, j, k);
    if (p[l] < p[i]) {
        return i;
    } else if (p[l] < p[j]) {
        return j;
    } else if (p[l] < p[k]) {
        return k;
    } else {
        return i;
    }
}

bool solve(vector<int> mask, int remain) {
    if (mask.size() <= 1) {
        return true;
    } else if ((int) mask.size() > P[remain]) {
        return false;
    } else if (compare.count(mask) > 0) {
        return true;
    }

    vector<int> one, two, three;
    for (int i = 0; i < N; ++i) {
        for (int j = i + 1; j < N; ++j) {
            for (int k = j + 1; k < N; ++k) {
                one.clear(), two.clear(), three.clear();
                for (auto u : mask) {
                    int x = lightest(inv[u], i, j, k);
                    (x == i ? one : (x == j ? two : three)).push_back(u);
                }
                if (solve(one, remain - 1) &&
                        solve(two, remain - 1) &&
                        solve(three, remain - 1)) {
                    compare[mask] = {i, j, k, -1};
                    return true;
                }

                one.clear(), two.clear(), three.clear();
                for (auto u : mask) {
                    int x = heaviest(inv[u], i, j, k);
                    (x == i ? one : (x == j ? two : three)).push_back(u);
                }
                if (solve(one, remain - 1) &&
                        solve(two, remain - 1) &&
                        solve(three, remain - 1)) {
                    compare[mask] = {i, j, k, -2};
                    return true;
                }


                one.clear(), two.clear(), three.clear();
                for (auto u : mask) {
                    int x = median(inv[u], i, j, k);
                    (x == i ? one : (x == j ? two : three)).push_back(u);
                }
                if (solve(one, remain - 1) &&
                        solve(two, remain - 1) &&
                        solve(three, remain - 1)) {
                    compare[mask] = {i, j, k, -3};
                    return true;
                }

                for (int l = 0; l < N; ++l) {
                    if (l != i && l != j && l != k) {
                        one.clear(), two.clear(), three.clear();
                        for (auto u : mask) {
                            int x = next(inv[u], i, j, k, l);
                            (x == i ? one : (x == j ? two : three)).push_back(u);
                        }
                        if (solve(one, remain - 1) &&
                                solve(two, remain - 1) &&
                                solve(three, remain - 1)) {
                            compare[mask] = {i, j, k, l};
                            return true;
                        }
                    }
                }
            }
        }
    }
    return false;
}

void init(int t) {
    vector<int> temp(N);
    iota(temp.begin(), temp.end(), 0);

    for (int i = 0; i < M; ++i) {
        perm[i] = temp;
        inv[i].resize(6);
        for (int j = 0; j < N; ++j) {
            inv[i][perm[i][j]] = j;
        }
        next_permutation(temp.begin(), temp.end());
    }

    vector<int> mask(M);
    iota(mask.begin(), mask.end(), 0);
    solve(mask, 6);
}

void orderCoins() {
    vector<int> mask(M);
    iota(mask.begin(), mask.end(), 0);

    while (mask.size() > 1) {
        auto [i, j, k, l] = compare[mask];
        vector<int> new_mask;

        if (l == -1) {
            int x = getLightest(i + 1, j + 1, k + 1) - 1;
            for (auto u : mask) {
                if (lightest(inv[u], i, j, k) == x) {
                    new_mask.push_back(u);
                }
            }
        } else if (l == -2) {
            int x = getHeaviest(i + 1, j + 1, k + 1) - 1;
            for (auto u : mask) {
                if (heaviest(inv[u], i, j, k) == x) {
                    new_mask.push_back(u);
                }
            }
        } else if (l == -3) {
            int x = getMedian(i + 1, j + 1, k + 1) - 1;
            for (auto u : mask) {
                if (median(inv[u], i, j, k) == x) {
                    new_mask.push_back(u);
                }
            }
        } else {
            int x = getNextLightest(i + 1, j + 1, k + 1, l + 1) - 1;
            for (auto u : mask) {
                if (next(inv[u], i, j, k, l) == x) {
                    new_mask.push_back(u);
                }
            }
        }

        mask = new_mask;
    }

    for (int i = 0; i < N; ++i) {
        ans[i] = perm[mask[0]][i] + 1;
    }
    answer(ans);
}

Compilation message (stderr)

scales.cpp: In function 'void init(int)':
scales.cpp:123:15: warning: unused parameter 't' [-Wunused-parameter]
  123 | void init(int t) {
      |           ~~~~^

• Subtask 1: 100 / 100