Submission #133105

#	Time	Username	Problem	Language	Result	Execution time	Memory
133105		ckodser	Scales (IOI15_scales)	C++14	71.43 / 100	17 ms	424 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 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 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;
}



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);
    }
 //   cout<<"VN"<<endl;
    while(halat.size()>1){
//	cout<<halat.size()<<endl;
	vector<pair<ll,pair<pii,pii> > > vec;
	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]));
		    vec.pb(mp(w1,mp(mp(1,a),mp(b,c))));
		    vec.pb(mp(w2,mp(mp(2,a),mp(b,c))));
		    vec.pb(mp(w3,mp(mp(3,a),mp(b,c))));
		}
	    }
	}
	sort(vec.begin(),vec.end());
	reverse(vec.begin(),vec.end());
	pair<pii,pii> w=vec.back().S;
	ll f[3]={w.F.S,w.S.F,w.S.S};
	vector<M> newhalat;
//	cout<<w.F.F<<':'<<f[0]<<' '<<f[1]<<' '<<f[2]<<endl;
	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:54:15: warning: unused parameter 'T' [-Wunused-parameter]
 void init(int T) {
               ^

• Subtask 1: 71.428571 / 100