Submission #782826

#	Time	Username	Problem	Language	Result	Execution time	Memory
782826		Sohsoh84	Scales (IOI15_scales)	C++17	100 / 100	400 ms	720 KiB

scales

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

#define sep			' '
#define debug(x)	cerr << #x << ": " << x << endl;

using namespace std;

const int n = 6;
typedef map<int, vector<vector<int>>> space;

namespace S {
	inline int get(const vector<int>& a, int x) {
		for (int i = 0; i < n; i++)
			if (a[i] == x)
				return i;

		return -1;
	}

	inline int getHeaviest(const vector<int>& a, int i, int j, int k) {
		int x = get(a, i), y = get(a, j), z = get(a, k);
		if (x > y && x > z) return i;
		if (y > x && y > z) return j;
		if (z > x && z > y) return k; 

		return -1;
	}

	inline int median(int x, int y, int z) {
		int a[3] = {x, y, z};
		sort(a, a + 3);
		return a[1];
	}

	inline int getMedian(const vector<int>& a, int i, int j, int k) {
		int x = get(a, i), y = get(a, j), z = get(a, k);
		int m = median(x, y, z);
		if (x == m) return i;
		if (y == m) return j;
		if (z == m) return k; 
		
		return -1;
	}

	inline int getLightest(const vector<int>& a, int i, int j, int k) {
		int x = get(a, i), y = get(a, j), z = get(a, k);
		if (x < y && x < z) return i;
		if (y < x && y < z) return j;
		if (z < x && z < y) return k; 
		
		return -1;
	}

	inline int getNextLightest(const vector<int>& a, int i, int j, int k, int r) {
		int x = get(a, i), y = get(a, j), z = get(a, k), f = get(a, r);
		if (max({x, y, z}) < f) return getLightest(a, i, j, k);
		int t = max({x, y, z});
		if (x > f && x < t) t = x;
		if (y > f && y < t) t = y;
		if (z > f && z < t) t = z;

		if (t == x) return i;
		if (t == y) return j;
		if (t == z) return k;

		return -1;
	}

	inline space D0(vector<vector<int>>& a, int i, int j, int k) {
		space ans;
		for (const vector<int>& e : a)
			ans[getHeaviest(e, i, j, k)].push_back(e);
		
		return ans;
	}

	inline space D1(vector<vector<int>>& a, int i, int j, int k) {
		space ans;
		for (const vector<int>& e : a)
			ans[getMedian(e, i, j, k)].push_back(e);
		
		return ans;
	} 
	
	inline space D2(vector<vector<int>>& a, int i, int j, int k) {
		space ans;
		for (const vector<int>& e : a)
			ans[getLightest(e, i, j, k)].push_back(e);
		
		return ans;
	} 

	inline space D3(vector<vector<int>>& a, int i, int j, int k, int r) {
		space ans;
		for (const vector<int>& e : a)
			ans[getNextLightest(e, i, j, k, r)].push_back(e);
		
		return ans;
	} 
}

inline int spaceScore(const space& a) {
	int score = 0;
	for (auto [x, y] : a)
		score = max(score, int(y.size()));

	return score;
}

inline void solve(vector<vector<int>> F) {
	if (F.size() == 1) {
		int ans[6];
		for (int i = 0; i < n; i++)
			ans[i] = F[0][i];
	
		answer(ans);
		return;
	}

	int best_score = 100000;
	space best_space;



	int ft = 0, fi = 0, fj = 1, fk = 2, fr = 3;

	for (int i = 1; i <= n; i++) {
		for (int j = i + 1; j <= n; j++) {
			for (int k = j + 1; k <= n; k++) {
				space tmp = S::D0(F, i, j, k);
				int s = spaceScore(tmp);
				if (s <= best_score) {
					best_score = s;
					best_space = tmp;
					
					ft = 0;
					fi = i;
					fj = j;
					fk = k;
				}
			}
		}
	}

	for (int i = 1; i <= n; i++) {
		for (int j = i + 1; j <= n; j++) {
			for (int k = j + 1; k <= n; k++) {
				space tmp = S::D2(F, i, j, k);
				int s = spaceScore(tmp);
				if (s <= best_score) {
					best_score = s;
					best_space = tmp;
					
					ft = 2;
					fi = i;
					fj = j;
					fk = k;
				}
			}
		}
	}


	for (int i = 1; i <= n; i++) {
		for (int j = i + 1; j <= n; j++) {
			for (int k = j + 1; k <= n; k++) {
				space tmp = S::D1(F, i, j, k);
				int s = spaceScore(tmp);
				if (s <= best_score) {
					best_score = s;
					best_space = tmp;
					
					ft = 1;
					fi = i;
					fj = j;
					fk = k;
				}
			}
		}
	}


	for (int r = 1; r <= n; r++) {
		for (int i = 1; i <= n; i++) {
			for (int j = i + 1; j <= n; j++) {
				for (int k = j + 1; k <= n; k++) {
					if (r == i || r == j || r == k) continue;
					space tmp = S::D3(F, i, j, k, r);
					int s = spaceScore(tmp);
					if (s <= best_score) {
						best_score = s;
						best_space = tmp;
						
						ft = 3;
						fi = i;
						fj = j;
						fk = k;
						fr = r;
					}
				}
			}
		}
	}

	int ans = 0;
	if (ft == 0) ans = getHeaviest(fi, fj, fk);
	if (ft == 1) ans = getMedian(fi, fj, fk);
	if (ft == 2) ans = getLightest(fi, fj, fk);
	if (ft == 3) ans = getNextLightest(fi, fj, fk, fr);
	
	F = best_space[ans];
	solve(F);
}

void init(int T) {}

void orderCoins() {
	/* ... */
	vector<vector<int>> F;
	vector<int> vec;
	for (int i = 1; i <= n; i++) vec.push_back(i);
	do {
		F.push_back(vec);
	} while (next_permutation(vec.begin(), vec.end()));

	solve(F);
}

Compilation message (stderr)

scales.cpp: In function 'void init(int)':
scales.cpp:216:15: warning: unused parameter 'T' [-Wunused-parameter]
  216 | void init(int T) {}
      |           ~~~~^

• Subtask 1: 100 / 100