Submission #713980

#	Time	Username	Problem	Language	Result	Execution time	Memory
713980		vjudge1	Scales (IOI15_scales)	C++17	0 / 100	9 ms	340 KiB

scales

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

using namespace std;

const int INF = 1e9;

void init(int T) {
    /* ... */
}

const int N = 720;
const int K = 6;
bitset <N> f;
int p[N][K];
int pos[N][K + 1];

int askmin(int i, int j, int k){
    int cti = 0, ctj = 0, ctk = 0;
    for(int id = 0; id < N; ++id){
        if (!f[id]) continue;

        vector <pair<int, int>> v;
        v.push_back({pos[id][i], i});
        v.push_back({pos[id][j], j});
        v.push_back({pos[id][k], k});

        sort(v.begin(), v.end());
        if (v[0].second == i) cti++;
        if (v[0].second == j) ctj++;
        if (v[0].second == k) ctk++; 
    }

    return max({cti, ctj, ctk});
}

int askmed(int i, int j, int k){
    int cti = 0, ctj = 0, ctk = 0;
    for(int id = 0; id < N; ++id){
        if (!f[id]) continue;

        vector <pair<int, int>> v;
        v.push_back({pos[id][i], i});
        v.push_back({pos[id][j], j});
        v.push_back({pos[id][k], k});

        sort(v.begin(), v.end());
        if (v[1].second == i) cti++;
        if (v[1].second == j) ctj++;
        if (v[1].second == k) ctk++; 
    }

    return max({cti, ctj, ctk});
}

int askmax(int i, int j, int k){
    int cti = 0, ctj = 0, ctk = 0;
    for(int id = 0; id < N; ++id){
        if (!f[id]) continue;

        vector <pair<int, int>> v;
        v.push_back({pos[id][i], i});
        v.push_back({pos[id][j], j});
        v.push_back({pos[id][k], k});

        sort(v.begin(), v.end());
        if (v[2].second == i) cti++;
        if (v[2].second == j) ctj++;
        if (v[2].second == k) ctk++; 
    }

    return max({cti, ctj, ctk});
}

void upd(array<int, 5> mi){
    int i = mi[1], j = mi[2], k = mi[3], type = mi[4];
    int val;
    if (type == 0) val = getLightest(i, j, k);
    if (type == 1) val = getMedian(i, j, k);
    if (type == 2) val = getHeaviest(i, j, k);

    for(int id = 0; id < N; ++id){
        if (!f[id]) continue;

        vector <pair<int, int>> v;
        v.push_back({pos[id][i], i});
        v.push_back({pos[id][j], j});
        v.push_back({pos[id][k], k});

        sort(v.begin(), v.end());
        if (v[type].second != val) f[id] = 0;
    }
}

void orderCoins() {
    vector <int> per;
    for(int i = 1; i <= K; ++i) per.push_back(i);

    int ct = 0;
    do{
        f[ct] = true;
        for(int i = 1; i <= K; ++i){
            p[ct][i] = per[i - 1];
            pos[ct][per[i]] = i;
        }
        ++ct;
    }while(next_permutation(per.begin(), per.end()));

    while ((int)f.count() > 1){
        array<int, 5> mi = {INF, INF, INF, INF, INF};
        for(int i = 1; i <= 6; ++i){
            for(int j = i + 1; j <= 6; ++j){
                for(int k = j + 1; k <= 6; ++k){
                    mi = min(mi, {askmin(i, j, k), i, j, k, 0});
                    mi = min(mi, {askmed(i, j, k), i, j, k, 1});
                    mi = min(mi, {askmax(i, j, k), i, j, k, 2});
                }
            }
        }

        upd(mi);
    }
    int W[6] = {0, 0, 0, 0, 0, 0};
    for(int id = 0; id < N; ++id){
        if (!f[id]) continue;
        for(int i = 0; i < 6; ++i) W[i] = p[id][i];
    }

    answer(W);
}

Compilation message (stderr)

scales.cpp: In function 'void init(int)':
scales.cpp:8:15: warning: unused parameter 'T' [-Wunused-parameter]
    8 | void init(int T) {
      |           ~~~~^
scales.cpp: In function 'void orderCoins()':
scales.cpp:103:22: warning: iteration 5 invokes undefined behavior [-Waggressive-loop-optimizations]
  103 |             p[ct][i] = per[i - 1];
scales.cpp:102:26: note: within this loop
  102 |         for(int i = 1; i <= K; ++i){
      |                        ~~^~~~
scales.cpp: In function 'void upd(std::array<int, 5>)':
scales.cpp:91:9: warning: 'val' may be used uninitialized in this function [-Wmaybe-uninitialized]
   91 |         if (v[type].second != val) f[id] = 0;
      |         ^~

• Subtask 1: 0 / 100