Submission #133221

#	Time	Username	Problem	Language	Result	Execution time	Memory
133221		MAMBA	Scales (IOI15_scales)	C++17	71.43 / 100	48 ms	764 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 , 1 , 1 , 1};

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

long long getHash(vi v) {
	long long res = 0;
	long long mod = 1e9 + 7;
	for (auto e : v)
		res = (res * mod + e + 1);
	return res;
}

bool dfs(vi me, int exp = 7) {

	long long hh = getHash(me);

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

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

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


	if (me.size() == 1) {
		mp[hh] = 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;

				long long aa = getHash(a);
				long long bb = getHash(b);
				long long cc = getHash(c);

				if (mp.count(aa)) wor = max(wor , mp[aa].n);
				if (mp.count(bb)) wor = max(wor , mp[bb].n);
				if (mp.count(cc)) wor = max(wor , mp[cc].n);

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


				if (wor + 1 < ans.n) 
					ans = dt(wor + 1 , 0 , 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;

				long long aa = getHash(a);
				long long bb = getHash(b);
				long long cc = getHash(c);

				if (mp.count(aa)) wor = max(wor , mp[aa].n);
				if (mp.count(bb)) wor = max(wor , mp[bb].n);
				if (mp.count(cc)) wor = max(wor , mp[cc].n);

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


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

			}

	}




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

}

void init(int T) {

	mp.clear();
	mp[0] = 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);

  	{
		int a3 = getHeaviest(1 , 2 , 3), a1 , a2;
		rep(i , 1 , 4)
			if (i != a3) 
				a1 = i;
		rep(i , 1 , 4)
			if (i != a1 && i != a3) 
				a2 = i;
		R0(st , 0 , 1 , 2 , a3 - 1);

		assert(a2);

		int a4 = getHeaviest(a1, a2 , 4);

		R0(st , a1 - 1 , a2 - 1 , 3 , a4 - 1);
	}


	if (!mp.count(getHash(st))) assert(dfs(st , 5));

  
	while (st.size() > 1) {
		dt me = mp[getHash(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);
		}

	}


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

	answer(w);

}

Compilation message (stderr)

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

• Subtask 1: 71.428571 / 100