제출 #286613

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
286613		AaronNaidu	저울 (IOI15_scales)	C++14	71.43 / 100	107 ms	632 KiB

scales

#include <bits/stdc++.h>
#include "scales.h"
using namespace std;
vector<vector<int> > poss;
bool used[7];
int aCount, bCount, cCount;
void init(int T) {}
int vectorFind(vector<int> v, int a) {
    for (int i = 0; i < v.size(); i++) {
        if (v[i] == a) return i;
    }
    return -1;
}
void generatePerms(vector<int> v) {
    if (v.size() == 6) {
        poss.push_back(v);
        return;
    }
    for (int i = 1; i <= 6; i++) {
        if (!used[i]) {
            used[i] = true;
            v.push_back(i);
            generatePerms(v);
            v.pop_back();
            used[i] = false;
        }
    }
}
int checkMin(int a, int b, int c) {
    aCount = bCount = cCount = 0;
    for (auto i : poss) {
        if (vectorFind(i, a) < vectorFind(i, b) and vectorFind(i, a) < vectorFind(i, c)) {
            aCount++;
        }
        else if (vectorFind(i, b) < vectorFind(i,c)) {
            bCount++;
        }
        else {
            cCount++;
        }
    }
    return max(aCount, max(bCount, cCount));
}
int checkMax(int a, int b, int c) {
    aCount = bCount = cCount = 0;
    for (auto i : poss) {
        if (vectorFind(i, a) > vectorFind(i, b) and vectorFind(i, a) > vectorFind(i, c)) {
            aCount++;
        }
        else if (vectorFind(i, b) > vectorFind(i,c)) bCount++;
        else cCount++;
    }
    return max(aCount, max(bCount, cCount));
}
int checkMed(int a, int b, int c) {
    aCount = bCount = cCount = 0;
    for (auto i : poss) {
        if (vectorFind(i, b) < vectorFind(i, a) and vectorFind(i, a) < vectorFind(i, c)) aCount++;
        else if (vectorFind(i, c) < vectorFind(i,a) and vectorFind(i, a) < vectorFind(i, b)) aCount++;
        else if (vectorFind(i, c) < vectorFind(i,b) and vectorFind(i, b) < vectorFind(i, a)) bCount++;
        else if (vectorFind(i, a) < vectorFind(i,b) and vectorFind(i, b) < vectorFind(i, c)) bCount++;
        else cCount++;
    }
    return max(aCount, max(bCount, cCount));
}
int checkOther(int a, int b, int c, int d) {
    aCount = bCount = cCount = 0;
    for (auto i : poss)
    {
        vector<pair<int, int> > tests;
        tests.push_back({vectorFind(i, a), 1});
        tests.push_back({vectorFind(i, b), 2});
        tests.push_back({vectorFind(i, c), 3});
        tests.push_back({vectorFind(i, d), 4});
        sort(tests.begin(), tests.end());
        if (tests[0].second == 4)
        {
            if (tests[1].second == 1) aCount++;
            if (tests[1].second == 2) bCount++;
            if (tests[1].second == 3) cCount++;
        }
        if (tests[1].second == 4)
        {
            if (tests[2].second == 1) aCount++;
            if (tests[2].second == 2) bCount++;
            if (tests[2].second == 3) cCount++;
        }
        if (tests[2].second == 4)
        {
            if (tests[3].second == 1) aCount++;
            if (tests[3].second == 2) bCount++;
            if (tests[3].second == 3) cCount++;
        }
        if (tests[3].second == 4)
        {
            if (tests[0].second == 1) aCount++;
            if (tests[0].second == 2) bCount++;
            if (tests[0].second == 3) cCount++;
        }
    }
    return max(max(aCount, bCount), cCount);
}
void optimalQuestion() {
    int minAnswer = 1000000000;
    int minType = -1;
    int mina, minb, minc, mind;
    for (int i = 1; i <= 6; i++) {
        for (int j = i+1; j <= 6; j++) {
            for (int k = j+1; k <= 6; k++) {
                int small = checkMin(i, j, k);
                int large = checkMax(i, j, k);
                int med = checkMed(i, j, k);
                if (small < minAnswer) {
                    minAnswer = small;
                    mina = i;
                    minb = j;
                    minc = k;
                    minType = 1;
                }
                if (large < minAnswer) {
                    minAnswer = large;
                    mina = i;
                    minb = j;
                    minc = k;
                    minType = 3;
                }
                if (med < minAnswer) {
                    minAnswer = med;
                    mina = i;
                    minb = j;
                    minc = k;
                    minType = 2;
                }
                for (int l = k+1; l <= 6; l++) {
                    int anss;
                    anss = checkOther(i, j, k, l);
                    if (anss < minAnswer) {
                        minAnswer = anss;
                        mina = i;
                        minb = j;
                        minc = k;
                        mind = l;
                        minType = 4;
                    }
                    anss = checkOther(i, j, l, k);
                    if (anss < minAnswer) {
                        minAnswer = anss;
                        mina = i;
                        minb = j;
                        minc = l;
                        mind = k;
                        minType = 4;
                    }
                    anss = checkOther(i, k, l, j);
                    if (anss < minAnswer) {
                        minAnswer = anss;
                        mina = i;
                        minb = k;
                        minc = l;
                        mind = j;
                        minType = 4;
                    }
                    anss = checkOther(j, k, l, i);
                    if (anss < minAnswer) {
                        minAnswer = anss;
                        mina = j;
                        minb = k;
                        minc = l;
                        mind = i;
                        minType = 4;
                    }
                }
            }
        }  
    }
    if (minType == 1) {
        int x = getLightest(mina, minb, minc);
        vector<vector<int> > newPossiblePerms;
        for (auto i : poss) {
            if (vectorFind(i, x) > vectorFind(i, mina) or vectorFind(i, x) > vectorFind(i, minb) or vectorFind(i, x) > vectorFind(i, minc)) {
                continue;
            }
            newPossiblePerms.push_back(i);
        }
        poss = newPossiblePerms;
        newPossiblePerms.clear();
    }
    if (minType == 3) {
        int x = getHeaviest(mina, minb, minc);
        vector<vector<int> > newPossiblePerms;
        for (auto i : poss) {
            if (vectorFind(i, x) < vectorFind(i, mina) or vectorFind(i, x) < vectorFind(i, minb) or vectorFind(i, x) < vectorFind(i, minc)) {
                continue;
            }
            newPossiblePerms.push_back(i);
        }
        poss = newPossiblePerms;
        newPossiblePerms.clear();
    }
    if (minType == 2) {
        int x = getMedian(mina, minb, minc);
        vector<vector<int> > newPossiblePerms;
        for (auto i : poss) {
            if (vectorFind(i, minb) > vectorFind(i, x) and vectorFind(i, x) > vectorFind(i, mina)) {
                newPossiblePerms.push_back(i);
            }
            if (vectorFind(i, mina) >  vectorFind(i, x) and vectorFind(i, x) > vectorFind(i, minb)) {
                newPossiblePerms.push_back(i);
            }
            if (vectorFind(i, minb) > vectorFind(i, x) and vectorFind(i, x) > vectorFind(i, minc)) {
                newPossiblePerms.push_back(i);
            }
            if (vectorFind(i, minc) > vectorFind(i, x) and vectorFind(i, x) > vectorFind(i, minb)) {
                newPossiblePerms.push_back(i);
            }
            if (vectorFind(i, mina) > vectorFind(i, x) and vectorFind(i, x) > vectorFind(i, minc)) {
                newPossiblePerms.push_back(i);
            }
            if (vectorFind(i, minc) > vectorFind(i, x) and vectorFind(i, x) > vectorFind(i, mina)) {
                newPossiblePerms.push_back(i);
            }
        }
        poss = newPossiblePerms;
        newPossiblePerms.clear();
    }
    if (minType == 4) {
        int y = getNextLightest(mina, minb, minc, mind);
        vector<vector<int> > newPossiblePerms;
        for (auto i : poss) {
            vector<pair<int, int> > tests;
            tests.push_back({vectorFind(i, mina), mina});
            tests.push_back({vectorFind(i, minb), minb});
            tests.push_back({vectorFind(i, minc), minc});
            tests.push_back({vectorFind(i, mind), mind});
            sort(tests.begin(), tests.end());
            if ((tests[0].second == mind and tests[1].second == y) or (tests[1].second == mind and tests[2].second == y) or (tests[2].second == mind and tests[3].second == y) or (tests[3].second == mind and tests[0].second == y)) {
                newPossiblePerms.push_back(i);
            }
        }
        poss = newPossiblePerms;
        newPossiblePerms.clear();
    }
    return;
}
void orderCoins() {
    poss.clear();
    generatePerms({});
    int x = getLightest(1, 2, 3);
    vector<vector<int> > newPossiblePerms;
    for (auto i : poss) {
        if (vectorFind(i, x) > vectorFind(i, 1) or vectorFind(i, x) > vectorFind(i, 2) or vectorFind(i, x) > vectorFind(i, 3)) {
            continue;
        }
        newPossiblePerms.push_back(i);
    }
    poss = newPossiblePerms;
    newPossiblePerms.clear();
    x = getLightest(4, 5, 6);
    for (auto i : poss) {
        if (vectorFind(i, x) > vectorFind(i, 4) or vectorFind(i, x) > vectorFind(i, 5) or vectorFind(i, x) > vectorFind(i, 6)) {
            continue;
        }
        newPossiblePerms.push_back(i);
    }
    poss = newPossiblePerms;
    newPossiblePerms.clear();
    while (poss.size() > 1) {
        optimalQuestion();
    }
    int finalAnswer[6];
    for (int i = 0; i < 6; i++) {
        finalAnswer[i] = poss[0][i];
    }
    answer(finalAnswer);
    return;
}

컴파일 시 표준 에러 (stderr) 메시지

scales.cpp: In function 'void init(int)':
scales.cpp:7:15: warning: unused parameter 'T' [-Wunused-parameter]
    7 | void init(int T) {}
      |           ~~~~^
scales.cpp: In function 'int vectorFind(std::vector<int>, int)':
scales.cpp:9:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    9 |     for (int i = 0; i < v.size(); i++) {
      |                     ~~^~~~~~~~~~
scales.cpp: In function 'void optimalQuestion()':
scales.cpp:236:176: warning: 'mind' may be used uninitialized in this function [-Wmaybe-uninitialized]
  236 |             if ((tests[0].second == mind and tests[1].second == y) or (tests[1].second == mind and tests[2].second == y) or (tests[2].second == mind and tests[3].second == y) or (tests[3].second == mind and tests[0].second == y)) {
      |                 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
scales.cpp:10:9: warning: 'minc' may be used uninitialized in this function [-Wmaybe-uninitialized]
   10 |         if (v[i] == a) return i;
      |         ^~
scales.cpp:106:21: note: 'minc' was declared here
  106 |     int mina, minb, minc, mind;
      |                     ^~~~
scales.cpp:10:9: warning: 'minb' may be used uninitialized in this function [-Wmaybe-uninitialized]
   10 |         if (v[i] == a) return i;
      |         ^~
scales.cpp:106:15: note: 'minb' was declared here
  106 |     int mina, minb, minc, mind;
      |               ^~~~
scales.cpp:10:9: warning: 'mina' may be used uninitialized in this function [-Wmaybe-uninitialized]
   10 |         if (v[i] == a) return i;
      |         ^~
scales.cpp:106:9: note: 'mina' was declared here
  106 |     int mina, minb, minc, mind;
      |         ^~~~

• Subtask 1: 71.428571 / 100