Submission #73501

#	Time	Username	Problem	Language	Result	Execution time	Memory
73501		MKopchev	Scales (IOI15_scales)	C++14	100 / 100	141 ms	1132 KiB

scales

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

vector< vector<int> > active;
vector<int> all;

map< vector< vector<int> >,bool > seen[15];
int maxi(int a,int b,int c)
{
    return max(max(a,b),c);
}
int mini(int a,int b,int c)
{
    return min(min(a,b),c);
}
int lim[10]={1,3,9,27,81,243,729,2187,6561};
bool can(int tests,vector< vector<int> > &now)
{
//cout<<tests<<" "<<now.size()<<endl;
if(now.size()<=1)return 1;
if(lim[tests]<now.size())return 0;
if(seen[tests].count(now))return seen[tests][now];

for(int i=0;i<6;i++)
    for(int j=i+1;j<6;j++)
        for(int p=j+1;p<6;p++)
    {
        vector< vector<int> > a1={},a2={},a3={};
        for(auto k:now)
        {
            if(k[i]>k[j]&&k[i]>k[p])a1.push_back(k);
            if(k[j]>k[p]&&k[j]>k[i])a2.push_back(k);
            if(k[p]>k[i]&&k[p]>k[j])a3.push_back(k);
        }
        if(lim[tests-1]<a1.size()||lim[tests-1]<a2.size()||lim[tests-1]<a3.size())continue;
        //if(maxi(a1.size(),a2.size(),a3.size())-mini(a1.size(),a2.size(),a3.size())>1)continue;
        if(can(tests-1,a1)&&can(tests-1,a2)&&can(tests-1,a3)){seen[tests][now]=1;return 1;}
    }

for(int i=0;i<6;i++)
    for(int j=i+1;j<6;j++)
        for(int p=j+1;p<6;p++)
    {
    vector< vector<int> > a1={},a2={},a3={};
        for(auto k:now)
        {
            if(k[i]<k[j]&&k[i]<k[p])a1.push_back(k);
            if(k[j]<k[p]&&k[j]<k[i])a2.push_back(k);
            if(k[p]<k[i]&&k[p]<k[j])a3.push_back(k);
        }
        if(lim[tests-1]<a1.size()||lim[tests-1]<a2.size()||lim[tests-1]<a3.size())continue;
        //if(maxi(a1.size(),a2.size(),a3.size())-mini(a1.size(),a2.size(),a3.size())>1)continue;
        if(can(tests-1,a1)&&can(tests-1,a2)&&can(tests-1,a3)){seen[tests][now]=1;return 1;}
    }

for(int i=0;i<6;i++)
    for(int j=i+1;j<6;j++)
        for(int p=j+1;p<6;p++)
    {
    vector< vector<int> > a1={},a2={},a3={};
        for(auto k:now)
        {
            if((k[i]<k[j])^(k[i]<k[p]))a1.push_back(k);
            if((k[j]<k[p])^(k[j]<k[i]))a2.push_back(k);
            if((k[p]<k[i])^(k[p]<k[j]))a3.push_back(k);
        }
        if(lim[tests-1]<a1.size()||lim[tests-1]<a2.size()||lim[tests-1]<a3.size())continue;
        //if(maxi(a1.size(),a2.size(),a3.size())-mini(a1.size(),a2.size(),a3.size())>1)continue;
        if(can(tests-1,a1)&&can(tests-1,a2)&&can(tests-1,a3)){seen[tests][now]=1;return 1;}
    }

for(int i=0;i<6;i++)
    for(int j=i+1;j<6;j++)
        for(int p=j+1;p<6;p++)
            for(int q=0;q<6;q++)
            {
            if(i==q||j==q||p==q)continue;
            vector< vector<int> > a1={},a2={},a3={};
            for(auto k:now)
            {
            int ans=-1;
            bool spec=0;
            if(k[q]>k[i]&&k[q]>k[j]&&k[q]>k[p])spec=1;
            if(spec||k[q]<k[i])
            {
                if(ans==-1||k[ans]>k[i])ans=i;
            }

            if(spec||k[q]<k[j])
            {
                if(ans==-1||k[ans]>k[j])ans=j;
            }

            if(spec||k[q]<k[p])
            {
                if(ans==-1||k[ans]>k[p])ans=p;
            }
            if(ans==i)a1.push_back(k);
            if(ans==j)a2.push_back(k);
            if(ans==p)a3.push_back(k);
            }
            if(lim[tests-1]<a1.size()||lim[tests-1]<a2.size()||lim[tests-1]<a3.size())continue;
            //if(maxi(a1.size(),a2.size(),a3.size())-mini(a1.size(),a2.size(),a3.size())>1)continue;
            if(can(tests-1,a1)&&can(tests-1,a2)&&can(tests-1,a3)){seen[tests][now]=1;return 1;}
            }

    seen[tests][now]=0;
    return 0;
}

int output[6];
void write(int tests,vector< vector<int> > &now)
{
//cout<<tests<<" "<<now.size()<<endl;
if(now.size()<=1)
{
    assert(now.size()==1);
    for(int i=0;i<6;i++)
    {
        output[now[0][i]]=i+1;
    }
    return;
}
//if(seen[tests].count(now))return seen[tests][now];

for(int i=0;i<6;i++)
    for(int j=i+1;j<6;j++)
        for(int p=j+1;p<6;p++)
    {
        vector< vector<int> > a1={},a2={},a3={};
        for(auto k:now)
        {
            if(k[i]>k[j]&&k[i]>k[p])a1.push_back(k);
            if(k[j]>k[p]&&k[j]>k[i])a2.push_back(k);
            if(k[p]>k[i]&&k[p]>k[j])a3.push_back(k);
        }
        if(lim[tests-1]<a1.size()||lim[tests-1]<a2.size()||lim[tests-1]<a3.size())continue;
        //if(maxi(a1.size(),a2.size(),a3.size())-mini(a1.size(),a2.size(),a3.size())>1)continue;
        if(can(tests-1,a1)&&can(tests-1,a2)&&can(tests-1,a3))
        {
            int ans=getHeaviest(i+1,j+1,p+1)-1;
            if(i==ans)write(tests-1,a1);
            if(j==ans)write(tests-1,a2);
            if(p==ans)write(tests-1,a3);
            return;
        }
    }

for(int i=0;i<6;i++)
    for(int j=i+1;j<6;j++)
        for(int p=j+1;p<6;p++)
    {
    vector< vector<int> > a1={},a2={},a3={};
        for(auto k:now)
        {
            if(k[i]<k[j]&&k[i]<k[p])a1.push_back(k);
            if(k[j]<k[p]&&k[j]<k[i])a2.push_back(k);
            if(k[p]<k[i]&&k[p]<k[j])a3.push_back(k);
        }
        if(lim[tests-1]<a1.size()||lim[tests-1]<a2.size()||lim[tests-1]<a3.size())continue;
        //if(maxi(a1.size(),a2.size(),a3.size())-mini(a1.size(),a2.size(),a3.size())>1)continue;
        if(can(tests-1,a1)&&can(tests-1,a2)&&can(tests-1,a3))
        {
            int ans=getLightest(i+1,j+1,p+1)-1;
            if(i==ans)write(tests-1,a1);
            if(j==ans)write(tests-1,a2);
            if(p==ans)write(tests-1,a3);
            return;
        }
    }

for(int i=0;i<6;i++)
    for(int j=i+1;j<6;j++)
        for(int p=j+1;p<6;p++)
    {
    vector< vector<int> > a1={},a2={},a3={};
        for(auto k:now)
        {
            if((k[i]<k[j])^(k[i]<k[p]))a1.push_back(k);
            if((k[j]<k[p])^(k[j]<k[i]))a2.push_back(k);
            if((k[p]<k[i])^(k[p]<k[j]))a3.push_back(k);
        }
        if(lim[tests-1]<a1.size()||lim[tests-1]<a2.size()||lim[tests-1]<a3.size())continue;
        //if(maxi(a1.size(),a2.size(),a3.size())-mini(a1.size(),a2.size(),a3.size())>1)continue;
        if(can(tests-1,a1)&&can(tests-1,a2)&&can(tests-1,a3))
        {
            int ans=getMedian(i+1,j+1,p+1)-1;
            if(i==ans)write(tests-1,a1);
            if(j==ans)write(tests-1,a2);
            if(p==ans)write(tests-1,a3);
            return;
        }
    }

for(int i=0;i<6;i++)
    for(int j=i+1;j<6;j++)
        for(int p=j+1;p<6;p++)
            for(int q=0;q<6;q++)
            {
            if(i==q||j==q||p==q)continue;
            vector< vector<int> > a1={},a2={},a3={};
            for(auto k:now)
            {
            int ans=-1;
            bool spec=0;
            if(k[q]>k[i]&&k[q]>k[j]&&k[q]>k[p])spec=1;
            if(spec||k[q]<k[i])
            {
                if(ans==-1||k[ans]>k[i])ans=i;
            }

            if(spec||k[q]<k[j])
            {
                if(ans==-1||k[ans]>k[j])ans=j;
            }

            if(spec||k[q]<k[p])
            {
                if(ans==-1||k[ans]>k[p])ans=p;
            }
            if(ans==i)a1.push_back(k);
            if(ans==j)a2.push_back(k);
            if(ans==p)a3.push_back(k);
            }
            if(lim[tests-1]<a1.size()||lim[tests-1]<a2.size()||lim[tests-1]<a3.size())continue;
            //if(maxi(a1.size(),a2.size(),a3.size())-mini(a1.size(),a2.size(),a3.size())>1)continue;
                if(can(tests-1,a1)&&can(tests-1,a2)&&can(tests-1,a3))
                {
                int ans=getNextLightest(i+1,j+1,p+1,q+1)-1;
                if(i==ans)write(tests-1,a1);
                if(j==ans)write(tests-1,a2);
                if(p==ans)write(tests-1,a3);
                return;
                }
            }
assert(0==1);
}


void init(int T)
{
    all={};
    for(int i=0;i<=5;i++)
        all.push_back(i);
    active={};
    do
    {
        active.push_back(all);
    }
    while(next_permutation(all.begin(),all.end()));
    //assert(can(7,active));
    assert(can(6,active));
}
void orderCoins()
{
    all={};
    for(int i=0;i<=5;i++)
        all.push_back(i);
    active={};
    do
    {
        active.push_back(all);
    }
    while(next_permutation(all.begin(),all.end()));
    write(6,active);
    answer(output);
    //write(8,active);
}
/*
int main()
{
    init(12);
    orderCoins();
}
*/

Compilation message (stderr)

In file included from grader.c:2:0:
graderlib.c: In function 'void answer(int*)':
graderlib.c:53:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
     if (_ghksjhdfkae19ga_ > 1) 
     ^~
graderlib.c:56:2: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
  for (i = 0; i < 6; i++) {
  ^~~
scales.cpp: In function 'bool can(int, std::vector<std::vector<int> >&)':
scales.cpp:22:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 if(lim[tests]<now.size())return 0;
    ~~~~~~~~~~^~~~~~~~~~~
scales.cpp:36:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if(lim[tests-1]<a1.size()||lim[tests-1]<a2.size()||lim[tests-1]<a3.size())continue;
            ~~~~~~~~~~~~^~~~~~~~~~
scales.cpp:36:48: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if(lim[tests-1]<a1.size()||lim[tests-1]<a2.size()||lim[tests-1]<a3.size())continue;
                                    ~~~~~~~~~~~~^~~~~~~~~~
scales.cpp:36:72: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if(lim[tests-1]<a1.size()||lim[tests-1]<a2.size()||lim[tests-1]<a3.size())continue;
                                                            ~~~~~~~~~~~~^~~~~~~~~~
scales.cpp:52:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if(lim[tests-1]<a1.size()||lim[tests-1]<a2.size()||lim[tests-1]<a3.size())continue;
            ~~~~~~~~~~~~^~~~~~~~~~
scales.cpp:52:48: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if(lim[tests-1]<a1.size()||lim[tests-1]<a2.size()||lim[tests-1]<a3.size())continue;
                                    ~~~~~~~~~~~~^~~~~~~~~~
scales.cpp:52:72: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if(lim[tests-1]<a1.size()||lim[tests-1]<a2.size()||lim[tests-1]<a3.size())continue;
                                                            ~~~~~~~~~~~~^~~~~~~~~~
scales.cpp:68:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if(lim[tests-1]<a1.size()||lim[tests-1]<a2.size()||lim[tests-1]<a3.size())continue;
            ~~~~~~~~~~~~^~~~~~~~~~
scales.cpp:68:48: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if(lim[tests-1]<a1.size()||lim[tests-1]<a2.size()||lim[tests-1]<a3.size())continue;
                                    ~~~~~~~~~~~~^~~~~~~~~~
scales.cpp:68:72: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if(lim[tests-1]<a1.size()||lim[tests-1]<a2.size()||lim[tests-1]<a3.size())continue;
                                                            ~~~~~~~~~~~~^~~~~~~~~~
scales.cpp:103:28: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             if(lim[tests-1]<a1.size()||lim[tests-1]<a2.size()||lim[tests-1]<a3.size())continue;
                ~~~~~~~~~~~~^~~~~~~~~~
scales.cpp:103:52: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             if(lim[tests-1]<a1.size()||lim[tests-1]<a2.size()||lim[tests-1]<a3.size())continue;
                                        ~~~~~~~~~~~~^~~~~~~~~~
scales.cpp:103:76: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             if(lim[tests-1]<a1.size()||lim[tests-1]<a2.size()||lim[tests-1]<a3.size())continue;
                                                                ~~~~~~~~~~~~^~~~~~~~~~
scales.cpp:73:1: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
 for(int i=0;i<6;i++)
 ^~~
scales.cpp:108:5: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
     seen[tests][now]=0;
     ^~~~
scales.cpp: In function 'void write(int, std::vector<std::vector<int> >&)':
scales.cpp:138:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if(lim[tests-1]<a1.size()||lim[tests-1]<a2.size()||lim[tests-1]<a3.size())continue;
            ~~~~~~~~~~~~^~~~~~~~~~
scales.cpp:138:48: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if(lim[tests-1]<a1.size()||lim[tests-1]<a2.size()||lim[tests-1]<a3.size())continue;
                                    ~~~~~~~~~~~~^~~~~~~~~~
scales.cpp:138:72: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if(lim[tests-1]<a1.size()||lim[tests-1]<a2.size()||lim[tests-1]<a3.size())continue;
                                                            ~~~~~~~~~~~~^~~~~~~~~~
scales.cpp:161:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if(lim[tests-1]<a1.size()||lim[tests-1]<a2.size()||lim[tests-1]<a3.size())continue;
            ~~~~~~~~~~~~^~~~~~~~~~
scales.cpp:161:48: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if(lim[tests-1]<a1.size()||lim[tests-1]<a2.size()||lim[tests-1]<a3.size())continue;
                                    ~~~~~~~~~~~~^~~~~~~~~~
scales.cpp:161:72: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if(lim[tests-1]<a1.size()||lim[tests-1]<a2.size()||lim[tests-1]<a3.size())continue;
                                                            ~~~~~~~~~~~~^~~~~~~~~~
scales.cpp:184:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if(lim[tests-1]<a1.size()||lim[tests-1]<a2.size()||lim[tests-1]<a3.size())continue;
            ~~~~~~~~~~~~^~~~~~~~~~
scales.cpp:184:48: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if(lim[tests-1]<a1.size()||lim[tests-1]<a2.size()||lim[tests-1]<a3.size())continue;
                                    ~~~~~~~~~~~~^~~~~~~~~~
scales.cpp:184:72: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if(lim[tests-1]<a1.size()||lim[tests-1]<a2.size()||lim[tests-1]<a3.size())continue;
                                                            ~~~~~~~~~~~~^~~~~~~~~~
scales.cpp:226:28: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             if(lim[tests-1]<a1.size()||lim[tests-1]<a2.size()||lim[tests-1]<a3.size())continue;
                ~~~~~~~~~~~~^~~~~~~~~~
scales.cpp:226:52: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             if(lim[tests-1]<a1.size()||lim[tests-1]<a2.size()||lim[tests-1]<a3.size())continue;
                                        ~~~~~~~~~~~~^~~~~~~~~~
scales.cpp:226:76: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             if(lim[tests-1]<a1.size()||lim[tests-1]<a2.size()||lim[tests-1]<a3.size())continue;
                                                                ~~~~~~~~~~~~^~~~~~~~~~
scales.cpp: In function 'void init(int)':
scales.cpp:241:15: warning: unused parameter 'T' [-Wunused-parameter]
 void init(int T)
               ^

• Subtask 1: 100 / 100