Submission #588620

#	Time	Username	Problem	Language	Result	Execution time	Memory
588620		sofapuden	Scales (IOI15_scales)	C++14	100 / 100	498 ms	512 KiB

scales

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

using namespace std;

struct node {
	int a, b, c, d, t;
	node () {}
	node (int _a, int _b, int _c, int _d, int _t) : a(_a), b(_b), c(_c), d(_d), t(_t) {}
	node (int _a, int _b, int _c, int _t) :	node(_a,_b,_c,0,_t) {}
};

vector<vector<int>> perm;
vector<node> Q;

int med(int a, int b, int c){
	if(a != max({a,b,c}) && a != min({a,b,c}))return a;
	if(b != max({a,b,c}) && b != min({a,b,c}))return b;
	if(c != max({a,b,c}) && c != min({a,b,c}))return c;
	return 0;
}

int nxl(int a, int b, int c, int d){
	vector<int> cu;
	cu.push_back(a);
	cu.push_back(b);
	cu.push_back(c);
	cu.push_back(d);
	sort(cu.begin(),cu.end());
	for(int i = 0; i < 4; ++i)
		if(cu[i] == d)return cu[(i+1)%4];
	return 0;
}

void init(int T) {
	if(!T){
		return;
	}
	vector<int> ini = {0,1,2,3,4,5};
	do {
		perm.push_back(ini);
	}while(next_permutation(ini.begin(),ini.end()));

	for(int i = 0; i < 6; ++i){
		for(int j = i+1; j < 6; ++j){
			for(int k = j+1; k < 6; ++k){
				Q.push_back(node(i,j,k,0));
				Q.push_back(node(i,j,k,1));
				Q.push_back(node(i,j,k,2));
			}
		}
	}
	for(int z = 0; z < 6; ++z){
		for(int i = 0; i < 6; ++i){
			for(int j = i+1; j < 6; ++j){
				for(int k = j+1; k < 6; ++k){
					if(z == i || z == j || z == k)continue;
					Q.push_back(node(i,j,k,z,3));
				}
			}
		}
	}
    /* ... */
}

void orderCoins() {
	vector<vector<int>> curperm = perm;
	while(curperm.size() > 1){
		int bes = 1000;
		node que(0,0,0,0);
		for(auto x : Q){
			if(x.t == 0){
				int A = 0, B = 0, C = 0;
				for(auto y : curperm){
					if(y[x.a] == max({y[x.a],y[x.b],y[x.c]}))A++;
					if(y[x.b] == max({y[x.a],y[x.b],y[x.c]}))B++;
					if(y[x.c] == max({y[x.a],y[x.b],y[x.c]}))C++;
				}
				A = max({A,B,C});
				if(A <= bes){
					bes = A;
					que = x;
				}
			}
			else if(x.t == 1){
				int A = 0, B = 0, C = 0;
				for(auto y : curperm){
					if(y[x.a] == min({y[x.a],y[x.b],y[x.c]}))A++;
					if(y[x.b] == min({y[x.a],y[x.b],y[x.c]}))B++;
					if(y[x.c] == min({y[x.a],y[x.b],y[x.c]}))C++;
				}
				A = max({A,B,C});
				if(A <= bes){
					bes = A;
					que = x;
				}

			}
			else if(x.t == 2){
				int A = 0, B = 0, C = 0;
				for(auto y : curperm){
					if(y[x.a] == med(y[x.a],y[x.b],y[x.c]))A++;
					if(y[x.b] == med(y[x.a],y[x.b],y[x.c]))B++;
					if(y[x.c] == med(y[x.a],y[x.b],y[x.c]))C++;
				}
				A = max({A,B,C});
				if(A <= bes){
					bes = A;
					que = x;
				}
			}
			else if(x.t == 3){
				int A = 0, B = 0, C = 0;
				for(auto y : curperm){
					if(y[x.a] == nxl(y[x.a],y[x.b],y[x.c],y[x.d]))A++;
					if(y[x.b] == nxl(y[x.a],y[x.b],y[x.c],y[x.d]))B++;
					if(y[x.c] == nxl(y[x.a],y[x.b],y[x.c],y[x.d]))C++;
				}
				A = max({A,B,C});
				if(A <= bes){
					bes = A;
					que = x;
				}
			}
		}
		vector<vector<int>> nP;
		if(que.t == 0){
			int k = getHeaviest(que.a+1,que.b+1,que.c+1)-1;
			for(auto y : curperm){
				if(y[k] == max({y[que.a],y[que.b],y[que.c]}))nP.push_back(y);
			}
		}
		else if(que.t == 1){
			int k = getLightest(que.a+1,que.b+1,que.c+1)-1;
			for(auto y : curperm){
				if(y[k] == min({y[que.a],y[que.b],y[que.c]}))nP.push_back(y);
			}
		}
		else if(que.t == 2){
			int k = getMedian(que.a+1,que.b+1,que.c+1)-1;
			for(auto y : curperm){
				if(y[k] == med(y[que.a],y[que.b],y[que.c]))nP.push_back(y);
			}
		}
		else if(que.t == 3){
			int k = getNextLightest(que.a+1,que.b+1,que.c+1,que.d+1) - 1;
			for(auto y : curperm){
				if(y[k] == nxl(y[que.a],y[que.b],y[que.c],y[que.d]))nP.push_back(y);
			}
		}
		swap(nP,curperm);
	}
    /* ... */

	int w[6];
	for(int i = 0; i < 6; ++i){
		w[curperm[0][i]] = i+1;
	}
    answer(w);
}

• Subtask 1: 100 / 100