답안 #133127

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
133127	2019-07-20T07:47:50 Z	ckodser	저울 (IOI15_scales)	C++14	72.3214 / 100	43 ms	504 KB

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))));
		    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*1000-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

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*1000-t1;
       ^~
scales.cpp:120:10: note: shadowed declaration is here
       ll k1=w1*1000-t1;
          ^~

Subtask #1

72.321429 / 100.0

#	결과	실행 시간	메모리	Grader output
1	Partially correct	41 ms	504 KB	Output is partially correct
2	Partially correct	40 ms	400 KB	Output is partially correct
3	Partially correct	40 ms	376 KB	Output is partially correct
4	Partially correct	40 ms	376 KB	Output is partially correct
5	Partially correct	40 ms	376 KB	Output is partially correct
6	Partially correct	40 ms	376 KB	Output is partially correct
7	Correct	40 ms	376 KB	Output is correct
8	Partially correct	40 ms	376 KB	Output is partially correct
9	Correct	40 ms	376 KB	Output is correct
10	Partially correct	41 ms	376 KB	Output is partially correct
11	Partially correct	40 ms	376 KB	Output is partially correct
12	Partially correct	40 ms	504 KB	Output is partially correct
13	Partially correct	40 ms	376 KB	Output is partially correct
14	Correct	41 ms	376 KB	Output is correct
15	Partially correct	40 ms	376 KB	Output is partially correct
16	Partially correct	40 ms	376 KB	Output is partially correct
17	Partially correct	40 ms	504 KB	Output is partially correct
18	Partially correct	40 ms	400 KB	Output is partially correct
19	Partially correct	41 ms	376 KB	Output is partially correct
20	Partially correct	41 ms	504 KB	Output is partially correct
21	Partially correct	40 ms	376 KB	Output is partially correct
22	Partially correct	40 ms	380 KB	Output is partially correct
23	Partially correct	41 ms	436 KB	Output is partially correct
24	Partially correct	40 ms	400 KB	Output is partially correct
25	Partially correct	40 ms	376 KB	Output is partially correct
26	Partially correct	40 ms	376 KB	Output is partially correct
27	Partially correct	40 ms	376 KB	Output is partially correct
28	Partially correct	41 ms	376 KB	Output is partially correct
29	Partially correct	40 ms	376 KB	Output is partially correct
30	Partially correct	40 ms	376 KB	Output is partially correct
31	Partially correct	40 ms	376 KB	Output is partially correct
32	Partially correct	40 ms	376 KB	Output is partially correct
33	Partially correct	40 ms	376 KB	Output is partially correct
34	Partially correct	40 ms	376 KB	Output is partially correct
35	Partially correct	40 ms	504 KB	Output is partially correct
36	Partially correct	43 ms	376 KB	Output is partially correct
37	Partially correct	40 ms	376 KB	Output is partially correct
38	Partially correct	41 ms	404 KB	Output is partially correct
39	Partially correct	40 ms	376 KB	Output is partially correct
40	Partially correct	40 ms	376 KB	Output is partially correct