Submission #429098

#	Time	Username	Problem	Language	Result	Execution time	Memory
429098		timmyfeng	Scales (IOI15_scales)	C++17	Compilation error	0 ms	0 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);
}

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) {
      |           ~~~~^
/usr/bin/ld: /tmp/ccGbw165.o: in function `main':
grader.c:(.text.startup+0xfb): undefined reference to `orderCoins'
collect2: error: ld returned 1 exit status