Submission #1193752

#	Time	Username	Problem	Language	Result	Execution time	Memory
1193752		DobromirAngelov	Scales (IOI15_scales)	C++20	100 / 100	32 ms	1352 KiB

scales

#include "scales.h"
#include<bits/stdc++.h>

using namespace std;

const int MAXV=1e4+5;
const int maxP[7]={1,3,9,27,81,243,729};

struct Query
{
    int a,b,c,d;

    Query() {};
    Query(int _a,int _b,int _c,int _d)
    {
        a=_a; b=_b; c=_c; d=_d;
    }

    int query()
    {
        int res=0;
        if(d==a) res=getLightest(a,b,c);
        else if(d==b) res=getMedian(a,b,c);
        else if(d==c) res=getHeaviest(a,b,c);
        else res=getNextLightest(a,b,c,d);
        if(res==a) return 0;
        if(res==b) return 1;
        if(res==c) return 2;
    }

    int getAns(vector<int> cur)
    {
        int ia,ib,ic,id;
        for(int i=0;i<6;i++)
        {
            if(cur[i]==a) ia=i;
            if(cur[i]==b) ib=i;
            if(cur[i]==c) ic=i;
            if(cur[i]==d) id=i;
        }
        int mn=min(ia, min(ib, ic));
        int mx=max(ia, max(ib, ic));
        int m=ia+ib+ic-mn-mx;
        bool fl=1;
        if(d!=a && d!=b && d!=c) fl=0;
        if(d==a || (fl==0 && (id<mn || id>mx)))
        {
            if(ia==mn) return 0;
            if(ib==mn) return 1;
            if(ic==mn) return 2;
        }
        if(d==b || (fl==0 && (id>mn && id<m)))
        {
            if(ia==m) return 0;
            if(ib==m) return 1;
            if(ic==m) return 2;
        }
        if(d==c || (fl==0 && (id>m && id<mx)))
        {
            if(ia==mx) return 0;
            if(ib==mx) return 1;
            if(ic==mx) return 2;
        }
    }
};
vector<Query> queries;

struct Node
{
    int rem;
    vector<vector<int> > poss;
    Query qr;
    int children[3];
};
Node tree[MAXV];

bool build(int ind)
{
    if(tree[ind].poss.size()<=1) return 1;
    // if(tree[ind].rem<0) return 0;

    tree[ind].children[0]=3*ind+1;
    tree[ind].children[1]=3*ind+2;
    tree[ind].children[2]=3*ind+3;

    int cnt[3];
    for(Query &qr: queries)
    {
        cnt[0]=cnt[1]=cnt[2]=0;
        for(auto &cur: tree[ind].poss)
        {
            int x=qr.getAns(cur);
            cnt[x]++;
            if(cnt[x]>maxP[tree[ind].rem]) break;
        }
        if(max(cnt[0], max(cnt[1], cnt[2]))>maxP[tree[ind].rem]) continue;

        for(int i=0;i<3;i++)
        {
            tree[tree[ind].children[i]].poss.clear();
            tree[tree[ind].children[i]].rem=tree[ind].rem-1;
        }
        for(auto &cur: tree[ind].poss)
        {
            tree[tree[ind].children[qr.getAns(cur)]].poss.push_back(cur);
        }

        bool fl=1;
        for(int i=0;i<3;i++) fl&=build(tree[ind].children[i]);
        if(!fl) continue;
        else 
        {
            tree[ind].qr=qr;
            return 1;
        }
    }
    return 0;
}

void init(int T) 
{
    for(int i=1;i<=4;i++)
        for(int j=i+1;j<=5;j++)
            for(int k=j+1;k<=6;k++)
                for(int h=1;h<=6;h++)
                    queries.push_back(Query(i,j,k,h));
    
    tree[0].rem=5;
    vector<int> v={1,2,3,4,5,6};
    do
    {
        tree[0].poss.push_back(v);
    } while (next_permutation(v.begin(), v.end()));
    build(0);
}

int a[6];
void orderCoins() 
{
    int ind=0;
    while(tree[ind].poss.size()>1)
    {
        ind=tree[ind].children[tree[ind].qr.query()];
    }
    for(int i=0;i<6;i++) a[i]=tree[ind].poss[0][i];
    answer(a);
}

Compilation message (stderr)

scales.cpp: In member function 'int Query::getAns(std::vector<int>)':
scales.cpp:64:5: warning: control reaches end of non-void function [-Wreturn-type]
   64 |     }
      |     ^
scales.cpp: In member function 'int Query::query()':
scales.cpp:29:5: warning: control reaches end of non-void function [-Wreturn-type]
   29 |     }
      |     ^

• Subtask 1: 100 / 100