Submission #1212664

#	Time	Username	Problem	Language	Result	Execution time	Memory
1212664		alex_2008	Scales (IOI15_scales)	C++20	71.43 / 100	680 ms	616 KiB

scales

#include "scales.h"
#include <iostream>
#include <vector>
#include <random>
#include <chrono>
#include <algorithm>
#include <iomanip>
#include <set>
#include <map>
#include <deque>
#include <queue>
#define ff first
#define ss second
typedef long long ll;
typedef long double ld;
using namespace std;
const int N = 1e5 + 10;
void init(int T) {
	return;
}
vector <int> ans;
void rec(vector<vector<int>> current_states) {
	if ((int)current_states.size() == 1) {
		ans = current_states[0];
		return;
	}
	vector <vector<int>> best_case = current_states;
	string type = "unknown"; 
	int A, B, C, D;
	//nextLightest
	for (int a = 1; a <= 6; a++) {
		for (int b = 1; b <= 6; b++) {
			for (int c = 1; c <= 6; c++) {
				for (int d = 1; d <= 6; d++) {
					if (a == b || a == c || b == c) continue;
					if (a == d || b == d || c == d) continue;
					vector <vector<int>> f, s, t;
					for (auto& it : current_states) {
						int indA, indB, indC, indD;
						for (int j = 0; j < 6; j++) {
							if (it[j] == a) indA = j;
							if (it[j] == b) indB = j;
							if (it[j] == c) indC = j;
							if (it[j] == d) indD = j;
						}
						int mn = 1000;
						if (indA > indD) mn = min(mn, indA);
						if (indB > indD) mn = min(mn, indB);
						if (indC > indD) mn = min(mn, indC);
						if (mn == 1000) {
							if (indA < indB && indA < indC) {
								f.push_back(it);
							}
							else if (indB < indA && indB < indC) {
								s.push_back(it);
							}	
							else {
								t.push_back(it);
							}
						}
						else if (mn == indA) {
							f.push_back(it);
						}
						else if (mn == indB) {
							s.push_back(it);
						}
						else t.push_back(it);
					}
					if ((int)f.size() < (int)s.size()) swap(f, s);
					if ((int)f.size() < (int)t.size()) swap(f, t);
					if ((int)f.size() < (int)best_case.size()) {
						best_case = f;
						type = "nextLightest";
						A = a;
						B = b;
						C = c;
						D = d;
					}
				}
			}
		}
	}
	//Median
	for (int a = 1; a <= 6; a++) {
		for (int b = 1; b <= 6; b++) {
			for (int c = 1; c <= 6; c++) {
				if (a == b || a == c || b == c) continue;
				vector <vector<int>> f, s, t;
				for (auto& it : current_states) {
					int indA, indB, indC;
					for (int j = 0; j < 6; j++) {
						if (it[j] == a) indA = j;
						if (it[j] == b) indB = j;
						if (it[j] == c) indC = j;
					}
					if (indA > min(indB, indC) && indA < max(indC, indB)) {
						f.push_back(it);
					}
					else if (indB > min(indA, indC) && indB < max(indA, indC)) {
						s.push_back(it);
					}
					else t.push_back(it);
				}
				if ((int)f.size() < (int)s.size()) swap(f, s);
				if ((int)f.size() < (int)t.size()) swap(f, t);
				if ((int)f.size() < (int)best_case.size()) {
					best_case = f;
					type = "Median";
					A = a;
					B = b;
					C = c;
				}
			}
		}
	}
	vector <vector<int>> nxt_case;
	if (type == "Light") {
		int u = getLightest(A, B, C);
		vector <vector<int>> f, s, t;
		for (auto& it : current_states) {
			int indA, indB, indC;
			for (int j = 0; j < 6; j++) {
				if (it[j] == A) indA = j;
				if (it[j] == B) indB = j;
				if (it[j] == C) indC = j;
			}
			if (indA < indB && indA < indC) {
				f.push_back(it);
			}
			else if (indB < indA && indB < indC) {
				s.push_back(it);
			}
			else t.push_back(it);
		}
		if (u == A) nxt_case = f;
		else if (u == B) nxt_case = s;
		else nxt_case = t;
	}
	else if (type == "Heavy") {
		int u = getHeaviest(A, B, C);
		vector <vector<int>> f, s, t;
		for (auto& it : current_states) {
			int indA, indB, indC;
			for (int j = 0; j < 6; j++) {
				if (it[j] == A) indA = j;
				if (it[j] == B) indB = j;
				if (it[j] == C) indC = j;
			}
			if (indA > indB && indA > indC) {
				f.push_back(it);
			}
			else if (indB > indA && indB > indC) {
				s.push_back(it);
			}
			else t.push_back(it);
		}
		if (u == A) nxt_case = f;
		else if (u == B) nxt_case = s;
		else nxt_case = t;
	}
	else if (type == "Median") {
		int u = getMedian(A, B, C);
		vector <vector<int>> f, s, t;
		for (auto& it : current_states) {
			int indA, indB, indC;
			for (int j = 0; j < 6; j++) {
				if (it[j] == A) indA = j;
				if (it[j] == B) indB = j;
				if (it[j] == C) indC = j;
			}
			if (indA > min(indB, indC) && indA < max(indC, indB)) {
				f.push_back(it);
			}
			else if (indB > min(indA, indC) && indB < max(indA, indC)) {
				s.push_back(it);
			}
			else t.push_back(it);
		}
		if (u == A) nxt_case = f;
		else if (u == B) nxt_case = s;
		else nxt_case = t;
	}
	else {
		int u = getNextLightest(A, B, C, D);
		vector <vector<int>> f, s, t;
		for (auto& it : current_states) {
			int indA, indB, indC, indD;
			for (int j = 0; j < 6; j++) {
				if (it[j] == A) indA = j;
				if (it[j] == B) indB = j;
				if (it[j] == C) indC = j;
				if (it[j] == D) indD = j;
			}
			int mn = 1000;
			if (indA > indD) mn = min(mn, indA);
			if (indB > indD) mn = min(mn, indB);
			if (indC > indD) mn = min(mn, indC);
			if (mn == 1000) {
				if (indA < indB && indA < indC) {
					f.push_back(it);
				}
				else if (indB < indA && indB < indC) {
					s.push_back(it);
				}
				else {
					t.push_back(it);
				}
			}
			else if (mn == indA) {
				f.push_back(it);
			}
			else if (mn == indB) {
				s.push_back(it);
			}
			else t.push_back(it);
		}
		if (u == A) nxt_case = f;
		else if (u == B) nxt_case = s;
		else nxt_case = t;
	}
	rec(nxt_case);
}
void orderCoins() {
	vector <int> v(6);
	for (int i = 0; i < 6; i++) {
		v[i] = i + 1;
	}
	vector <vector<int>> esim;
	while (1) {
		esim.push_back(v);
		if (!next_permutation(v.begin(), v.end())) break;
	}
	rec(esim);	
	int* answ = new int[6];
	for (int i = 0; i < 6; i++) {
		answ[i] = ans[i];
	}
	answer(answ);
}

• Subtask 1: 71.4286 / 100