Submission #133134

#	Time	Username	Problem	Language	Result	Execution time	Memory
133134		ckodser	Scales (IOI15_scales)	C++14	72.02 / 100	42 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-t1;
		    ll k2=w2-t2;
		    ll k3=w3-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))));
		    for(ll d=c+1;d<6;d++){
			ll o[3];
			memset(o,0,sizeof o);
			
			
			for(auto v:halat){
			    o[find4(v,a,b,c,d)]++;
			}
			ll w1=max(o[0],max(o[1],o[2]));
			ll t1=min(o[0],min(o[1],o[2]));
			ll k1=w1-t1;
			ves.pb(mp(k1,mp(mp(a,b),mp(c,d))));

		    }
		}
	    }
	}
	sort(vec.begin(),vec.end());
	sort(vec.begin(),vec.end());
	vector<M> newhalat;

	if(vec[0].F<ves[0].F){
	    pair<pii,pii> w=vec[0].S;
	    ll f[3]={w.F.S,w.S.F,w.S.S};
	    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);
		    }
		}
	    }
	}else{
	    pair<pii,pii> w=ves[0].S;
	    ll f[4]={w.F.F,w.F.S,w.S.F,w.S.S};
	    ll e=get4(f);
	    for(auto v:halat){
	        if(find4(v,f[0],f[1],f[2],f[3])==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) {
               ^
scales.cpp: In function 'void orderCoins()':
scales.cpp:135:7: warning: declaration of 'w1' shadows a previous local [-Wshadow]
    ll w1=max(o[0],max(o[1],o[2]));
       ^~
scales.cpp:112:10: note: shadowed declaration is here
       ll w1=max(low[0],max(low[1],low[2]));
          ^~
scales.cpp:136:7: warning: declaration of 't1' shadows a previous local [-Wshadow]
    ll t1=min(o[0],min(o[1],o[2]));
       ^~
scales.cpp:116:10: note: shadowed declaration is here
       ll t1=min(low[0],min(low[1],low[2]));
          ^~
scales.cpp:137:7: warning: declaration of 'k1' shadows a previous local [-Wshadow]
    ll k1=w1-t1;
       ^~
scales.cpp:120:10: note: shadowed declaration is here
       ll k1=w1-t1;
          ^~

• Subtask 1: 72.02381 / 100