# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
133134 |
2019-07-20T07:54:12 Z |
ckodser |
Scales (IOI15_scales) |
C++14 |
|
42 ms |
504 KB |
#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
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;
^~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Partially correct |
39 ms |
504 KB |
Output is partially correct |
2 |
Partially correct |
40 ms |
376 KB |
Output is partially correct |
3 |
Partially correct |
40 ms |
376 KB |
Output is partially correct |
4 |
Partially correct |
39 ms |
380 KB |
Output is partially correct |
5 |
Partially correct |
40 ms |
376 KB |
Output is partially correct |
6 |
Partially correct |
41 ms |
376 KB |
Output is partially correct |
7 |
Partially correct |
39 ms |
376 KB |
Output is partially correct |
8 |
Partially correct |
40 ms |
504 KB |
Output is partially correct |
9 |
Partially correct |
41 ms |
504 KB |
Output is partially correct |
10 |
Partially correct |
42 ms |
376 KB |
Output is partially correct |
11 |
Partially correct |
39 ms |
412 KB |
Output is partially correct |
12 |
Partially correct |
40 ms |
400 KB |
Output is partially correct |
13 |
Partially correct |
40 ms |
376 KB |
Output is partially correct |
14 |
Correct |
42 ms |
376 KB |
Output is correct |
15 |
Partially correct |
42 ms |
376 KB |
Output is partially correct |
16 |
Correct |
41 ms |
412 KB |
Output is correct |
17 |
Partially correct |
41 ms |
376 KB |
Output is partially correct |
18 |
Partially correct |
39 ms |
440 KB |
Output is partially correct |
19 |
Partially correct |
41 ms |
376 KB |
Output is partially correct |
20 |
Partially correct |
40 ms |
376 KB |
Output is partially correct |
21 |
Partially correct |
40 ms |
376 KB |
Output is partially correct |
22 |
Partially correct |
40 ms |
376 KB |
Output is partially correct |
23 |
Partially correct |
40 ms |
376 KB |
Output is partially correct |
24 |
Partially correct |
40 ms |
380 KB |
Output is partially correct |
25 |
Partially correct |
40 ms |
504 KB |
Output is partially correct |
26 |
Partially correct |
41 ms |
376 KB |
Output is partially correct |
27 |
Partially correct |
40 ms |
376 KB |
Output is partially correct |
28 |
Partially correct |
40 ms |
376 KB |
Output is partially correct |
29 |
Partially correct |
42 ms |
376 KB |
Output is partially correct |
30 |
Partially correct |
39 ms |
376 KB |
Output is partially correct |
31 |
Partially correct |
39 ms |
436 KB |
Output is partially correct |
32 |
Partially correct |
40 ms |
436 KB |
Output is partially correct |
33 |
Partially correct |
41 ms |
376 KB |
Output is partially correct |
34 |
Partially correct |
40 ms |
376 KB |
Output is partially correct |
35 |
Partially correct |
39 ms |
376 KB |
Output is partially correct |
36 |
Partially correct |
39 ms |
440 KB |
Output is partially correct |
37 |
Partially correct |
39 ms |
392 KB |
Output is partially correct |
38 |
Partially correct |
39 ms |
376 KB |
Output is partially correct |
39 |
Partially correct |
39 ms |
376 KB |
Output is partially correct |
40 |
Partially correct |
40 ms |
376 KB |
Output is partially correct |