Submission #1259930

#	Time	Username	Problem	Language	Result	Execution time	Memory
1259930		erering	Scales (IOI15_scales)	C++20	0 / 100	645 ms	589824 KiB

scales

#include <bits/stdc++.h>
#include "scales.h"
using namespace std;
#define pb push_back
vector<vector<int>> all;
void init(int T) {
    vector<int> vec={1,2,3,4,5,6};
    do{
        all.pb(vec);
    }
    while(next_permutation(vec.begin(),vec.end()));
}
vector<int> sol(vector<vector<int>> vecs){
    if(vecs.size()==1)return vecs[0];
    int mn=1e9,type;
    vector<int> ask;
    for(int a=1;a<=6;a++){
        for(int b=a+1;b<=6;b++){
            for(int c=b+1;c<=6;c++){
                //if i ask lightest
                vector<vector<int>> v[3];
                for(auto i:vecs){
                    int posa,posb,posc;
                    for(int j=0;j<6;j++){
                        if(i[j]==a)posa=j;
                        if(i[j]==b)posb=j;
                        if(i[j]==c)posc=j;
                    }
                    int m=min({posa,posb,posc});
                    if(posa==m)v[0].pb(i);
                    else if(posb==m)v[1].pb(i);
                    else v[2].pb(i);
                }
                if(max({v[0].size(),v[1].size(),v[2].size()})<mn){
                    mn=max({v[0].size(),v[1].size(),v[2].size()});
                    ask={a,b,c}; type=0;
                }
                //if i ask max
                v[0].clear(); v[1].clear(); v[2].clear();
                for(auto i:vecs){
                    int posa,posb,posc;
                    for(int j=0;j<6;j++){
                        if(i[j]==a)posa=j;
                        if(i[j]==b)posb=j;
                        if(i[j]==c)posc=j;
                    }
                    int m=max({posa,posb,posc});
                    if(posa==m)v[0].pb(i);
                    else if(posb==m)v[1].pb(i);
                    else v[2].pb(i);
                }
                if(max({v[0].size(),v[1].size(),v[2].size()})<mn){
                    mn=max({v[0].size(),v[1].size(),v[2].size()});
                    ask={a,b,c}; type=1;
                }
                //if i ask median
                v[0].clear(); v[1].clear(); v[2].clear();
                for(auto i:vecs){
                    int posa,posb,posc;
                    for(int j=0;j<6;j++){
                        if(i[j]==a)posa=j;
                        if(i[j]==b)posb=j;
                        if(i[j]==c)posc=j;
                    }
                    int arr[3]={posa,posb,posc};
                    sort(arr,arr+3);
                    int m=arr[1];
                    if(posa==m)v[0].pb(i);
                    else if(posb==m)v[1].pb(i);
                    else v[2].pb(i);
                }
                if(max({v[0].size(),v[1].size(),v[2].size()})<mn){
                    mn=max({v[0].size(),v[1].size(),v[2].size()});
                    ask={a,b,c}; type=2;
                }
                for(int k=c+1;k<=6;k++){
                    //if i ask nextheaviest
                    v[0].clear(); v[1].clear(); v[2].clear();
                    for(auto i:vecs){
                        int posa,posb,posc,posk;
                        for(int j=0;j<6;j++){
                            if(i[j]==a)posa=j;
                            if(i[j]==b)posb=j;
                            if(i[j]==c)posc=j;
                            if(i[j]==k)posk=j;
                        }
                        int arr[3]={posa,posb,posc};
                        sort(arr,arr+3);
                        if(posc<posk || posk<posa)v[0].pb(i);
                        if(posk<posb)v[1].pb(i);
                        if(posk<posc)v[2].pb(i);
                    }
                    if(max({v[0].size(),v[1].size(),v[2].size()})<mn){
                        mn=max({v[0].size(),v[1].size(),v[2].size()});
                        ask={a,b,c,k}; type=3;
                    }
                }
            }
        }
    }
   // cout<<type<<' '<<vecs.size()<<endl;
    vector<vector<int>> v;
    if(type==0){
        int x=getLightest(ask[0],ask[1],ask[2]);
       // cout<<ask[0]<<" "<<ask[1]<<" "<<ask[2]<<" "<<x<<endl;
        for(auto i:vecs){
            int posa,posb,posc;
            for(int j=0;j<6;j++){
                if(i[j]==ask[0])posa=j;
                if(i[j]==ask[1])posb=j;
                if(i[j]==ask[2])posc=j;
            }
            int m=min({posa,posb,posc});
            if(posa==m && x==ask[0])v.pb(i);
            else if(posb==m && x==ask[1])v.pb(i);
            else if(posc==m && x==ask[2])v.pb(i);
        }
    }
   // cout<<v.size()<<endl;
   // exit(0);
    if(type==1){
        int x=getHeaviest(ask[0],ask[1],ask[2]);
        for(auto i:vecs){
            int posa,posb,posc;
            for(int j=0;j<6;j++){
                if(i[j]==ask[0])posa=j;
                if(i[j]==ask[1])posb=j;
                if(i[j]==ask[2])posc=j;
            }
            int m=max({posa,posb,posc});
            if(posa==m && x==ask[0])v.pb(i);
            else if(posb==m && x==ask[1])v.pb(i);
            else if(posc==m && x==ask[2])v.pb(i);
        }
    }

    if(type==2){
        int x=getMedian(ask[0],ask[1],ask[2]);
        for(auto i:vecs){
            int posa,posb,posc;
            for(int j=0;j<6;j++){
                if(i[j]==ask[0])posa=j;
                if(i[j]==ask[1])posb=j;
                if(i[j]==ask[2])posc=j;
            }
            int arr[3]={posa,posb,posc};
            sort(arr,arr+3);
            int m=arr[1];
            if(posa==m && x==ask[0])v.pb(i);
            else if(posb==m && x==ask[1])v.pb(i);
            else if(posc==m && x==ask[2])v.pb(i);
        }
    }

    if(type==3){
        int x=getNextLightest(ask[0],ask[1],ask[2],ask[3]);
        for(auto i:vecs){
            int posa,posb,posc,posk;
            for(int j=0;j<6;j++){
                if(i[j]==ask[0])posa=j;
                if(i[j]==ask[1])posb=j;
                if(i[j]==ask[2])posc=j;
                if(i[j]==ask[3])posk=j;
            }
            int arr[3]={posa,posb,posc};
            sort(arr,arr+3);
            if(ask[0]==x && (posc<posk || posk<posa))v.pb(i);
            if(ask[1]==x && posk<posb)v.pb(i);
            if(ask[2]==x && posk<posc)v.pb(i);
        }
    }
    return sol(v);
}
void orderCoins() {
    /* ... */
    int W[] = {1, 2, 3, 4, 5, 6};
    vector<int> vec=sol(all);
    for(int i=0;i<6;i++){
        W[i]=vec[i];
       // cout<<W[i]<<' ';
    }
   // cout<<endl;
    answer(W);
}
//3 4 6 2 1 5

• Subtask 1: 0 / 100