Submission #411267

#	Time	Username	Problem	Language	Result	Execution time	Memory
411267		nxteru	Scales (IOI15_scales)	C++14	71.43 / 100	514 ms	476 KiB

scales

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

void init(int T) {
    /* ... */
}
struct data{
    vector<vector<int>>x;

    vector<vector<int>> addHeaviest(vector<int>a,int p){
        vector<vector<int>>res;
        for(auto v:x){
            bool ok=true;
            for(auto i:a){
                if(v[i]>v[p])ok=false;
            }
            if(ok)res.push_back(v);
        }
        return res;
    }
    vector<vector<int>> addLightest(vector<int>a,int p){
        vector<vector<int>>res;
        for(auto v:x){
            bool ok=true;
            for(auto i:a){
                if(v[i]<v[p])ok=false;
            }
            if(ok)res.push_back(v);
        }
        return res;
    }
    vector<vector<int>> addMedian(vector<int>a,int p){
        vector<vector<int>>res;
        for(auto v:x){
            bool ok=true;
            int ma=-1,mi=10;
            for(auto i:a){
                ma=max(ma,v[i]);
                mi=min(mi,v[i]);
            }
            if(ma==v[p]||mi==v[p])ok=false;
            if(ok)res.push_back(v);
        }
        return res;
    }
    vector<vector<int>> addNext(vector<int>a,int q,int p){
        vector<vector<int>>res;
        for(auto v:x){
            bool ok=true;
            int mi=10,mii=10;
            for(auto i:a){
                mii=min(mii,v[i]);
                if(v[q]<v[i])mi=min(mi,v[i]);
            }
            if(mi==10)mi=mii;
            if(mi!=v[p])ok=false;
            if(ok)res.push_back(v);
        }
        return res;
    }
    vector<int> Next(void){
        int mi=1000;
        vector<int>res;
        vector<int>pp={0,1,2,3,4,5};
        bool vis1[6*6*6],vis2[6*6*6*6];
        for(int i=0;i<6*6*6;i++)vis1[i]=false;
        for(int i=0;i<6*6*6*6;i++)vis2[i]=false;
        do{
            int p[4]={pp[0],pp[1],pp[2],pp[3]};
            sort(p,p+3);
            int s=p[0]+p[1]*6+p[2]*6*6;
            if(!vis1[s]){
                vector<int>a;
                for(int i=0;i<3;i++)a.push_back(p[i]);
                int ma=0;
                for(int i=0;i<3;i++)ma=max(int(addHeaviest(a,a[i]).size()),ma);
                if(ma<mi){
                    mi=ma;
                    res=a;
                    res.push_back(0);
                }

                ma=0;
                for(int i=0;i<3;i++)ma=max(int(addLightest(a,a[i]).size()),ma);
                if(ma<mi){
                    mi=ma;
                    res=a;
                    res.push_back(1);
                }

                ma=0;
                for(int i=0;i<3;i++)ma=max(int(addMedian(a,a[i]).size()),ma);
                if(ma<mi){
                    mi=ma;
                    res=a;
                    res.push_back(2);
                }
                vis1[s]=true;
            }
            s+=p[3]*6*6*6;
            if(!vis2[s]){
                vector<int>a;
                for(int i=0;i<3;i++)a.push_back(p[i]);
                int ma=0;
                for(int i=0;i<3;i++)ma=max(int(addNext(a,p[3],a[i]).size()),ma);
                if(ma<mi){
                    mi=ma;
                    res=a;
                    res.push_back(p[3]);
                    res.push_back(3);
                }
                vis2[s]=true;
            }
        }while(next_permutation(pp.begin(),pp.end()));
        return res;
    }

};

void orderCoins() {
    data d;
    vector<int>p={0,1,2,3,4,5};
    do{
        d.x.push_back(p);
    }while(next_permutation(p.begin(),p.end()));
    while(d.x.size()>1){
        vector<int>q=d.Next();
        if(q.back()==0){
            q.pop_back();
            d.x=d.addHeaviest(q,getHeaviest(q[0]+1,q[1]+1,q[2]+1)-1);
        }else if(q.back()==1){
            q.pop_back();
            d.x=d.addLightest(q,getLightest(q[0]+1,q[1]+1,q[2]+1)-1);
        }else if(q.back()==2){
            q.pop_back();
            d.x=d.addMedian(q,getMedian(q[0]+1,q[1]+1,q[2]+1)-1);
        }else{
            q.pop_back();
            int x=q.back();
            q.pop_back();
            d.x=d.addNext(q,x,getNextLightest(q[0]+1,q[1]+1,q[2]+1,x+1)-1);
        }
    }
    int ans[6];
    for(int i=0;i<6;i++){
        ans[d.x[0][i]]=i+1;
    }
    answer(ans);
}

Compilation message (stderr)

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

• Subtask 1: 71.428571 / 100