Submission #638989

#	Time	Username	Problem	Language	Result	Execution time	Memory
638989		ggoh	Scales (IOI15_scales)	C++14	0 / 100	1 ms	340 KiB

scales

#include "scales.h"
#include<bits/stdc++.h>
using namespace std;
#define sz(v) ((int)(v).size())
typedef long long lint;
int ans,rev[720][7],sz;
int c[7],a[7];
void br(int p)
{
    if(p==7)
    {
        for(int i=1;i<=6;i++)
        {
            rev[sz][i]=a[i];
        }
        sz++;
        return ;
    }
    for(int i=1;i<=6;i++)
    {
        if(!c[i])
        {
            c[i]=1;
            a[p]=i;
            br(p+1);
            a[p]=0;
            c[i]=0;
        }
    }
}

void init(int T) {
    sz=0;
    br(1);
}

void f(vector<int> X)
{
    int n=sz(X);
    if(n==1)
    {
        ans=X[0];
        return;
    }
    int u=(n+2)/3;

    for(int i=1;i<=6;i++)
    {
        for(int j=i+1;j<=6;j++)
        {
            for(int k=j+1;k<=6;k++)
            {
                //getHeaviest
                vector<int>Xi;
                vector<int>Xj;
                vector<int>Xk;
                for(auto &x:X)
                {
                    if(rev[x][i]>rev[x][j] && rev[x][i]>rev[x][k])Xi.push_back(x);
                    if(rev[x][j]>rev[x][i] && rev[x][j]>rev[x][k])Xj.push_back(x);
                    if(rev[x][k]>rev[x][i] && rev[x][k]>rev[x][j])Xk.push_back(x);
                }
                if(sz(Xi)<=u && sz(Xj)<=u && sz(Xk)<=u)
                {
                    int t=getHeaviest(i,j,k);
                    if(t==i)f(Xi);
                    else if(t==j)f(Xj);
                    else f(Xk);
                    return ;
                }
                //getMedian
                Xi.clear();
                Xj.clear();
                Xk.clear();
                for(auto &x:X)
                {
                    if((rev[x][i]>rev[x][j] && rev[x][i]<rev[x][k]) || (rev[x][i]<rev[x][j] && rev[x][i]>rev[x][k]))Xi.push_back(x);
                    if((rev[x][j]>rev[x][i] && rev[x][j]<rev[x][k])||(rev[x][j]<rev[x][i] && rev[x][j]>rev[x][k]))Xj.push_back(x);
                    if((rev[x][k]>rev[x][i] && rev[x][k]<rev[x][j])||(rev[x][k]<rev[x][i] && rev[x][k]>rev[x][j]))Xk.push_back(x);
                }
                if(sz(Xi)<=u && sz(Xj)<=u && sz(Xk)<=u)
                {
                    int t=getMedian(i,j,k);
                    if(t==i)f(Xi);
                    else if(t==j)f(Xj);
                    else f(Xk);
                    return ;
                }

                //getLightest
                Xi.clear();
                Xj.clear();
                Xk.clear();
                for(auto &x:X)
                {
                    if(rev[x][i]<rev[x][j] && rev[x][i]<rev[x][k])Xi.push_back(x);
                    if(rev[x][j]<rev[x][i] && rev[x][j]<rev[x][k])Xj.push_back(x);
                    if(rev[x][k]<rev[x][i] && rev[x][k]<rev[x][j])Xk.push_back(x);
                }
                if(sz(Xi)<=u && sz(Xj)<=u && sz(Xk)<=u)
                {
                    int t=getLightest(i,j,k);
                    if(t==i)f(Xi);
                    else if(t==j)f(Xj);
                    else f(Xk);
                    return ;
                }
                
                //getNextLightest
                for(int l=1;l<=6;l++)
                {
                    if(l!=i && l!=j && l!=k)
                    {
                        Xi.clear();
                        Xj.clear();
                        Xk.clear();
                        for(auto &x:X)
                        {
                            if(rev[x][l]>rev[x][i]&&rev[x][l]>rev[x][j]&&rev[x][l]>rev[x][k])
                            {
                                if(rev[x][i]<rev[x][j] && rev[x][i]<rev[x][k])Xi.push_back(x);
                                if(rev[x][j]<rev[x][i] && rev[x][j]<rev[x][k])Xj.push_back(x);
                                if(rev[x][k]<rev[x][i] && rev[x][k]<rev[x][j])Xk.push_back(x);
                            }
                            else
                            {
                                if(rev[x][l]<rev[x][i] && !(rev[x][l]<rev[x][j] && rev[x][j]<rev[x][i]) && !(rev[x][l]<rev[x][k] && rev[x][k]<rev[x][i]))Xi.push_back(x);
                                if(rev[x][l]<rev[x][j] && !(rev[x][l]<rev[x][i] && rev[x][i]<rev[x][j]) && !(rev[x][l]<rev[x][k] && rev[x][k]<rev[x][j]))Xj.push_back(x);
                                if(rev[x][l]<rev[x][k] && !(rev[x][l]<rev[x][i] && rev[x][i]<rev[x][k]) && !(rev[x][l]<rev[x][j] && rev[x][j]<rev[x][k]))Xk.push_back(x);
                            }
                        }
                        if(sz(Xi)<=u && sz(Xj)<=u && sz(Xk)<=u)
                        {
                            int t=getNextLightest(i,j,k,l);
                            if(t==i)f(Xi);
                            else if(t==j)f(Xj);
                            else f(Xk);
                            return ;
                        }
                    }
                }
            }
        }
    }


    //puts("mang");
}

void orderCoins() {
    
    vector<int>X;
    for(int i=0;i<720;i++)X.push_back(i);
    f(X);
    int W[6];
    for(int i=1;i<=6;i++)W[rev[ans][i]-1]=i;
    answer(W);
}

Compilation message (stderr)

scales.cpp: In function 'void init(int)':
scales.cpp:32:15: warning: unused parameter 'T' [-Wunused-parameter]
   32 | void init(int T) {
      |           ~~~~^

• Subtask 1: 0 / 100