제출 #713991

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
713991		vjudge1	Scales (IOI15_scales)	C++17	0 / 100	13 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});
}

int asklb(int i, int j, int k, int b){
    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});
        v.push_back({pos[id][b], b});

        sort(v.begin(), v.end());
        int pb;
        for(int i = 0; i < 4; ++i){
            if (v[i].second == b) pb = b;
        } 
        if (pb == 3) pb = -1;

        if (v[pb + 1].second == i) cti++;
        if (v[pb + 1].second == j) ctj++;
        if (v[pb + 1].second == k) ctk++;
    }

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

void upd_lb(int i, int j, int k, int b){
    int val = getNextLightest(i, j, k, b);

    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});
        v.push_back({pos[id][b], b});

        sort(v.begin(), v.end());
        int pb;
        for(int i = 0; i < 4; ++i){
            if (v[i].second == b) pb = b;
        } 
        if (pb == 3){
            pb = -1;
        }

        if (v[pb + 1].second != val) f[id] = 0;
    }
}

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);
    if (type >= 100){
        type -= 100;
        upd_lb(i, j, k, type);
        return;
    }

    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 = 0; i < K; ++i){
            p[ct][i] = per[i];
            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});

                    for(int b = 1; b <= 6; ++b){
                        if (b == i || b == j || b == k) continue;
                        mi = min(mi, {asklb(i, j, k, b), i, j, k, b + 100});
                    }
                }
            }
        }

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

컴파일 시 표준 에러 (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 'int asklb(int, int, int, int)':
scales.cpp:88:17: warning: declaration of 'int i' shadows a parameter [-Wshadow]
   88 |         for(int i = 0; i < 4; ++i){
      |                 ^
scales.cpp:75:15: note: shadowed declaration is here
   75 | int asklb(int i, int j, int k, int b){
      |           ~~~~^
scales.cpp: In function 'void upd_lb(int, int, int, int)':
scales.cpp:115:17: warning: declaration of 'int i' shadows a parameter [-Wshadow]
  115 |         for(int i = 0; i < 4; ++i){
      |                 ^
scales.cpp:101:17: note: shadowed declaration is here
  101 | void upd_lb(int i, int j, int k, int b){
      |             ~~~~^
scales.cpp: In function 'int asklb(int, int, int, int)':
scales.cpp:93:18: warning: 'pb' may be used uninitialized in this function [-Wmaybe-uninitialized]
   93 |         if (v[pb + 1].second == i) cti++;
      |               ~~~^~~
scales.cpp: In function 'void upd_lb(int, int, int, int)':
scales.cpp:122:18: warning: 'pb' may be used uninitialized in this function [-Wmaybe-uninitialized]
  122 |         if (v[pb + 1].second != val) f[id] = 0;
      |               ~~~^~~
scales.cpp: In function 'void upd(std::array<int, 5>)':
scales.cpp:147:9: warning: 'val' may be used uninitialized in this function [-Wmaybe-uninitialized]
  147 |         if (v[type].second != val) f[id] = 0;
      |         ^~

• Subtask 1: 0 / 100