Submission #584916

#	Time	Username	Problem	Language	Result	Execution time	Memory
584916		Jomnoi	Scales (IOI15_scales)	C++17	71.43 / 100	23 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];
bool cantuse[720];

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()));
}

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 orderCoins() {
    possible = 720;
    memset(cantuse, false, sizeof(cantuse));
    while(possible > 1) {
        int optLeft = INF;
        int A, B, C, D, type;
        int tmp, remain, result;
        int hi, hj, hk, li, lj, lk, mi, mj, mk, nli, nlj, nlk;
        for(int i = 0; i < 6; i++) {
            for(int j = i + 1; j < 6; j++) {
                for(int k = j + 1; k < 6; k++) {
                    hi = 0, hj = 0, hk = 0;
                    li = 0, lj = 0, lk = 0;
                    mi = 0, mj = 0, mk = 0;
                    for(int p = 0; p < 720; p++) {
                        if(cantuse[p] == true) {
                            continue;
                        }

                        tmp = findHeaviest(perm[p][i], perm[p][j], perm[p][k]);
                        if(tmp == perm[p][i]) {
                            hi++;
                        }
                        if(tmp == perm[p][j]) {
                            hj++;
                        }
                        if(tmp == perm[p][k]) {
                            hk++;
                        }

                        tmp = findLightest(perm[p][i], perm[p][j], perm[p][k]);
                        if(tmp == perm[p][i]) {
                            li++;
                        }
                        if(tmp == perm[p][j]) {
                            lj++;
                        }
                        if(tmp == perm[p][k]) {
                            lk++;
                        }

                        tmp = findMedian(perm[p][i], perm[p][j], perm[p][k]);
                        if(tmp == perm[p][i]) {
                            mi++;
                        }
                        if(tmp == perm[p][j]) {
                            mj++;
                        }
                        if(tmp == perm[p][k]) {
                            mk++;
                        }
                    }

                    remain = max({hi, hj, hk});
                    if(remain < optLeft) {
                        optLeft = remain;
                        A = i, B = j, C = k;
                        type = 1;
                    }

                    remain = max({li, lj, lk});
                    if(remain < optLeft) {
                        optLeft = remain;
                        A = i, B = j, C = k;
                        type = 2;
                    }

                    remain = max({mi, mj, mk});
                    if(remain < optLeft) {
                        optLeft = remain;
                        A = i, B = j, C = k;
                        type = 3;
                    }

                    for(int l = 0; l < 6; l++) {
                        if(l == i or l == j or l == k) {
                            continue;
                        }   

                        nli = 0, nlj = 0, nlk = 0;
                        for(int p = 0; p < 720; p++) {
                            if(cantuse[p] == true) {
                                continue;
                            }

                            tmp = findNextLightest(perm[p][i], perm[p][j], perm[p][k], perm[p][l]);
                            if(tmp == perm[p][i]) {
                                nli++;
                            }
                            if(tmp == perm[p][j]) {
                                nlj++;
                            }
                            if(tmp == perm[p][k]) {
                                nlk++;
                            }
                        }

                        remain = max({nli, nlj, nlk});
                        if(remain < optLeft) {
                            optLeft = remain;
                            A = i, B = j, C = k, D = l;
                            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:11:15: warning: unused parameter 'T' [-Wunused-parameter]
   11 | void init(int T) {
      |           ~~~~^
scales.cpp: In function 'void orderCoins()':
scales.cpp:207:14: warning: 'type' may be used uninitialized in this function [-Wmaybe-uninitialized]
  207 |         else if(type == 4) {
      |              ^~
scales.cpp:214:82: warning: 'D' may be used uninitialized in this function [-Wmaybe-uninitialized]
  214 |                 if(findNextLightest(perm[p][A], perm[p][B], perm[p][C], perm[p][D]) != perm[p][result]) {
      |                                                                                  ^
scales.cpp:175:66: warning: 'C' may be used uninitialized in this function [-Wmaybe-uninitialized]
  175 |                 if(findHeaviest(perm[p][A], perm[p][B], perm[p][C]) != perm[p][result]) {
      |                                                                  ^
scales.cpp:175:54: warning: 'B' may be used uninitialized in this function [-Wmaybe-uninitialized]
  175 |                 if(findHeaviest(perm[p][A], perm[p][B], perm[p][C]) != perm[p][result]) {
      |                                                      ^
scales.cpp:175:42: warning: 'A' may be used uninitialized in this function [-Wmaybe-uninitialized]
  175 |                 if(findHeaviest(perm[p][A], perm[p][B], perm[p][C]) != perm[p][result]) {
      |                                          ^

• Subtask 1: 71.428571 / 100