Submission #276377

#	Time	Username	Problem	Language	Result	Execution time	Memory
276377		stoyan_malinin	Scales (IOI15_scales)	C++14	71.43 / 100	5 ms	384 KiB

scales

#include "scales.h"
//#include "grader.cpp"

#include <set>
#include <vector>
#include <iostream>
#include <algorithm>

using namespace std;

struct Query
{
    int type;

    int d;
    set <int> args;

    int ans;

    Query(){}
    Query(int type, set <int> args, int ans)
    {
        this->type = type;
        this->args = args;
        this->d = -1;

        this->ans = ans;
    }
    Query(int type, set <int> args, int d, int ans)
    {
        this->type = type;
        this->args = args;
        this->d = d;

        this->ans = ans;
    }
};

struct QueryKeeper
{
    vector <Query> v;

    int get(int ind)
    {
        return v[ind].ans;
    }

    vector <int> sol, num2Pos;

    int findSol()
    {
        int cnt = 0;

        vector <int> p;
        for(int i = 1;i<=6;i++) p.push_back(i);

        num2Pos.resize(10);
        do
        {
            for(int i = 0;i<6;i++) num2Pos[ p[i] ] = i;

            bool fail = false;
            for(Query q: v)
            {
                if(q.type==1)
                {
                    int maxVal = -1;
                    for(int x: q.args) maxVal = max(maxVal, num2Pos[x]);

                    if(q.ans!=p[maxVal])
                    {
                        fail = true;
                        break;
                    }
                }
                else if(q.type==2)
                {
                    int minVal = 69;
                    for(int x: q.args) minVal = min(minVal, num2Pos[x]);

                    if(q.ans!=p[minVal])
                    {
                        fail = true;
                        break;
                    }
                }
                else if(q.type==3)
                {
                    int minVal = 69;
                    for(int x: q.args) minVal = min(minVal, num2Pos[x]);

                    int maxVal = -1;
                    for(int x: q.args) maxVal = max(maxVal, num2Pos[x]);

                    if(q.ans==p[minVal] || q.ans==p[maxVal])
                    {
                        fail = true;
                        break;
                    }
                }
            }

            if(fail==false)
            {
                sol = p;
                cnt++;
            }
        }
        while(next_permutation(p.begin(), p.end()));

        return cnt;
    }
};

QueryKeeper welko;
int ask(int type, set <int> args)
{
    int a, b, c, d;
    auto it = args.begin();

    a = *it;it++;
    b = *it;it++;
    c = *it;it++;
    if(type==4) d = *it;

    int res;
    if(type==1) res = getHeaviest(a, b, c);
    else if(type==2) res = getLightest(a, b, c);
    else if(type==3) res = getMedian(a, b, c);
    else if(type==4) res = getNextLightest(a, b, c, d);

    welko.v.push_back(Query(type, args, res));
    return res;
}

set <int> exclude(set <int> s, vector <int> v)
{
    for(int x: v) s.erase(x);
    return s;
}

set <int> include(set <int> s, vector <int> v)
{
    for(int x: v) s.insert(x);
    return s;
}

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

void solve4(set <int> s, int *W)
{
    vector <int> v;
    for(int x: s) v.push_back(x);

    int b = ask(1, {v[0], v[1], v[2]});
    W[1] = ask(2, exclude(s, {b}));

    int med = ask(3, exclude(s, {W[1]}));

    int c;
    if(v[3]!=W[1]) c = v[3];
    else c = *exclude(s, {b, W[1]}).begin();

    int a = *exclude(s, {b, c, W[1]}).begin();

    if(med==b) W[2] = a, W[3] = b, W[4] = c;
    else if(med==a) W[2] = c, W[3] = a, W[4] = b;
    else if(med==c) W[2] = a, W[3] = c, W[4] = b;

    //cout << a << " " << b << " " << c << '\n';
}

void orderCoins() {
    /* ... */

    welko.v.clear();
    int W[] = {-1, -1, -1, -1, -1, -1};

    ask(1, {1, 2, 3});
    ask(2, {4, 5, 6});
    ask(1, include(exclude({4, 5, 6}, {welko.get(1)}), {welko.get(0)}));
    ask(2, include(exclude({1, 2, 3}, {welko.get(0)}), {welko.get(1)}));

    W[5] = welko.get(2);
    W[0] = welko.get(3);

    set <int> rem = exclude({1, 2, 3, 4, 5, 6}, {welko.get(2), welko.get(3)});
    solve4(rem, W);

    welko.findSol();
    for(int i = 0;i<6;i++) W[i] = welko.sol[i];

    answer(W);
}

Compilation message (stderr)

scales.cpp: In constructor 'Query::Query(int, std::set<int>, int)':
scales.cpp:22:5: warning: declaration of 'ans' shadows a member of 'Query' [-Wshadow]
   22 |     {
      |     ^
scales.cpp:18:9: note: shadowed declaration is here
   18 |     int ans;
      |         ^~~
scales.cpp:22:5: warning: declaration of 'args' shadows a member of 'Query' [-Wshadow]
   22 |     {
      |     ^
scales.cpp:16:15: note: shadowed declaration is here
   16 |     set <int> args;
      |               ^~~~
scales.cpp:22:5: warning: declaration of 'type' shadows a member of 'Query' [-Wshadow]
   22 |     {
      |     ^
scales.cpp:13:9: note: shadowed declaration is here
   13 |     int type;
      |         ^~~~
scales.cpp: In constructor 'Query::Query(int, std::set<int>, int)':
scales.cpp:28:5: warning: declaration of 'ans' shadows a member of 'Query' [-Wshadow]
   28 |     }
      |     ^
scales.cpp:18:9: note: shadowed declaration is here
   18 |     int ans;
      |         ^~~
scales.cpp:28:5: warning: declaration of 'args' shadows a member of 'Query' [-Wshadow]
   28 |     }
      |     ^
scales.cpp:16:15: note: shadowed declaration is here
   16 |     set <int> args;
      |               ^~~~
scales.cpp:28:5: warning: declaration of 'type' shadows a member of 'Query' [-Wshadow]
   28 |     }
      |     ^
scales.cpp:13:9: note: shadowed declaration is here
   13 |     int type;
      |         ^~~~
scales.cpp: In constructor 'Query::Query(int, std::set<int>, int)':
scales.cpp:28:5: warning: declaration of 'ans' shadows a member of 'Query' [-Wshadow]
   28 |     }
      |     ^
scales.cpp:18:9: note: shadowed declaration is here
   18 |     int ans;
      |         ^~~
scales.cpp:28:5: warning: declaration of 'args' shadows a member of 'Query' [-Wshadow]
   28 |     }
      |     ^
scales.cpp:16:15: note: shadowed declaration is here
   16 |     set <int> args;
      |               ^~~~
scales.cpp:28:5: warning: declaration of 'type' shadows a member of 'Query' [-Wshadow]
   28 |     }
      |     ^
scales.cpp:13:9: note: shadowed declaration is here
   13 |     int type;
      |         ^~~~
scales.cpp: In constructor 'Query::Query(int, std::set<int>, int, int)':
scales.cpp:30:5: warning: declaration of 'ans' shadows a member of 'Query' [-Wshadow]
   30 |     {
      |     ^
scales.cpp:18:9: note: shadowed declaration is here
   18 |     int ans;
      |         ^~~
scales.cpp:30:5: warning: declaration of 'd' shadows a member of 'Query' [-Wshadow]
   30 |     {
      |     ^
scales.cpp:15:9: note: shadowed declaration is here
   15 |     int d;
      |         ^
scales.cpp:30:5: warning: declaration of 'args' shadows a member of 'Query' [-Wshadow]
   30 |     {
      |     ^
scales.cpp:16:15: note: shadowed declaration is here
   16 |     set <int> args;
      |               ^~~~
scales.cpp:30:5: warning: declaration of 'type' shadows a member of 'Query' [-Wshadow]
   30 |     {
      |     ^
scales.cpp:13:9: note: shadowed declaration is here
   13 |     int type;
      |         ^~~~
scales.cpp: In constructor 'Query::Query(int, std::set<int>, int, int)':
scales.cpp:36:5: warning: declaration of 'ans' shadows a member of 'Query' [-Wshadow]
   36 |     }
      |     ^
scales.cpp:18:9: note: shadowed declaration is here
   18 |     int ans;
      |         ^~~
scales.cpp:36:5: warning: declaration of 'd' shadows a member of 'Query' [-Wshadow]
   36 |     }
      |     ^
scales.cpp:15:9: note: shadowed declaration is here
   15 |     int d;
      |         ^
scales.cpp:36:5: warning: declaration of 'args' shadows a member of 'Query' [-Wshadow]
   36 |     }
      |     ^
scales.cpp:16:15: note: shadowed declaration is here
   16 |     set <int> args;
      |               ^~~~
scales.cpp:36:5: warning: declaration of 'type' shadows a member of 'Query' [-Wshadow]
   36 |     }
      |     ^
scales.cpp:13:9: note: shadowed declaration is here
   13 |     int type;
      |         ^~~~
scales.cpp: In constructor 'Query::Query(int, std::set<int>, int, int)':
scales.cpp:36:5: warning: declaration of 'ans' shadows a member of 'Query' [-Wshadow]
   36 |     }
      |     ^
scales.cpp:18:9: note: shadowed declaration is here
   18 |     int ans;
      |         ^~~
scales.cpp:36:5: warning: declaration of 'd' shadows a member of 'Query' [-Wshadow]
   36 |     }
      |     ^
scales.cpp:15:9: note: shadowed declaration is here
   15 |     int d;
      |         ^
scales.cpp:36:5: warning: declaration of 'args' shadows a member of 'Query' [-Wshadow]
   36 |     }
      |     ^
scales.cpp:16:15: note: shadowed declaration is here
   16 |     set <int> args;
      |               ^~~~
scales.cpp:36:5: warning: declaration of 'type' shadows a member of 'Query' [-Wshadow]
   36 |     }
      |     ^
scales.cpp:13:9: note: shadowed declaration is here
   13 |     int type;
      |         ^~~~
scales.cpp: In function 'void init(int)':
scales.cpp:148:15: warning: unused parameter 'T' [-Wunused-parameter]
  148 | void init(int T) {
      |           ~~~~^
scales.cpp: In function 'int ask(int, std::set<int>)':
scales.cpp:27:19: warning: 'res' may be used uninitialized in this function [-Wmaybe-uninitialized]
   27 |         this->ans = ans;
      |         ~~~~~~~~~~^~~~~
scales.cpp:126:9: note: 'res' was declared here
  126 |     int res;
      |         ^~~

• Subtask 1: 71.428571 / 100