Submission #606305

#	Time	Username	Problem	Language	Result	Execution time	Memory
606305		Koosha_mv	Scales (IOI15_scales)	C++14	71.43 / 100	694 ms	620 KiB

scales

#include "scales.h"
#include <bits/stdc++.h>
using namespace std;
#define dbgv(v) cout<<#v<<" = "; f(i,0,int(v.size())) cout<<v[i]<<" "; cout<<endl
#define dbga(a,x,y) cout<<#a<<" = "; f(i,x,y) cout<<a[i]<<" "; cout<<endl
#define erorp(x) cout<<#x<<"={"<<x.F<<" , "<<x.S<<"}"<<endl
#define eror(x) cout<<#x<<'='<<(x)<<endl
#define f_(i,a,b) for(int i=a;i>=b;i--)
#define f(i,a,b) for(int i=a;i<b;i++)
#define nb(x) __builtin_popcount(x)
#define all(v) v.begin(),v.end()
#define bit(n,k) (((n)>>(k))&1)
#define Add(x,y) x=(x+y)%mod
#define maxm(a,b) a=max(a,b)
#define minm(a,b) a=min(a,b)
#define lst(x) x[x.size()-1]
#define sz(x) int(x.size())
#define mp make_pair
#define ll long long
#define pb push_back
#define S second
#define F first

const int N=10;

int n=6,cnt[N];
vector<vector<int>> op,vc;

int Max(){
    int mx=0;
    f(i,0,N) maxm(mx,cnt[i]);
    return mx;
}
int getLightest(int A, int B, int C,vector<int> vec){
    int ted=0;
    for(auto x : vec){
        int id=-1;
        if(x==A){
            id=A;
        }
        if(x==B){
            id=B;
        }
        if(x==C){
            id=C;
        }
        if(id!=-1){
            ted++;
            if(ted==1) return id;
        }
    }
    return 0;
}
int getMedian(int A, int B, int C,vector<int> vec){
    vector<pair<int,int>> p;
    int ted=0;
    for(auto x : vec){
        int id=-1;
        if(x==A){
            id=A;
        }
        if(x==B){
            id=B;
        }
        if(x==C){
            id=C;
        }
        if(id!=-1){
            ted++;
            if(ted==2) return id;
        }
    }
    return 0;
}
int getHeaviest(int A, int B, int C,vector<int> vec){
    vector<pair<int,int>> p;
    int ted=0;
    for(auto x : vec){
        int id=-1;
        if(x==A){
            id=A;
        }
        if(x==B){
            id=B;
        }
        if(x==C){
            id=C;
        }
        if(id!=-1){
            ted++;
            if(ted==3) return id;
        }
    }
    return 0;
}
int getNextLightest(int A, int B, int C, int D,vector<int> vec){
    int b=0;
    for(auto x : vec){
        if(x==D) b=1;
        if(b==1 && (x==A || x==B || x==C)){
            return x;
        }
    }
    for(auto x : vec){
        if(b==1 && (x==A || x==B || x==C)){
            return x;
        }
    }
    return 0;
}
void do_it(){
    int res=int(vc.size());
    for(auto p : op){
        fill(cnt,cnt+N,0);
        for(auto v : vc){
            cnt[getLightest(p[0],p[1],p[2],v)]++;
        }
        minm(res,Max());
    }
    for(auto p : op){
        fill(cnt,cnt+N,0);
        for(auto v : vc){
            cnt[getMedian(p[0],p[1],p[2],v)]++;
        }
        minm(res,Max());
    }
    for(auto p : op){
        fill(cnt,cnt+N,0);
        for(auto v : vc){
            cnt[getHeaviest(p[0],p[1],p[2],v)]++;
        }
        minm(res,Max());
    }
    /*
    for(auto p : op){
        f(x,1,n+1){
            if(x==p[0] || x==p[1] || x==p[2]) continue ;
            for(auto v : vc){
                getNextLightest(p[0],p[1],p[2],x,v);
            } 
        }
    }*/
    for(auto p : op){
        fill(cnt,cnt+N,0);
        for(auto v : vc){
            cnt[getLightest(p[0],p[1],p[2],v)]++;
        }
        if(res==Max()){
            vector<vector<int>> nvc;
            int id=getLightest(p[0],p[1],p[2]);
            for(auto v : vc){
                if(getLightest(p[0],p[1],p[2],v)==id){
                    nvc.pb(v);
                }
            }   
            vc=nvc;
            return ;
        }
    }
    for(auto p : op){
        fill(cnt,cnt+N,0);
        for(auto v : vc){
            cnt[getMedian(p[0],p[1],p[2],v)]++;
        }
        if(res==Max()){
            vector<vector<int>> nvc;
            int id=getMedian(p[0],p[1],p[2]);
            for(auto v : vc){
                if(getMedian(p[0],p[1],p[2],v)==id){
                    nvc.pb(v);
                }
            }
            vc=nvc;   
            return ;
        }
    }
    for(auto p : op){
        fill(cnt,cnt+N,0);
        for(auto v : vc){
            cnt[getHeaviest(p[0],p[1],p[2],v)]++;
        }
        if(res==Max()){
            vector<vector<int>> nvc;
            int id=getHeaviest(p[0],p[1],p[2]);
            for(auto v : vc){
                if(getHeaviest(p[0],p[1],p[2],v)==id){
                    nvc.pb(v);
                }
            }   
            vc=nvc;
            return ;
        }
    }
}
void orderCoins() {
    vector<int> p(n);   
    iota(all(p),1);
    do{
        vc.pb(p);
    } while(next_permutation(all(p)));
    f(i,0,n) p[i]=(i>=3);
    do{
        vector<int> v;
        f(i,0,n) if(p[i]==1) v.pb(i+1);
        op.pb(v);
    } while(next_permutation(all(p)));

    ////
    //vc.clear();
    //vc.pb({3,4,6,2,1,5});
    //vc.pb({3,4,6,2,5,1});
    ///

    while(vc.size()>1){
        //cout<<"size "<<vc.size()<<endl;
        /*if(vc.size()==2){
            for(auto v : vc){
                dbgv(v);
            }
            //break ;
        }*/
        do_it();
    }
    //eror(vc.size());
    //cout<<"ans -> ";
    //for(auto x : vc[0]) cout<<x<<" ";
    //cout<<endl;
    int W[6];
    f(i,0,6) W[i]=vc[0][i];
    answer(W);
}
void init(int T) {
    T=T;
}

/*int getMedian(int A, int B, int C);
int getHeaviest(int A, int B, int C);
int getLightest(int A, int B, int C);
int getNextLightest(int A, int B, int C, int D);
*/

• Subtask 1: 71.428571 / 100