Submission #639938

#	Time	Username	Problem	Language	Result	Execution time	Memory
639938		piOOE	Scales (IOI15_scales)	C++17	100 / 100	517 ms	7888 KiB

scales

#include <bits/stdc++.h>
#include "scales.h"

using namespace std;

constexpr 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[i] > p[k]) {
        swap(i, k);
    }
    if (p[j] > p[k]) {
        swap(j, k);
    }
}

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 lightest(vector<int> &p, int i, int j, int k) {
    sort(p, i, j, k);
    return i;
}

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

bool solve(vector<int> mask, int remain) {
    if (mask.size() <= 1) {
        return true;
    } else if (mask.size() > P[remain]) {
        return false;
    } else if (compare.count(mask)) {
        return true;
    }
    vector<int> one, two, three;
    for (int i = 0; i < N - 2; ++i) {
        for (int j = i + 1; j < N - 1; ++j) {
            for (int k = j + 1; k < N; ++k) {
                one.clear(), two.clear(), three.clear();
                for (int p: mask) {
                    int x = lightest(inv[p], i, j, k);
                    (x == i ? one : (x == j ? two : three)).push_back(p);
                }
                if (solve(one, remain - 1) && solve(two, remain - 1) && solve(three, remain - 1)) {
                    compare[mask] = {i, j, k, -3};
                    return true;
                }
                
                one.clear(), two.clear(), three.clear();
                for (int p: mask) {
                    int x = heaviest(inv[p], i, j, k);
                    (x == i ? one : (x == j ? two : three)).push_back(p);
                }
                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 (int p: mask) {
                    int x = median(inv[p], i, j, k);
                    (x == i ? one : (x == j ? two : three)).push_back(p);
                }
                if (solve(one, remain - 1) && solve(two, remain - 1) && solve(three, remain - 1)) {
                    compare[mask] = {i, j, k, -2};
                    return true;
                }


                for (int l = 0; l < N; ++l) {
                    if (i != l && j != l && k != l) {
                        one.clear(), two.clear(), three.clear();
                        for (int p: mask) {
                            int x = next(inv[p], i, j, k, l);
                            (x == i ? one : (x == j ? two : three)).push_back(p);
                        }
                        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> p(N);
    iota(p.begin(), p.end(), 0);
    for (int i = 0; i < M; ++i) {
        inv[i].resize(N);
        for (int k = 0; k < N; ++k) {
            inv[i][p[k]] = k;
        }
        perm[i] = p;
        next_permutation(p.begin(), p.end());
    }
    vector<int> mask(M);
    iota(mask.begin(), mask.end(), 0);
    solve(mask, N);
}

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;
        int y;
        if (l == -1) {
            y = getHeaviest(i + 1, j + 1, k + 1) - 1;
            for (int p: mask) {
                if (y == heaviest(inv[p], i, j, k)) {
                    new_mask.push_back(p);
                }
            }
        } else if (l == -2) {
            y = getMedian(i + 1, j + 1, k + 1) - 1;
            for (int p: mask) {
                if (y == median(inv[p], i, j, k)) {
                    new_mask.push_back(p);
                }
            }
        } else if (l == -3) {
            y = getLightest(i + 1, j + 1, k + 1) - 1;
            for (int p: mask) {
                if (y == lightest(inv[p], i, j, k)) {
                    new_mask.push_back(p);
                }
            }
        } else {
            y = getNextLightest(i + 1, j + 1, k + 1, l + 1) - 1;
            for (int p: mask) {
                if (y == next(inv[p], i, j, k, l)) {
                    new_mask.push_back(p);
                }
            }
        }
        swap(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 'bool solve(std::vector<int>, int)':
scales.cpp:53:28: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'const int' [-Wsign-compare]
   53 |     } else if (mask.size() > P[remain]) {
      |                ~~~~~~~~~~~~^~~~~~~~~~~
scales.cpp: In function 'void init(int)':
scales.cpp:114:15: warning: unused parameter 'T' [-Wunused-parameter]
  114 | void init(int T) {
      |           ~~~~^

• Subtask 1: 100 / 100