제출 #133174

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
133174		MAMBA	저울 (IOI15_scales)	C++17	0 / 100	1092 ms	12920 KiB

scales

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

// getheaviest
// getLightest
// getMedian
// getNextLightest

using namespace std;

#define rep(i , j , k) for(int i = j; i < (int)k; i++)
#define pb push_back

typedef array<int , 6> ar;
typedef vector<int> vi;

struct dt {
	int n = 1e9;
	int nxt = -1;
	int A = -1, B = -1, C = -1, D = -1;
	dt() {}
	dt(int N , int Nxt , int a , int b, int c , int d = -1) {
		n = N, nxt = Nxt , A = a, B = b, C = c, D = d;
	}
};


ar per[720];


inline void R0(vi &v , int A , int B , int C, int R) {
	vi res;
	for (auto e : v)
		if (max({per[e][A] , per[e][B] , per[e][C]}) <= per[e][R])
			res.pb(e);
	v = res;
}

inline void R1(vi &v , int A , int B , int C, int R) {
	vi res;
	for (auto e : v)
		if (min({per[e][A] , per[e][B] , per[e][C]}) >= per[e][R])
			res.pb(e);
	v = res;
}

inline void R2(vi &v , int A , int B , int C, int R) {
	vi res;
	for (auto e : v)
		if (min({per[e][A] , per[e][B] , per[e][C]}) < per[e][R] &&
				max({per[e][A] , per[e][B] , per[e][C]}) > per[e][R])
			res.pb(e);
	v = res;
}

inline void R3(vi &v , int A , int B , int C, int D, int R) {
	vi res;
	for (auto e : v) {
		if (max({per[e][A] , per[e][B] , per[e][C]}) < per[e][D]) {
			if (min({per[e][A] , per[e][B] , per[e][C]}) == per[e][R])
				res.pb(e);
		}
		else {
			bool flag = false;
			if (per[e][A] > per[e][D] && per[e][A] < per[e][R]) flag = true;
			if (per[e][B] > per[e][D] && per[e][B] < per[e][R]) flag = true;
			if (per[e][C] > per[e][D] && per[e][C] < per[e][R]) flag = true;
			if (!flag)
				res.pb(e);
		}
	}
	v = res;
}

bool ok[4] = {1 , 0 , 1 , 0};

map<vi , int> last_try;
map<vi , dt> mp;


bool dfs(vi me, int exp = 1e9) {

	if (last_try.count(me) && last_try[me] >= exp)
		return false;

	int cnt = 0;
	int ww = 1;
	while (ww < me.size()) {
		ww *= 3;
		cnt++;
	}

	if (cnt > exp) {
		last_try[me] = exp;
		return false;
	}


	if (me.size() == 1) {
		mp[me] = dt(0 , -1 , -1, -1, -1);
		return true;
	}

	dt ans(exp + 1 , -1 , -1 , -1, -1);
	if (ok[0]) {// 0
		rep(i , 0 , 6)
			rep(j , i + 1 , 6)
			rep(k , j + 1 , 6) {
				vi a = me;
				vi b = me;
				vi c = me;
				R0(a , i , j , k , i);
				R0(b , i , j , k , j);
				R0(c , i , j , k , k);

				int wor = -10;

				if (max({a.size() , b.size() , c.size()}) == me.size()) continue;

				if (mp.count(a)) wor = max(wor , mp[a].n);
				if (mp.count(b)) wor = max(wor , mp[b].n);
				if (mp.count(c)) wor = max(wor , mp[c].n);

				if (wor + 1 < ans.n && !mp.count(a)) {
					if (dfs(a , ans.n - 2))
						wor = max(wor , mp[a].n);
					else 
						wor = 1e9;
				}
				if (wor + 1 < ans.n && !mp.count(b)) {
					if (dfs(b , ans.n - 2))
						wor = max(wor , mp[b].n);
					else 
						wor = 1e9;
				}
				if (wor + 1 < ans.n && !mp.count(c)) {
					if (dfs(c , ans.n - 2))
						wor = max(wor , mp[c].n);
					else 
						wor = 1e9;
				}


				if (wor + 1 < ans.n) 
					ans = dt(wor + 1 , 0 , i , j , k);
			}
	}
	if (ok[1]) {// 1
		rep(i , 0 , 6)
			rep(j , i + 1 , 6)
			rep(k , j + 1 , 6) {
				vi a = me;
				vi b = me;
				vi c = me;
				R1(a , i , j , k , i);
				R1(b , i , j , k , j);
				R1(c , i , j , k , k);
				int wor = -10;

				if (max({a.size() , b.size() , c.size()}) == me.size()) continue;

				if (mp.count(a)) wor = max(wor , mp[a].n);
				if (mp.count(b)) wor = max(wor , mp[b].n);
				if (mp.count(c)) wor = max(wor , mp[c].n);

				if (wor + 1 < ans.n && !mp.count(a)) {
					if (dfs(a , ans.n - 2))
						wor = max(wor , mp[a].n);
					else 
						wor = 1e9;
				}
				if (wor + 1 < ans.n && !mp.count(b)) {
					if (dfs(b , ans.n - 2))
						wor = max(wor , mp[b].n);
					else 
						wor = 1e9;
				}
				if (wor + 1 < ans.n && !mp.count(c)) {
					if (dfs(c , ans.n - 2))
						wor = max(wor , mp[c].n);
					else 
						wor = 1e9;
				}


				if (wor + 1 < ans.n) 
					ans = dt(wor + 1 , 1 , i , j , k);

			}

	}
	if (ok[2]) {// 2
		rep(i , 0 , 6)
			rep(j , i + 1 , 6)
			rep(k , j + 1 , 6) {
				vi a = me;
				vi b = me;
				vi c = me;
				R2(a , i , j , k , i);
				R2(b , i , j , k , j);
				R2(c , i , j , k , k);
				int wor = -10;

				if (max({a.size() , b.size() , c.size()}) == me.size()) continue;

				if (mp.count(a)) wor = max(wor , mp[a].n);
				if (mp.count(b)) wor = max(wor , mp[b].n);
				if (mp.count(c)) wor = max(wor , mp[c].n);

				if (wor + 1 < ans.n && !mp.count(a)) {
					if (dfs(a , ans.n - 2))
						wor = max(wor , mp[a].n);
					else 
						wor = 1e9;
				}
				if (wor + 1 < ans.n && !mp.count(b)) {
					if (dfs(b , ans.n - 2))
						wor = max(wor , mp[b].n);
					else 
						wor = 1e9;
				}
				if (wor + 1 < ans.n && !mp.count(c)) {
					if (dfs(c , ans.n - 2))
						wor = max(wor , mp[c].n);
					else 
						wor = 1e9;
				}


				if (wor + 1 < ans.n) 
					ans = dt(wor + 1 , 2 , i , j , k);

			}

	}
	if (ok[3]) {// 3
		rep(i , 0 , 6)
			rep(j , i + 1 , 6)
			rep(k , j + 1 , 6) 
			rep(z , k + 1, 6) {
				vi a = me;
				vi b = me;
				vi c = me;
				R3(a , i , j , k , z , i);
				R3(b , i , j , k , z , j);
				R3(c , i , j , k , z , k);

				int wor = -10;

				if (max({a.size() , b.size() , c.size()}) == me.size()) continue;

				if (mp.count(a)) wor = max(wor , mp[a].n);
				if (mp.count(b)) wor = max(wor , mp[b].n);
				if (mp.count(c)) wor = max(wor , mp[c].n);

				if (wor + 1 < ans.n && !mp.count(a)) {
					if (dfs(a , ans.n - 2))
						wor = max(wor , mp[a].n);
					else 
						wor = 1e9;
				}
				if (wor + 1 < ans.n && !mp.count(b)) {
					if (dfs(b , ans.n - 2))
						wor = max(wor , mp[b].n);
					else 
						wor = 1e9;
				}
				if (wor + 1 < ans.n && !mp.count(c)) {
					if (dfs(c , ans.n - 2))
						wor = max(wor , mp[c].n);
					else 
						wor = 1e9;
				}


				if (wor + 1 < ans.n) 
					ans = dt(wor + 1 , 3 , i , j , k, z);

			}

	}


	if (ans.nxt == -1) {
		last_try[me] = exp;
		return false;
	}
	mp[me] = ans;
	return true;

}

void init(int T) {


	mp.clear();
	mp[vi()] = dt(0 , -1 , -1 , -1, -1);

	ar tmp = {0 , 1 , 2 , 3 , 4, 5};
	rep(i , 0 , 720) {
		per[i] = tmp;
		next_permutation(tmp.begin(), tmp.end());
	}

	vi st(720);
	iota(st.begin(), st.end()  , 0);


	dfs(st);


}

void orderCoins() {

	vi st(720);
	iota(st.begin(), st.end()  , 0);

	while (st.size() > 1) {
		dt me = mp[st];
		int tp = me.nxt;


		assert(~tp);

		if (tp == 0) {
			int res = getHeaviest(me.A + 1 , me.B + 1 , me.C + 1) - 1;
			R0(st , me.A , me.B , me.C , res);
		}
		if (tp == 1) {
			int res = getLightest(me.A + 1, me.B + 1 , me.C + 1) - 1;
			R1(st , me.A , me.B , me.C , res);
		}
		if (tp == 2) {
			int res = getMedian(me.A + 1 , me.B + 1 , me.C + 1) - 1;
			R2(st , me.A , me.B , me.C , res);
		}
		if (tp == 3) {
			int res = getNextLightest(me.A + 1, me.B + 1 , me.C + 1, me.D + 1) - 1;
			R3(st , me.A , me.B , me.C , me.D , res);
		}

	}

	assert(0);
	int w[6];
	rep(i , 0 , 6)
		w[per[st[0]][i]] = i + 1;
	answer(w);

}

컴파일 시 표준 에러 (stderr) 메시지

scales.cpp: In function 'bool dfs(vi, int)':
scales.cpp:88:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while (ww < me.size()) {
         ~~~^~~~~~~~~~~
scales.cpp: In function 'void init(int)':
scales.cpp:293:15: warning: unused parameter 'T' [-Wunused-parameter]
 void init(int T) {
               ^

• Subtask 1: 0 / 100