Submission #133122

#	Time	Username	Problem	Language	Result	Execution time	Memory
133122		ckodser	Scales (IOI15_scales)	C++14	71.43 / 100	17 ms	504 KiB

scales

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

#define ll int
#define F first
#define S second
#define pb push_back
#define pii pair<ll,ll>
#define mp make_pair

using namespace :: std;


struct M{
    ll a[6];
};
M base;

ll getInd(ll f[],ll e){
    if(e==f[0])return 0;
    if(e==f[1])return 1;
    return 2;
}
ll findLow(M v,ll a,ll b,ll c){
    if(v.a[a]<v.a[b] && v.a[a]<v.a[c])return 0;
    if(v.a[b]<v.a[c])return 1;
    return 2;
}
ll findHigh(M v,ll a,ll b,ll c){
    if(v.a[a]>v.a[b] && v.a[a]>v.a[c])return 0;
    if(v.a[b]>v.a[c])return 1;
    return 2;
}
ll findMid(M v,ll a,ll b,ll c){
    return (findHigh(v,a,b,c)^findLow(v,a,b,c)^3);
}
ll find4(M v,ll a,ll b,ll c,ll d){
    vector<ll> vec;
    ll f[3]={a,b,c};
    if(v.a[a]>v.a[d])vec.pb(a);
    if(v.a[b]>v.a[d])vec.pb(b);
    if(v.a[c]>v.a[d])vec.pb(c);
    if(vec.size()==3 || vec.size()==0){
	return findLow(v,a,b,c);
    }
    if(vec.size()==1){
	return getInd(f,vec[0]);
    }
    if(v.a[vec[0]]<v.a[vec[1]]){
	return getInd(f,vec[0]);
    }
    return getInd(f,vec[1]);
}

ll gethigh(ll f[]){
    ll e=getHeaviest(f[0]+1,f[1]+1,f[2]+1);
    if(e==f[0]+1)return 0;
    if(e==f[1]+1)return 1;
    return 2;
}
ll getlow(ll f[]){
    ll e=getLightest(f[0]+1,f[1]+1,f[2]+1);
    if(e==f[0]+1)return 0;
    if(e==f[1]+1)return 1;
    return 2;
}
ll getmid(ll f[]){
    ll e=getMedian(f[0]+1,f[1]+1,f[2]+1);
    if(e==f[0]+1)return 0;
    if(e==f[1]+1)return 1;
    return 2;
}
ll get4(ll f[]){
    ll e=getNextLightest(f[0]+1,f[1]+1,f[2]+1,f[3]+1);
    if(e==f[0]+1)return 0;
    if(e==f[1]+1)return 1;
    return 2;

}


void init(int T) {
    for(ll i=0;i<6;i++){
	base.a[i]=i;
    }
}
void orderCoins() {
    vector<M> halat;
    M h=base;
    for(ll i=0;i<720;i++){
	halat.pb(h);
	next_permutation(h.a,h.a+6);
    }
    while(halat.size()>1){
	vector<pair<ll,pair<pii,pii> > > vec;
	vector<pair<ll,pair<pii,pii> > > ves;
	for(ll a=0;a<6;a++){
	    for(ll b=a+1;b<6;b++){
		for(ll c=b+1;c<6;c++){
		    ll low[3];
		    ll mid[3];
		    ll high[3];
		    memset(low,0,sizeof low);
		    memset(mid,0,sizeof mid);
		    memset(high,0,sizeof high);
		    
		    for(auto v:halat){
			low[findLow(v,a,b,c)]++;
			mid[findMid(v,a,b,c)]++;
			high[findHigh(v,a,b,c)]++;
		    }
		    ll w1=max(low[0],max(low[1],low[2]));
		    ll w2=max(mid[0],max(mid[1],mid[2]));
		    ll w3=max(high[0],max(high[1],high[2]));
		   
		    ll t1=min(low[0],min(low[1],low[2]));
		    ll t2=min(mid[0],min(mid[1],mid[2]));
		    ll t3=min(high[0],min(high[1],high[2]));
		    
		    ll k1=w1*1000-t1;
		    ll k2=w2*1000-t2;
		    ll k3=w3*1000-t3;

		    vec.pb(mp(k1,mp(mp(1,a),mp(b,c))));
		    vec.pb(mp(k2,mp(mp(2,a),mp(b,c))));
		    vec.pb(mp(k3,mp(mp(3,a),mp(b,c))));
		}
	    }
	}
	sort(vec.begin(),vec.end());
	pair<pii,pii> w=vec[0].S;
	ll f[3]={w.F.S,w.S.F,w.S.S};
	vector<M> newhalat;
	if(w.F.F==1){
	    ll e=getlow(f);
	    for(auto v:halat){
		if(findLow(v,f[0],f[1],f[2])==e){
		    newhalat.pb(v);
		}
	    }
	}
	if(w.F.F==2){
	    ll e=getmid(f);
	    for(auto v:halat){
		if(findMid(v,f[0],f[1],f[2])==e){
		    newhalat.pb(v);
		}
	    }
	}
	if(w.F.F==3){
	    ll e=gethigh(f);
	    for(auto v:halat){
		if(findHigh(v,f[0],f[1],f[2])==e){
		    newhalat.pb(v);
		}
	    }
	}
	halat=newhalat;
    }
    ll t[6];
    for(ll i=0;i<6;i++){
	t[halat.back().a[i]]=i+1;
    }
    answer(t);
}

Compilation message (stderr)

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

• Subtask 1: 71.428571 / 100