Submission #886688

#TimeUsernameProblemLanguageResultExecution timeMemory
886688HuyQuang_re_ZeroScales (IOI15_scales)C++14
100 / 100
28 ms884 KiB
#include <bits/stdc++.h>
#define db long double
#define II pair <ll,ll>
#define III pair <ll,II>
#define IV pair <vector <int>,vector <int> >
#define TII pair <treap*,treap*>
#define fst first
#define snd second
#define BIT(x,i) ((x>>i)&1)
#define pi acos(-1)
#define to_radian(x) (x*pi/180.0)
#define to_degree(x) (x*180.0/pi)
#define Log(x) (31-__builtin_clz((int)x))
#define LogLL(x) (63-__builtin_clzll((ll)x))
#include "scales.h"
using namespace std;
/*
struct Interactive
{
    int a[7]={ 0,3,4,6,2,1,5 };
    int Query(int type,int A,int B,int C,int D)
    {
        int val[4]={ 0,a[A],a[B],a[C] };
        sort(val+1,val+4);
        int k;
        if(type<=3) k=val[type];
        else if(val[3]<a[D]) k=val[1];
        else
        {
            for(int i=3;i>=1;i--)
                if(val[i]>a[D]) k=val[i];
        }
        if(a[A]==k) return A;
        if(a[B]==k) return B;
        if(a[C]==k) return C;
    }

} IR;
int getLightest(int A,int B,int C) { return IR.Query(1,A,B,C,0); }
int getMedian(int A,int B,int C) { return IR.Query(2,A,B,C,0); }
int getHeaviest(int A,int B,int C) { return IR.Query(3,A,B,C,0); }
int getNextLightest(int A,int B,int C,int D) { return IR.Query(4,A,B,C,D); }
void answer(int w[])
{
    for(int i=0;i<6;i++) cout<<w[i]<<" ";
}
*/
struct query { int type,A,B,C,D; };
vector <query> query_set;
map <vector <vector <int> >,query> opt;
int limit[6]={ 243,81,27,9,3,1 };
vector <vector <int> > Set;
int Encode_answer(vector <int> a,query q)
{
    int val[4]={ 0,a[q.A-1],a[q.B-1],a[q.C-1] };
    sort(val+1,val+4);
    int k;
    if(q.type<=3) k=val[q.type];
    else if(val[3]<a[q.D-1]) k=val[1];
    else
    {
        for(int i=3;i>=1;i--)
            if(val[i]>a[q.D-1]) k=val[i];
    }
    if(a[q.A-1]==k) return 0;
    if(a[q.B-1]==k) return 1;
    if(a[q.C-1]==k) return 2;
}


bool check(vector <vector <int> > Set,int step)
{
    if(Set.size()<2) return 1;
    for(query q:query_set)
    {
        vector <vector <int> > split[3];
        for(vector <int> x:Set)
            split[Encode_answer(x,q)].push_back(x);
        int lim=min(limit[step],(int)Set.size()-1);
        if(split[0].size()<=lim && split[1].size()<=lim && split[2].size()<=lim)
        {
            if(check(split[0],step+1) && check(split[1],step+1) && check(split[2],step+1))
            {
                opt[Set]=q;
                return 1;
            }
        }
    }
    return 0;
}
void init(int k)
{
    for(int type=1;type<=4;type++)
        for(int i=1;i<=6;i++)
            for(int j=i+1;j<=6;j++)
                for(int k=j+1;k<=6;k++)
                    if(type<4) query_set.push_back({ type,i,j,k,0 });
                    else
                        for(int h=1;h<=6;h++)
                            if(h!=i && h!=j && h!=k)
                                query_set.push_back({ type,i,j,k,h });
    vector <int> vec;
    for(int i=1;i<=6;i++) vec.push_back(i);
    do
    {
        Set.push_back(vec);
    }
    while(next_permutation(vec.begin(),vec.end()));
    check(Set,0);
}




vector <int> solve(vector <vector <int> > Set)
{
    if(Set.size()==1) return Set[0];
    query q=opt[Set];
    vector <vector <int> > split[3];
    for(vector <int> x:Set)
        split[Encode_answer(x,q)].push_back(x);
    int ok,num;
    if(q.type==1) ok=getLightest(q.A,q.B,q.C);
    if(q.type==2) ok=getMedian(q.A,q.B,q.C);
    if(q.type==3) ok=getHeaviest(q.A,q.B,q.C);
    if(q.type==4) ok=getNextLightest(q.A,q.B,q.C,q.D);
    if(ok==q.A) num=0;
    if(ok==q.B) num=1;
    if(ok==q.C) num=2;
    return solve(split[num]);
}
void orderCoins()
{
    vector <int> vec=solve(Set);
    int w[6];
    for(int i=1;i<=6;i++)
        for(int j=0;j<6;j++)
            if(vec[j]==i) w[i-1]=j+1;
    answer(w);
}
/*
int main()
{
    freopen("scales.inp","r",stdin);
    freopen("scales.out","w",stdout);
    init(0);
    orderCoins();
}
*/

Compilation message (stderr)

scales.cpp: In function 'bool check(std::vector<std::vector<int> >, int)':
scales.cpp:71:35: warning: declaration of 'Set' shadows a global declaration [-Wshadow]
   71 | bool check(vector <vector <int> > Set,int step)
      |            ~~~~~~~~~~~~~~~~~~~~~~~^~~
scales.cpp:52:24: note: shadowed declaration is here
   52 | vector <vector <int> > Set;
      |                        ^~~
scales.cpp:80:27: warning: comparison of integer expressions of different signedness: 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   80 |         if(split[0].size()<=lim && split[1].size()<=lim && split[2].size()<=lim)
      |            ~~~~~~~~~~~~~~~^~~~~
scales.cpp:80:51: warning: comparison of integer expressions of different signedness: 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   80 |         if(split[0].size()<=lim && split[1].size()<=lim && split[2].size()<=lim)
      |                                    ~~~~~~~~~~~~~~~^~~~~
scales.cpp:80:75: warning: comparison of integer expressions of different signedness: 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   80 |         if(split[0].size()<=lim && split[1].size()<=lim && split[2].size()<=lim)
      |                                                            ~~~~~~~~~~~~~~~^~~~~
scales.cpp: In function 'void init(int)':
scales.cpp:96:25: warning: declaration of 'int k' shadows a parameter [-Wshadow]
   96 |                 for(int k=j+1;k<=6;k++)
      |                         ^
scales.cpp:91:15: note: shadowed declaration is here
   91 | void init(int k)
      |           ~~~~^
scales.cpp:91:15: warning: unused parameter 'k' [-Wunused-parameter]
scales.cpp: In function 'std::vector<int> solve(std::vector<std::vector<int> >)':
scales.cpp:115:43: warning: declaration of 'Set' shadows a global declaration [-Wshadow]
  115 | vector <int> solve(vector <vector <int> > Set)
      |                    ~~~~~~~~~~~~~~~~~~~~~~~^~~
scales.cpp:52:24: note: shadowed declaration is here
   52 | vector <vector <int> > Set;
      |                        ^~~
scales.cpp: In function 'int Encode_answer(std::vector<int>, query)':
scales.cpp:68:1: warning: control reaches end of non-void function [-Wreturn-type]
   68 | }
      | ^
scales.cpp:66:5: warning: 'k' may be used uninitialized in this function [-Wmaybe-uninitialized]
   66 |     if(a[q.B-1]==k) return 1;
      |     ^~
scales.cpp: In function 'std::vector<int> solve(std::vector<std::vector<int> >)':
scales.cpp:128:5: warning: 'ok' may be used uninitialized in this function [-Wmaybe-uninitialized]
  128 |     if(ok==q.B) num=1;
      |     ^~
#Verdict Execution timeMemoryGrader output
Fetching results...