Submission #1055258

#	Time	Username	Problem	Language	Result	Execution time	Memory
1055258		Faisal_Saqib	Scales (IOI15_scales)	C++17	100 / 100	685 ms	7192 KiB

scales

#include <bits/stdc++.h>
#include "scales.h"
// void answer(int C[]);
// int getMedian(int A, int B, int C);
// int getHeaviest(int A, int B, int C);
// int getLightest(int A, int B, int C);
// int getNextLightest(int A, int B, int C, int D);
using namespace std;
#include <bits/stdc++.h>
// #include "scales.h"
// void answer(int C[]);
// int getMedian(int A, int B, int C);
// int getHeaviest(int A, int B, int C);
// int getLightest(int A, int B, int C);
// int getNextLightest(int A, int B, int C, int D);
using namespace std;

#define question array<int,5>
#define permutation array<int,6>
#define possibility vector<permutation>

map<possibility,question> best_question;
map<possibility,int> min_queries;

int ask(permutation&p,question&q)
{
    permutation ind;
    for(int i=0;i<p.size();i++)
        ind[p[i]-1]=i;
    int A=q[1]; // A= 1
    int B=q[2];// B=2
    int C=q[3];
    int D=q[4];
    if(q[0]==1)//heaviest
    {
      if (ind[A-1] > ind[B-1] && ind[A-1] > ind[C-1])
        return A;
      if (ind[B-1] > ind[A-1] && ind[B-1] > ind[C-1])
        return B;
      return C;
    }
    else if(q[0]==2)// lightest
    {
      if (ind[A-1] < ind[B-1] && ind[A-1] < ind[C-1])
        return A;

      if (ind[B-1] < ind[A-1] && ind[B-1] < ind[C-1])
        return B;

      return C;
    }
    else if(q[0]==3) // medians
    {
      if (ind[B-1] < ind[A-1] && ind[A-1] < ind[C-1])
        return A;

      if (ind[C-1] < ind[A-1] && ind[A-1] < ind[B-1])
        return A;

      if (ind[A-1] < ind[B-1] && ind[B-1] < ind[C-1])
        return B;

      if (ind[C-1] < ind[B-1] && ind[B-1] < ind[A-1])
        return B;

      return C;
    }
    else
    {
      int allLess = 1;
      if (ind[A-1] > ind[D-1] || ind[B-1] > ind[D-1] || ind[C-1] > ind[D-1])
        allLess = 0;

      if (allLess == 1) {
        if (ind[A-1] < ind[B-1] && ind[A-1] < ind[C-1])
          return A;

        if (ind[B-1] < ind[A-1] && ind[B-1] < ind[C-1])
          return B;

        return C;
      }

      if (ind[A-1] > ind[D-1]) {
        if ((ind[A-1] < ind[B-1] || ind[B-1] < ind[D-1]) &&
            (ind[A-1] < ind[C-1] || ind[C-1] < ind[D-1]))
          return A;
      }

      if (ind[B-1] > ind[D-1]) {
        if ((ind[B-1] < ind[A-1] || ind[A-1] < ind[D-1]) &&
            (ind[B-1] < ind[C-1] || ind[C-1] < ind[D-1]))
          return B;
      }

      return C;
    }
}
possibility outcomes(question&q,possibility&cur,int&answer)
{
    possibility remaining;
    for(auto&perm:cur)
    {
        if(ask(perm,q)==answer)
        {
            remaining.push_back(perm);
        }
    }
    return remaining;
}
void find_solution(possibility& cur,int lim=730,int depth=6)
{
    if(cur.size()<=1)
    {
        min_queries[cur]=0;
        return;
    }
    if(best_question.find(cur)!=best_question.end() or min_queries.find(cur)!=min_queries.end())
        return;
    if(cur.size()>lim or depth==0)
    {
        min_queries[cur]=1000;
        return;
    }
    question q;
    question ansp;
    min_queries[cur]=1000;
    for(q[0]=1;q[0]<=4;q[0]++)
    {
        for(q[1]=1;q[1]<=6;q[1]++)
        {
            for(q[2]=q[1]+1;q[2]<=6;q[2]++)
            {
                for(q[3]=q[2]+1;q[3]<=6;q[3]++)
                {
                    for(q[4]=1;q[4]<=6;q[4]++)
                    {
                        if(q[0]!=4 and q[4]!=1)continue;
                        if(q[0]==4 and (q[4]==q[1] or q[4]==q[2] or q[4]==q[3]))continue;
                        possibility result_in_a;
                        possibility result_in_b;
                        possibility result_in_c;
                        result_in_a = outcomes(q,cur,q[1]);
                        result_in_b = outcomes(q,cur,q[2]);
                        result_in_c = outcomes(q,cur,q[3]);
                        int mx_sz=max({result_in_a.size(),result_in_b.size(),result_in_c.size()});
                        if(mx_sz>(lim/3))continue;
                        find_solution(result_in_a,lim/3,depth-1);
                        find_solution(result_in_b,lim/3,depth-1);
                        find_solution(result_in_c,lim/3,depth-1);
                        int result=1+max({min_queries[result_in_a],min_queries[result_in_b],min_queries[result_in_c]});
                        if(result<min_queries[cur])
                        {
                            min_queries[cur]=result;
                            ansp=q;
                            if(min_queries[cur]==6)
                            {
                                best_question[cur]=ansp;
                                return;
                            }
                        }
                    }
                }
            }
        }
    }
    best_question[cur]=ansp;
}
void init(int TPPA)
{
    possibility total;
    permutation a={1,2,3,4,5,6};
    do
    {
        total.push_back(a);
    }while(next_permutation(begin(a),end(a)));
    find_solution(total);
}
void orderCoins() {
    possibility total;
    permutation a={1,2,3,4,5,6};
    do
    {
        total.push_back(a);
    }while(next_permutation(begin(a),end(a)));
    while(total.size()!=1)
    {
        question q=best_question[total];
        int ans=0;
        if(q[0]==1)
        {
            ans=getHeaviest(q[1],q[2],q[3]);
        }
        else if(q[0]==2)
        {
            ans=getLightest(q[1],q[2],q[3]);
        }
        else if(q[0]==3)
        {
            ans=getMedian(q[1],q[2],q[3]);

        }
        else{
            ans=getNextLightest(q[1],q[2],q[3],q[4]);
            // q[0]==4
        }
        possibility nxt=outcomes(q,total,ans);
        total=nxt;
    }
    int anpp[6];
    for(auto&j:total)
    {
        for(int i=0;i<6;i++)
        {
            anpp[i]=j[i];
        }
    }
    answer(anpp);
}

Compilation message (stderr)

scales.cpp: In function 'int ask(std::array<int, 6>&, std::array<int, 5>&)':
scales.cpp:28:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::array<int, 6>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |     for(int i=0;i<p.size();i++)
      |                 ~^~~~~~~~~
scales.cpp: In function 'void find_solution(std::vector<std::array<int, 6> >&, int, int)':
scales.cpp:120:18: warning: comparison of integer expressions of different signedness: 'std::vector<std::array<int, 6> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  120 |     if(cur.size()>lim or depth==0)
      |        ~~~~~~~~~~^~~~
scales.cpp:146:38: warning: conversion from 'long unsigned int' to 'int' may change value [-Wconversion]
  146 |                         int mx_sz=max({result_in_a.size(),result_in_b.size(),result_in_c.size()});
      |                                   ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
scales.cpp: In function 'void init(int)':
scales.cpp:169:15: warning: unused parameter 'TPPA' [-Wunused-parameter]
  169 | void init(int TPPA)
      |           ~~~~^~~~

• Subtask 1: 100 / 100