Submission #706189

#	Time	Username	Problem	Language	Result	Execution time	Memory
706189		bin9638	Scales (IOI15_scales)	C++17	72.62 / 100	25 ms	372 KiB

scales

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

using namespace std;

#define ll long long
#define fs first
#define sc second
#define N 12
#define pb push_back
#define ii pair<int,int>

#ifdef SKY
int p[N],w[N];
void answer(int W[])
{
    for(int i=0;i<6;i++)cout<<W[i]<<" ";cout<<endl;
}

bool SS(const int&u,const int&v)
{
    return w[u]<w[v];
}

int getHeaviest(int A, int B, int C)
{
    cout<<"cc\n";
    int f[3]={A,B,C};
    sort(f,f+3,SS);
    return f[2];
}

int getLightest(int A,int B,int C)
{
    cout<<"cc\n";
    int f[3]={A,B,C};
    sort(f,f+3,SS);
    return f[0];
}

int getMedian(int A, int B, int C)
{
    cout<<"cc\n";
    int f[3]={A,B,C};
    sort(f,f+3,SS);
    return f[1];
}

int getNextLightest(int A, int B, int C, int D)
{
    cout<<"cc\n";
    int f[3]={A,B,C};
    sort(f,f+3,SS);
    if(w[f[0]]>w[D])
        return f[0];
    if(w[f[1]]>w[D])
        return f[1];
    if(w[f[2]]>w[D])
        return f[2];
    return f[0];
}
#endif // SKY

int dem,ktr[732],b[N],hv[732][12],c[732][12];

void make_per(int pos)
{
    if(pos==7)
    {
        dem++;
        for(int i=1;i<=6;i++)
            hv[dem][i]=b[i],c[dem][b[i]]=i;
        return;
    }
    for(int i=1;i<=6;i++)
        if(ktr[i]==0)
        {
            b[pos]=i;
            ktr[i]=1;
            make_per(pos+1);
            ktr[i]=0;
        }
}

bool check_heaivest(int id,int A,int B,int C,int res)
{
    return (max(c[id][A],max(c[id][B],c[id][C]))==c[id][res]);
}

bool check_lightest(int id,int A,int B,int C,int res)
{
    return (min(c[id][A],min(c[id][B],c[id][C]))==c[id][res]);
}

bool check_median(int id,int A,int B,int C,int res)
{
    return (c[id][A]+c[id][B]+c[id][C]-min(c[id][A],min(c[id][B],c[id][C]))-max(c[id][A],max(c[id][B],c[id][C]))==c[id][res]);
}

bool check_next(int id,int A,int B,int C,int D,int res)
{
    if(c[id][A]>c[id][B])
        swap(A,B);
    if(c[id][A]>c[id][C])
        swap(A,C);
    if(c[id][B]>c[id][C])
        swap(B,C);
    if(c[id][A]>c[id][D])
        return(A==res);
    if(c[id][B]>c[id][D])
        return(B==res);
    if(c[id][C]>c[id][D])
        return(C==res);
    return (A==res);
}

void solve()
{
    int type=-1,bad_case=-1;
    vector<int>tv;
    //heaviest
    for(int A=1;A<=6;A++)
        for(int B=1;B<A;B++)
            for(int C=1;C<B;C++)
            {
                int cnt[3]={};
                for(int id=1;id<=dem;id++)
                    if(ktr[id]==0)
                    {
                        if(check_heaivest(id,A,B,C,A))
                            cnt[0]++;
                        if(check_heaivest(id,A,B,C,B))
                            cnt[1]++;
                        if(check_heaivest(id,A,B,C,C))
                            cnt[2]++;
                    }
                int val=max(cnt[0],max(cnt[1],cnt[2]));
                if(type==-1||val<bad_case)
                {
                    type=1;
                    bad_case=val;
                    tv={A,B,C};
                }
                if(val==bad_case&&rand()%2==0)
                {
                    type=1;
                    bad_case=val;
                    tv={A,B,C};
                }
            }
    //Lightest
    for(int A=1;A<=6;A++)
        for(int B=1;B<A;B++)
            for(int C=1;C<B;C++)
            {
                int cnt[3]={};
                for(int id=1;id<=dem;id++)
                    if(ktr[id]==0)
                    {
                        if(check_lightest(id,A,B,C,A))
                            cnt[0]++;
                        if(check_lightest(id,A,B,C,B))
                            cnt[1]++;
                        if(check_lightest(id,A,B,C,C))
                            cnt[2]++;
                    }
                int val=max(cnt[0],max(cnt[1],cnt[2]));
                if(type==-1||val<bad_case)
                {
                    type=2;
                    bad_case=val;
                    tv={A,B,C};
                }
                if(val==bad_case&&rand()%2==0)
                {
                    type=2;
                    bad_case=val;
                    tv={A,B,C};
                }
            }
    //Median
      for(int A=1;A<=6;A++)
        for(int B=1;B<A;B++)
            for(int C=1;C<B;C++)
            {
                int cnt[3]={};
                for(int id=1;id<=dem;id++)
                    if(ktr[id]==0)
                    {
                        if(check_median(id,A,B,C,A))
                            cnt[0]++;
                        if(check_median(id,A,B,C,B))
                            cnt[1]++;
                        if(check_median(id,A,B,C,C))
                            cnt[2]++;
                    }
                int val=max(cnt[0],max(cnt[1],cnt[2]));
                if(type==-1||val<bad_case)
                {
                    type=3;
                    bad_case=val;
                    tv={A,B,C};
                }
                if(val==bad_case&&rand()%2==0)
                {
                    type=3;
                    bad_case=val;
                    tv={A,B,C};
                }
            }
    //next
    for(int A=1;A<=6;A++)
        for(int B=1;B<A;B++)
            for(int C=1;C<B;C++)
                for(int D=1;D<=6;D++)
                    if(D!=A&&D!=B&&D!=C)
                    {
                        int cnt[3]={};
                        for(int id=1;id<=dem;id++)
                            if(ktr[id]==0)
                            {
                                if(check_next(id,A,B,C,D,A))
                                    cnt[0]++;
                                if(check_next(id,A,B,C,D,B))
                                    cnt[1]++;
                                if(check_next(id,A,B,C,D,C))
                                    cnt[2]++;
                            }
                        int val=max(cnt[0],max(cnt[1],cnt[2]));
                        if(type==-1||val<bad_case)
                        {
                            type=4;
                            bad_case=val;
                            tv={A,B,C,D};
                        }
                        if(val==bad_case&&rand()%2==0)
                        {
                            type=4;
                            bad_case=val;
                            tv={A,B,C,D};
                        }
                    }
    if(type==1)
    {
        int A=tv[0],B=tv[1],C=tv[2];
        int res=getHeaviest(A,B,C);
        for(int id=1;id<=dem;id++)
            if(ktr[id]==0)
            {
                if(!check_heaivest(id,A,B,C,res))
                    ktr[id]=1;
            }
    }
    if(type==2)
    {
        int A=tv[0],B=tv[1],C=tv[2];
        int res=getLightest(A,B,C);
        for(int id=1;id<=dem;id++)
            if(ktr[id]==0)
            {
                if(!check_lightest(id,A,B,C,res))
                    ktr[id]=1;
            }
    }
    if(type==3)
    {
        int A=tv[0],B=tv[1],C=tv[2];
        int res=getMedian(A,B,C);
        for(int id=1;id<=dem;id++)
            if(ktr[id]==0)
            {
                if(!check_median(id,A,B,C,res))
                    ktr[id]=1;
            }
    }
    if(type==4)
    {
        int A=tv[0],B=tv[1],C=tv[2],D=tv[3];
        int res=getNextLightest(A,B,C,D);
        for(int id=1;id<=dem;id++)
            if(ktr[id]==0)
            {
                if(!check_next(id,A,B,C,D,res))
                    ktr[id]=1;
            }
    }
}

void orderCoins()
{
    #ifdef SKY
    for(int i=1;i<=6;i++)
    {
       // p[i]=i;w[p[i]]=i;
        cin>>p[i],w[p[i]]=i;
    }
    #endif // SKY
    memset(ktr,0,sizeof(ktr));
    int res=getLightest(1,2,3);
    for(int i=1;i<=dem;i++)
        if(!check_lightest(i,1,2,3,res))
            ktr[i]=1;
   /* res=getHeaviest(4,5,6);
    for(int i=1;i<=dem;i++)
        if(!check_heaivest(i,4,5,6,res))
            ktr[i]=1;*/
    /*int cnt=0;
    for(int i=1;i<=dem;i++)if(ktr[i]==0)cnt++;
    cout<<cnt<<endl;*/
    while(1)
    {
        int sl=0;
        for(int i=1;i<=dem;i++)
            if(ktr[i]==0)
                sl++;
        if(sl>1)
            solve();
            else{
                int kq[6];
                for(int i=1;i<=dem;i++)
                    if(ktr[i]==0)
                    {
                        for(int j=1;j<=6;j++)
                            kq[j-1]=hv[i][j];
                        answer(kq);
                        return;
                    }
            }
    }
}

void init(int q)
{
    srand(time(0));
    make_per(1);
    //cout<<dem<<endl;
    #ifdef SKY
    while(q--)
        orderCoins();
    #endif // SKY
}

#ifdef SKY
int main()
{
    freopen("A.inp","r",stdin);
    freopen("A.out","w",stdout);
  //  ios::sync_with_stdio(0);
   // cin.tie(NULL);
   // cout.tie(NULL);
    int q;
    cin>>q;
    init(q);
    return 0;
}
#endif // SKY

Compilation message (stderr)

scales.cpp: In function 'void init(int)':
scales.cpp:336:15: warning: conversion from 'time_t' {aka 'long int'} to 'unsigned int' may change value [-Wconversion]
  336 |     srand(time(0));
      |           ~~~~^~~
scales.cpp:334:15: warning: unused parameter 'q' [-Wunused-parameter]
  334 | void init(int q)
      |           ~~~~^

• Subtask 1: 72.619048 / 100