Submission #1212739

#	Time	Username	Problem	Language	Result	Execution time	Memory
1212739		alex_2008	Scales (IOI15_scales)	C++20	71.73 / 100	902 ms	548 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(6);
int cur_count_of_queries = 0;
int cur_sum_of_queries = 0;
vector <int> cur_vec(6);
/*
inline void answer(int* esim) {
	cur_sum_of_queries += cur_count_of_queries;
	//cout << "? " << cur_count_of_queries << "\n";
	cur_count_of_queries = 0;
}
inline int getLightest(int A, int B, int C) {
	cur_count_of_queries++;
	for (auto it : cur_vec) {
		if (it == A || it == B || it == C) return it;
	}
	return A;
}
inline int getHeaviest(int A, int B, int C) {
	cur_count_of_queries++;
	int w = 0;
	for (auto it : cur_vec) {
		if (it == A || it == B || it == C) w++;
		if (w == 3) return it;
	}
	return A;
}
inline int getMedian(int A, int B, int C) {
	cur_count_of_queries++;
	int w = 0;
	for (auto it : cur_vec) {
		if (it == A || it == B || it == C) w++;
		if (w == 2) return it;
	}
	return A;
}
inline int getNextLightest(int A, int B, int C, int D) {
	cur_count_of_queries++;
	bool ch = false;
	for (auto it : cur_vec) {
		if (it == D) ch = true;
		if (!ch) continue;
		if (it == A || it == B || it == C) return it;
	}
	for (auto it : cur_vec) {
		if (it == A || it == B || it == C) return it;
	}
	return A;
}
*/
int W;
vector <vector<int>> current_states;
void rec() {
	vector <int> v(6);
	for (int i = 0; i < 6; i++) {
		v[i] = i + 1;
	}
	while (1) {
		current_states.push_back(v);
		if (!next_permutation(v.begin(), v.end())) break;
	}
	while (1) {
		W /= 3;
		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;
		//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() <= (W - 1) || (int)f.size() < (int)best_case.size()) {
						best_case = f;
						type = "Median";
						A = a;
						B = b;
						C = c;
					}
				}
			}
		}
		//Lightest
		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 < indB && indA < indC) {
							f.push_back(it);
						}
						else if (indB < indA && indB < 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() <= (W - 1) || (int)f.size() < (int)best_case.size()) {
						best_case = f;
						type = "Light";
						A = a;
						B = b;
						C = c;
					}
				}
			}
		}
		//Heaviest
		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 > indB && indA > indC) {
							f.push_back(it);
						}
						else if (indB > indA && indB > 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() <= (W - 1) || (int)f.size() < (int)best_case.size()) {
						best_case = f;
						type = "Heavy";
						A = a;
						B = b;
						C = c;
					}
				}
			}
		}
		//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() <= (W - 1) || (int)f.size() < (int)best_case.size()) {
							best_case = f;
							type = "nextLightest";
							A = a;
							B = b;
							C = c;
							D = d;
						}
					}
				}
			}
		}
		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;
		}
		current_states = nxt_case;
	}
}
void orderCoins() {
	W = 729;
	vector <int> v(6);
	for (int i = 0; i < 6; i++) {
		v[i] = i + 1;
	}
	rec();
	int* answ = new int[6];
	for (int i = 0; i < 6; i++) {
		answ[i] = ans[i];
	}
	answer(answ);
}
/*
int main() {
	for (int i = 0; i < 6; i++) {
		cur_vec[i] = i + 1;
	}
	orderCoins();
	int ind = 0;
	int limit = 0;
	int range = 40;
	while (next_permutation(cur_vec.begin(), cur_vec.end())) {
		int prev_val = cur_sum_of_queries;
		ind++;
		if (ind >= limit && ind <= limit + range) {
			orderCoins();
			if ((cur_sum_of_queries - prev_val) > 7) {
				cout << "! ";
				for (auto it : cur_vec) {
					cout << it << " ";
				}
				return 0;
			}
		}
	}
	cout << cur_sum_of_queries << "\n";
}
*/

• Subtask 1: 71.7262 / 100