Submission #584938

#	Time	Username	Problem	Language	Result	Execution time	Memory
584938		Jomnoi	Scales (IOI15_scales)	C++17	80.06 / 100	28 ms	348 KiB

scales

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

const int INF = 1e9 + 7;

int possible;
vector <int> perm[720];
vector <tuple <int, int, int, int, int>> ask;
bool cantuse[720];

int findHeaviest(int A, int B, int C) {
    return max({A, B, C});
}

int findLightest(int A, int B, int C) {
    return min({A, B, C});
}

int findMedian(int A, int B, int C) {
    int ma = max({A, B, C}), mi = min({A, B, C});
    if(A != ma and A != mi) {
        return A;
    }
    if(B != ma and B != mi) {
        return B;
    }
    if(C != ma and C != mi) {
        return C;
    }
    return -1;
}

int findNextLightest(int A, int B, int C, int D) {
    int upb = INF;
    if(A > D) {
        upb = min(upb, A);
    }
    if(B > D) {
        upb = min(upb, B);
    }
    if(C > D) {
        upb = min(upb, C);
    }
    
    if(upb == INF) {
        upb = min({A, B, C});
    }
    return upb;
}

void init(int T) {
    vector <int> arr({1, 2, 3, 4, 5, 6});
    int cnt = 0;
    do {
        perm[cnt] = arr;
        cnt++;
    } while(next_permutation(arr.begin(), arr.end()));

    for(int i = 0; i < 6; i++) {
        for(int j = i + 1; j < 6; j++) {
            for(int k = j + 1; k < 6; k++) {
                ask.emplace_back(i, j, k, 0, 1);
                ask.emplace_back(i, j, k, 0, 2);
                ask.emplace_back(i, j, k, 0, 3);
                for(int l = 0; l < 6; l++) {
                    if(l != i and l != j and l != k) {
                        ask.emplace_back(i, j, k, l, 4);
                    }
                }
            }
        }
    }

    random_shuffle(ask.begin(), ask.end());
}

void orderCoins() {
    possible = 720;
    memset(cantuse, false, sizeof(cantuse));
    while(possible > 1) {
        int optLeft = INF, remain;
        int A, B, C, D, type;
        int tmp, result;
        int ii, jj, kk;
        for(auto [a, b, c, d, t] : ask) {
            ii = 0, jj = 0, kk = 0;
            if(t == 1) {    
                for(int p = 0; p < 720; p++) {
                    if(cantuse[p] == true) {
                        continue;
                    }

                    tmp = findHeaviest(perm[p][a], perm[p][b], perm[p][c]);
                    if(tmp == perm[p][a]) {
                        ii++;
                    }
                    if(tmp == perm[p][b]) {
                        jj++;
                    }
                    if(tmp == perm[p][c]) {
                        kk++;
                    }
                }

                remain = max({ii, jj, kk}) - min({ii, jj, kk});
                if(optLeft >= remain) {
                    optLeft = remain;
                    A = a, B = b, C = c;
                    type = 1;
                }
            }
            else if(t == 2) {
                for(int p = 0; p < 720; p++) {
                    if(cantuse[p] == true) {
                        continue;
                    }

                    tmp = findLightest(perm[p][a], perm[p][b], perm[p][c]);
                    if(tmp == perm[p][a]) {
                        ii++;
                    }
                    if(tmp == perm[p][b]) {
                        jj++;
                    }
                    if(tmp == perm[p][c]) {
                        kk++;
                    }
                }

                remain = max({ii, jj, kk}) - min({ii, jj, kk});
                if(optLeft >= remain) {
                    optLeft = remain;
                    A = a, B = b, C = c;
                    type = 2;
                }
            }
            else if(t == 3) {
                for(int p = 0; p < 720; p++) {
                    if(cantuse[p] == true) {
                        continue;
                    }

                    tmp = findMedian(perm[p][a], perm[p][b], perm[p][c]);
                    if(tmp == perm[p][a]) {
                        ii++;
                    }
                    if(tmp == perm[p][b]) {
                        jj++;
                    }
                    if(tmp == perm[p][c]) {
                        kk++;
                    }
                }

                remain = max({ii, jj, kk}) - min({ii, jj, kk});
                if(optLeft >= remain) {
                    optLeft = remain;
                    A = a, B = b, C = c;
                    type = 3;
                }
            }
            else if(t == 4) {
                for(int p = 0; p < 720; p++) {
                    if(cantuse[p] == true) {
                        continue;
                    }

                    tmp = findNextLightest(perm[p][a], perm[p][b], perm[p][c], perm[p][d]);
                    if(tmp == perm[p][a]) {
                        ii++;
                    }
                    if(tmp == perm[p][b]) {
                        jj++;
                    }
                    if(tmp == perm[p][c]) {
                        kk++;
                    }
                }

                remain = max({ii, jj, kk}) - min({ii, jj, kk});
                if(optLeft >= remain) {
                    optLeft = remain;
                    A = a, B = b, C = c, D = d;
                    type = 4;
                }
            }
        }

        if(type == 1) {
            result = getHeaviest(A + 1, B + 1, C + 1) - 1;
            for(int p = 0; p < 720; p++) {
                if(cantuse[p] == true) {
                    continue;
                }

                if(findHeaviest(perm[p][A], perm[p][B], perm[p][C]) != perm[p][result]) {
                    cantuse[p] = true;
                    possible--;
                }
            }
        }
        else if(type == 2) {
            result = getLightest(A + 1, B + 1, C + 1) - 1;
            for(int p = 0; p < 720; p++) {
                if(cantuse[p] == true) {
                    continue;
                }

                if(findLightest(perm[p][A], perm[p][B], perm[p][C]) != perm[p][result]) {
                    cantuse[p] = true;
                    possible--;
                }
            }
        }
        else if(type == 3) {
            result = getMedian(A + 1, B + 1, C + 1) - 1;
            for(int p = 0; p < 720; p++) {
                if(cantuse[p] == true) {
                    continue;
                }

                if(findMedian(perm[p][A], perm[p][B], perm[p][C]) != perm[p][result]) {
                    cantuse[p] = true;
                    possible--;
                }
            }
        }
        else if(type == 4) {
            result = getNextLightest(A + 1, B + 1, C + 1, D + 1) - 1;
            for(int p = 0; p < 720; p++) {
                if(cantuse[p] == true) {
                    continue;
                }

                if(findNextLightest(perm[p][A], perm[p][B], perm[p][C], perm[p][D]) != perm[p][result]) {
                    cantuse[p] = true;
                    possible--;
                }
            }
        }
    }

    int W[6];
    for(int p = 0; p < 720; p++) {
        if(cantuse[p] == false) {
            for(int i = 0; i < 6; i++) {
                W[perm[p][i] - 1] = i + 1;
            }
        }
    }
    answer(W);
}

Compilation message (stderr)

scales.cpp: In function 'void init(int)':
scales.cpp:52:15: warning: unused parameter 'T' [-Wunused-parameter]
   52 | void init(int T) {
      |           ~~~~^
scales.cpp: In function 'void orderCoins()':
scales.cpp:216:14: warning: 'type' may be used uninitialized in this function [-Wmaybe-uninitialized]
  216 |         else if(type == 3) {
      |              ^~
scales.cpp:236:82: warning: 'D' may be used uninitialized in this function [-Wmaybe-uninitialized]
  236 |                 if(findNextLightest(perm[p][A], perm[p][B], perm[p][C], perm[p][D]) != perm[p][result]) {
      |                                                                                  ^
scales.cpp:197:66: warning: 'C' may be used uninitialized in this function [-Wmaybe-uninitialized]
  197 |                 if(findHeaviest(perm[p][A], perm[p][B], perm[p][C]) != perm[p][result]) {
      |                                                                  ^
scales.cpp:197:54: warning: 'B' may be used uninitialized in this function [-Wmaybe-uninitialized]
  197 |                 if(findHeaviest(perm[p][A], perm[p][B], perm[p][C]) != perm[p][result]) {
      |                                                      ^
scales.cpp:191:33: warning: 'A' may be used uninitialized in this function [-Wmaybe-uninitialized]
  191 |             result = getHeaviest(A + 1, B + 1, C + 1) - 1;
      |                      ~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 80.059524 / 100