Submission #1188486

#	Time	Username	Problem	Language	Result	Execution time	Memory
1188486		simona1230	Scales (IOI15_scales)	C++20	0 / 100	1095 ms	320 KiB

scales

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

int id;
int p[750][7];
int r[750][7];
int in[7],h[7];
void prec(int i)
{
    if(i==7)
    {
        id++;
        for(int j=1;j<=6;j++)
            p[id][j]=h[j],r[id][h[j]]=j;
        return;
    }

    for(int j=1;j<=6;j++)
    {
        if(in[j])continue;
        in[j]=1;
        h[i]=j;
        prec(i+1);
        in[j]=0;
    }
}

int ch[5000][3];
int c[32][4],id2;
void prec2(int i)
{
    if(i==4)
    {
        id2++;
        for(int j=1;j<=6;j++)
            c[id2][1]=h[1],c[id2][2]=h[2],c[id2][3]=h[3];
        return;
    }

    for(int j=h[i-1];j<=6;j++)
    {
        if(in[j])continue;
        in[j]=1;
        h[i]=j;
        prec2(i+1);
        in[j]=0;
    }
}
int act[5000][750];
int op[5000];
int lf[5000];

bool build(int i,int cnt)
{
    int all=0,here=0;
    for(int j=1;j<=id;j++)
        if(act[i][j])all++,here=j;

    if(all==1)
    {
        lf[i]=here;
        return 1;
    }

    if(cnt==0)return 0;

    for(int t=0;t<3;t++)
    {
        for(int x=1;x<=id2;x++)
        {
            int i1=c[x][1],i2=c[x][2],i3=c[x][3];
            for(int j=1;j<=id;j++)
            {
                act[ch[i][0]][j]=act[ch[i][1]][j]=act[ch[i][2]][j]=0;
                if(!act[i][j])continue;
                if(t==0)
                {
                    if(r[j][i1]<r[j][i2]&&r[j][i1]<r[j][i3])act[ch[i][0]][j]=1;
                    else if(r[j][i2]<r[j][i1]&&r[j][i2]<r[j][i3])act[ch[i][1]][j]=1;
                    else act[ch[i][2]][j]=1;
                }
                if(t==1)
                {
                    if(r[j][i1]>r[j][i2]&&r[j][i1]>r[j][i3])act[ch[i][0]][j]=1;
                    else if(r[j][i2]>r[j][i1]&&r[j][i2]>r[j][i3])act[ch[i][1]][j]=1;
                    else act[ch[i][2]][j]=1;
                }
                if(t==2)
                {
                    if(r[j][i1]<max(r[j][i2],r[j][i3])&&r[j][i1]>min(r[j][i2],r[j][i3]))act[ch[i][0]][j]=1;
                    else if(r[j][i2]<max(r[j][i1],r[j][i3])&&r[j][i2]>min(r[j][i1],r[j][i3]))act[ch[i][1]][j]=1;
                    else act[ch[i][2]][j]=1;
                }
            }

            if(build(ch[i][0],cnt-1)&&build(ch[i][1],cnt-1)&&build(ch[i][2],cnt-1))
            {
                op[i]=x*10+t;
                return 1;
            }
        }
    }
    return 0;
}


void init(int T) {}

int w[6];
void orderCoins()
{
    prec(1);
    prec2(1);
    int f=2;
    vector<int> lvl={1},pr={};
    for(int i=1;i<=6;i++)
    {
        pr=lvl;
        lvl.clear();
        for(int j=0;j<pr.size();j++)
        {
            int g=pr[j];
            ch[g][0]=f;
            ch[g][1]=f+1;
            ch[g][2]=f+2;
            lvl.push_back(f);
            lvl.push_back(f+1);
            lvl.push_back(f+2);
        }
    }

    build(1,6);

    int i=1;
    while(lf[i]==0)
    {
        int j=op[i]/10,x;
        if(op[i]%10==1)x=getLightest(c[j][1],c[j][2],c[j][3]);
        else if(op[i]%10==2)x=getMedian(c[j][1],c[j][2],c[j][3]);
        else x=getHeaviest(c[j][1],c[j][2],c[j][3]);

        if(x==c[j][1])i=ch[i][0];
        else if(x==c[j][2])i=ch[i][1];
        else i=ch[i][2];
    }

    answer(p[lf[i]]);
}

• Subtask 1: 0 / 100