Submission #286480

#	Time	Username	Problem	Language	Result	Execution time	Memory
286480		AaronNaidu	Scales (IOI15_scales)	C++14	71.43 / 100	54 ms	512 KiB

scales

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

int t;
vector<vector<int> > possiblePerms;
bool used[7];

void init(int T) {
    t = 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)
    {
        possiblePerms.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) {
    int aCount = 0;
    int bCount = 0;
    int cCount = 0;
    for (auto i : possiblePerms)
    {
        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) {
    int aCount = 0;
    int bCount = 0;
    int cCount = 0;
    for (auto i : possiblePerms)
    {
        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) {
    int aCount = 0;
    int bCount = 0;
    int cCount = 0;
    for (auto i : possiblePerms)
    {
        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) {
    return 1000000009;
}

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 ans;
                    ans = checkOther(i, j, k, l);
                    if (ans < minAnswer)
                    {
                        minAnswer = ans;
                        mina = i;
                        minb = j;
                        minc = k;
                        mind = l;
                        minType = 4;
                    }
                    ans = checkOther(i, j, l, k);
                    if (ans < minAnswer)
                    {
                        minAnswer = ans;
                        mina = i;
                        minb = j;
                        minc = l;
                        mind = k;
                        minType = 4;
                    }
                    ans = checkOther(i, k, l, j);
                    if (ans < minAnswer)
                    {
                        minAnswer = ans;
                        mina = i;
                        minb = k;
                        minc = l;
                        mind = j;
                        minType = 4;
                    }
                    ans = checkOther(j, k, l, i);
                    if (ans < minAnswer)
                    {
                        minAnswer = ans;
                        mina = j;
                        minb = k;
                        minc = l;
                        mind = i;
                        minType = 4;
                    }
                }
            }
        }  
    }
    //cout << possiblePerms.size() << " possiblities\n";
    if (minType == 1)
    {
        int x = getLightest(mina, minb, minc);
        vector<vector<int> > newPossiblePerms;
        for (auto i : possiblePerms)
        {
            if (vectorFind(i, x) > vectorFind(i, mina))
            {
                continue;
            }
            if (vectorFind(i, x) > vectorFind(i, minb))
            {
                continue;
            }
            if (vectorFind(i, x) > vectorFind(i, minc))
            {
                continue;
            }
            newPossiblePerms.push_back(i);
        }
        possiblePerms = newPossiblePerms;
        newPossiblePerms.clear();
    }
    if (minType == 3)
    {
        int x = getHeaviest(mina, minb, minc);
        vector<vector<int> > newPossiblePerms;
        for (auto i : possiblePerms)
        {
            if (vectorFind(i, x) < vectorFind(i, mina))
            {
                continue;
            }
            if (vectorFind(i, x) < vectorFind(i, minb))
            {
                continue;
            }
            if (vectorFind(i, x) < vectorFind(i, minc))
            {
                continue;
            }
            newPossiblePerms.push_back(i);
        }
        possiblePerms = newPossiblePerms;
        newPossiblePerms.clear();
    }
    if (minType == 2)
    {
        int x = getMedian(mina, minb, minc);
        vector<vector<int> > newPossiblePerms;
        for (auto i : possiblePerms)
        {
            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);
            }
        }
        possiblePerms = newPossiblePerms;
        newPossiblePerms.clear();
    }
    return;
}

void orderCoins() {
    possiblePerms.clear();
    generatePerms({});
    int x = getLightest(1, 2, 3);
    vector<vector<int> > newPossiblePerms;
   // cout << possiblePerms.size() << " possiblities\n";
    for (auto i : possiblePerms)
    {
        if (vectorFind(i, x) > vectorFind(i, 1))
        {
            continue;
        }
        if (vectorFind(i, x) > vectorFind(i, 2))
        {
            continue;
        }
        if (vectorFind(i, x) > vectorFind(i, 3))
        {
            continue;
        }
        newPossiblePerms.push_back(i);
    }
    possiblePerms = newPossiblePerms;
    newPossiblePerms.clear();
   // cout << possiblePerms.size() << " possiblities\n";
    x = getLightest(4, 5, 6);
    for (auto i : possiblePerms)
    {
        if (vectorFind(i, x) > vectorFind(i, 4))
        {
            continue;
        }
        if (vectorFind(i, x) > vectorFind(i, 5))
        {
            continue;
        }
        if (vectorFind(i, x) > vectorFind(i, 6))
        {
            continue;
        }
        newPossiblePerms.push_back(i);
    }
    possiblePerms = newPossiblePerms;
    newPossiblePerms.clear();
    while (possiblePerms.size() > 1)
    {
        optimalQuestion();
    }
    int finalAnswer[6];
    for (int i = 0; i < 6; i++)
    {
        finalAnswer[i] = possiblePerms[0][i];
    }
    answer(finalAnswer);
    return;
}

Compilation message (stderr)

scales.cpp: In function 'int vectorFind(std::vector<int>, int)':
scales.cpp:14:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   14 |     for (int i = 0; i < v.size(); i++)
      |                     ~~^~~~~~~~~~
scales.cpp: In function 'int checkOther(int, int, int, int)':
scales.cpp:117:20: warning: unused parameter 'a' [-Wunused-parameter]
  117 | int checkOther(int a, int b, int c, int d) {
      |                ~~~~^
scales.cpp:117:27: warning: unused parameter 'b' [-Wunused-parameter]
  117 | int checkOther(int a, int b, int c, int d) {
      |                       ~~~~^
scales.cpp:117:34: warning: unused parameter 'c' [-Wunused-parameter]
  117 | int checkOther(int a, int b, int c, int d) {
      |                              ~~~~^
scales.cpp:117:41: warning: unused parameter 'd' [-Wunused-parameter]
  117 | int checkOther(int a, int b, int c, int d) {
      |                                     ~~~~^
scales.cpp: In function 'void optimalQuestion()':
scales.cpp:124:27: warning: variable 'mind' set but not used [-Wunused-but-set-variable]
  124 |     int mina, minb, minc, mind;
      |                           ^~~~
scales.cpp:16:9: warning: 'minc' may be used uninitialized in this function [-Wmaybe-uninitialized]
   16 |         if (v[i] == a)
      |         ^~
scales.cpp:124:21: note: 'minc' was declared here
  124 |     int mina, minb, minc, mind;
      |                     ^~~~
scales.cpp:16:9: warning: 'minb' may be used uninitialized in this function [-Wmaybe-uninitialized]
   16 |         if (v[i] == a)
      |         ^~
scales.cpp:124:15: note: 'minb' was declared here
  124 |     int mina, minb, minc, mind;
      |               ^~~~
scales.cpp:16:9: warning: 'mina' may be used uninitialized in this function [-Wmaybe-uninitialized]
   16 |         if (v[i] == a)
      |         ^~
scales.cpp:124:9: note: 'mina' was declared here
  124 |     int mina, minb, minc, mind;
      |         ^~~~

• Subtask 1: 71.428571 / 100