Submission #807416

#	Time	Username	Problem	Language	Result	Execution time	Memory
807416		happypotato	Scales (IOI15_scales)	C++17	100 / 100	885 ms	332 KiB

scales

#include "scales.h"
 
#include <bits/stdc++.h>
using namespace std;
#define pii pair<int, int>
#define ff first
#define ss second
#define pb push_back
#pragma GCC optimize("O2")
 
void init(int T) {
	
}
 
/*
getHeaviest()
getLightest()
getMedian()
getNextLightest()
*/
 
vector<pair<int, vector<int>>> clues; // {type, {answer, [query elements]}}
vector<int> perm = {0, 1, 2, 3, 4, 5, 6};
pair<int, vector<int>> FindAllPossible() {
	// cerr << "CURRENT CLUES:\n";
	// for (pair<int, vector<int>> &cur : clues) {
	// 	cerr << cur.ff << " | ";
	// 	for (int &x : cur.ss) cerr << x << ' ';
	// 	cerr << endl;
	// }
	sort(perm.begin(), perm.end());
	pair<int, vector<int>> res = {0, {}};
	do {
		bool valid = true;
		for (pair<int, vector<int>> &cur : clues) {
			// cerr << "CLUE " << cur.ff << ' ';
			// for (int &x : cur.ss) cerr << x << ' '; cerr << endl;
			if (cur.ff == 1) {
				for (int i = 1; i <= 3; i++) {
					if (cur.ss[0] == cur.ss[i]) continue;
					valid &= (perm[cur.ss[0]] > perm[cur.ss[i]]);
                	if (!valid) break;
				}
			}
			if (cur.ff == 2) {
				for (int i = 1; i <= 3; i++) {
					if (cur.ss[0] == cur.ss[i]) continue;
					valid &= (perm[cur.ss[0]] < perm[cur.ss[i]]);
                	if (!valid) break;
				}
			}
			if (cur.ff == 3) {
				int cnt = 0;
				for (int i = 1; i <= 3; i++) {
					if (cur.ss[0] == cur.ss[i]) continue;
					cnt += (perm[cur.ss[0]] < perm[cur.ss[i]]);
				}
				valid &= (cnt == 1);
                if (!valid) break;
			}
			if (cur.ff == 4) {
				bool allsmaller = true;
				for (int i = 1; i <= 3; i++) {
					allsmaller &= (perm[cur.ss[i]] < perm[cur.ss[4]]);
				}
				if (allsmaller) {
					for (int i = 1; i <= 3; i++) {
						if (cur.ss[0] == cur.ss[i]) continue;
						valid &= (perm[cur.ss[i]] > perm[cur.ss[0]]);
						if (!valid) break;
					}
				} else {
					valid &= (perm[cur.ss[0]] > perm[cur.ss[4]]);
					for (int i = 1; i <= 3; i++) {
						if (cur.ss[0] == cur.ss[i]) continue;
						valid &= (perm[cur.ss[i]] < perm[cur.ss[4]] || perm[cur.ss[i]] > perm[cur.ss[0]]);
						if (!valid) break;
					}
				}
			}
			if (!valid) break;
		}
		if (valid) {
			// cerr << "FOUND ";
			// for (int &x : perm) cerr << x << ' ';
			// cerr << endl;
			res.ff++;
			res.ss = perm;
		}
	} while (next_permutation(perm.begin() + 1, perm.end()));
	return res;
}
void Answer(vector<int> &v) {
	int ans[6];
	for (int i = 1; i <= 6; i++) ans[v[i] - 1] = i;
	answer(ans);
}
 
int testres;
int Heaviest(int a, int b, int c = 0) {
	if (c == 0) c = (min(a, b) != 1 ? 1 : max(a, b) != 2 ? 2 : 3);
	testres = getHeaviest(a, b, c);
	clues.pb({1, {testres, a, b, c}});
	return testres;
}
int Lightest(int a, int b, int c = 0) {
	if (c == 0) c = (min(a, b) != 1 ? 1 : max(a, b) != 2 ? 2 : 3);
	testres = getLightest(a, b, c);
	clues.pb({2, {testres, a, b, c}});
	return testres;
}
int Median(int a, int b, int c) {
	testres = getMedian(a, b, c);
	clues.pb({3, {testres, a, b, c}});
	return testres;
}
int NextLightest(int a, int b, int c, int d) {
	testres = getNextLightest(a, b, c, d);
	clues.pb({4, {testres, a, b, c, d}});
	return testres;
}
/*
getHeaviest()
getLightest()
getMedian()
getNextLightest()
*/
int TryHeaviest(int a, int b, int c) {
	testres = 0;
	clues.pb({1, {a, a, b, c}}); testres = max(testres, FindAllPossible().ff); clues.pop_back();
	clues.pb({1, {b, a, b, c}}); testres = max(testres, FindAllPossible().ff); clues.pop_back();
	clues.pb({1, {c, a, b, c}}); testres = max(testres, FindAllPossible().ff); clues.pop_back();
	return testres;
}
int TryLightest(int a, int b, int c) {
	testres = 0;
	clues.pb({2, {a, a, b, c}}); testres = max(testres, FindAllPossible().ff); clues.pop_back();
	clues.pb({2, {b, a, b, c}}); testres = max(testres, FindAllPossible().ff); clues.pop_back();
	clues.pb({2, {c, a, b, c}}); testres = max(testres, FindAllPossible().ff); clues.pop_back();
	return testres;
}
int TryMedian(int a, int b, int c) {
	testres = 0;
	clues.pb({3, {a, a, b, c}}); testres = max(testres, FindAllPossible().ff); clues.pop_back();
	clues.pb({3, {b, a, b, c}}); testres = max(testres, FindAllPossible().ff); clues.pop_back();
	clues.pb({3, {c, a, b, c}}); testres = max(testres, FindAllPossible().ff); clues.pop_back();
	return testres;
}
int TryNextLightest(int a, int b, int c, int d) {
	testres = 0;
	clues.pb({4, {a, a, b, c, d}}); testres = max(testres, FindAllPossible().ff); clues.pop_back();
	clues.pb({4, {b, a, b, c, d}}); testres = max(testres, FindAllPossible().ff); clues.pop_back();
	clues.pb({4, {c, a, b, c, d}}); testres = max(testres, FindAllPossible().ff); clues.pop_back();
	return testres;
}
int TestTwo(pair<int, vector<int>> lhs, vector<pair<int, vector<int>>> rhs) {
	int res = 0;
	for (int i = 1; i <= 3; i++) {
		lhs.ss[0] = lhs.ss[i];
		clues.pb(lhs);
		for (int j = 1; j <= 3; j++) {
			rhs[i - 1].ss[0] = rhs[i - 1].ss[i];
			clues.pb(rhs[i - 1]);
			res = max(res, FindAllPossible().ff);
			clues.pop_back();
		}
		clues.pop_back();
	}
	return res;
}
 
mt19937 rng(time(NULL));
int GetRand(int x) {
	return (int)(rng() % x);
}
 
vector<vector<int>> GetBestQueries(int tar = -1) {
	int cursz = FindAllPossible().ff, res;
	vector<vector<int>> nxtqueries;
	for (int a = 1; a <= 6; a++) {
		for (int b = a + 1; b <= 6; b++) {
			for (int c = b + 1; c <= 6; c++) {
				// res = TryHeaviest(a, b, c);
				// if (res <= cursz) {
				// 	if (res < cursz) nxtqueries.clear();
				// 	nxtqueries.pb({1, a, b, c});
				// 	cursz = res;
				// }
 
				// res = TryLightest(a, b, c);
				// if (res <= cursz) {
				// 	if (res < cursz) nxtqueries.clear();
				// 	nxtqueries.pb({2, a, b, c});
				// 	cursz = res;
				// }
 
				res = TryMedian(a, b, c);
				if (res <= cursz) {
					if (res < cursz) nxtqueries.clear();
					nxtqueries.pb({3, a, b, c});
					cursz = res;
				}
 
				for (int d = 1; d <= 6; d++) {
					if (d == a || d == b || d == c) continue;
					res = TryNextLightest(a, b, c, d);
					if (res <= cursz) {
						if (res < cursz) nxtqueries.clear();
						nxtqueries.pb({4, a, b, c, d});
						cursz = res;
					}
				}
 
				if (tar != -1 && cursz <= tar) return nxtqueries;
				// if (nxtqueries.size() >= 10) return nxtqueries;
			}
		}
	}
	return nxtqueries;
}
void UseThisQuery(vector<int> nxtquery) {
	if (nxtquery.front() == 1) Heaviest(nxtquery[1], nxtquery[2], nxtquery[3]);
	if (nxtquery.front() == 2) Lightest(nxtquery[1], nxtquery[2], nxtquery[3]);
	if (nxtquery.front() == 3) Median(nxtquery[1], nxtquery[2], nxtquery[3]);
	if (nxtquery.front() == 4) NextLightest(nxtquery[1], nxtquery[2], nxtquery[3], nxtquery[4]);
}
void TryUseThisQuery(vector<int> nxtquery, int res) {
	swap(nxtquery[0], res);
	clues.pb({res, nxtquery});
}
void orderCoins() {
	clues.clear();
 
	Lightest(1, 2, 3);
	Median(4, 5, 6);
	UseThisQuery(GetBestQueries().front());
 
	pair<int, vector<int>> fin = FindAllPossible();
	vector<int> allrem;
	while (fin.ff > 1) {
		if (clues.size() == 6) {
			cout << "fucked up: ";
			for (int &x : allrem) cout << x << ' ';
			cout << endl;
		}
		allrem.pb(fin.ff);
		// cerr << "Current size: " << fin.size() << ", ";
		// cerr << "Current queries: " << clues.size() << endl;
 
		vector<vector<int>> curquery = GetBestQueries();
		vector<int> finquery = curquery.front();
		int finmin = 720;
		vector<int> corr = {720, 240, 80, 26, 9, 3, 1};
		for (vector<int> &cur : curquery) {
			int fincur = 0;
			for (int res = 1; res <= 3; res++) {
				TryUseThisQuery(cur, cur[res]);
				vector<int> follow = GetBestQueries(corr[(int)clues.size() + 1]).front();
				for (int fres = 1; fres <= 3; fres++) {
					TryUseThisQuery(follow, follow[fres]);
					fincur = max(fincur, FindAllPossible().ff);
					clues.pop_back();
				}
				clues.pop_back();
			}
			if (fincur < finmin) {
				finmin = fincur;
				finquery = cur;
			}
		}
 
		// cerr << "Current clues: " << clues.size() << ", Final Query: ";
		// for (int &x : finquery) cerr << x << ' ';
		// cerr << endl;
		UseThisQuery(finquery);
		
		fin = FindAllPossible();
	}
	Answer(fin.ss);
}
/*
15 edges to consider (know all -> must can sort)
full sol: 6 queries (by math)
(current sol: 7 queries)
 
full sol is consider 2 queries at once (?)
*/

Compilation message (stderr)

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

• Subtask 1: 100 / 100