Submission #800655

#	Time	Username	Problem	Language	Result	Execution time	Memory
800655		happypotato	Scales (IOI15_scales)	C++17	6.85 / 100	1 ms	212 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

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};
vector<int> IsUnique() {
	sort(perm.begin(), perm.end());
	vector<int> res = {};
	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 (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 (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 (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]]);
					}
				} 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) {
			// cerr << "FOUND ";
			// for (int &x : perm) cerr << x << ' ';
			// cerr << endl;
			if (res.empty()) res = perm;
			else return {};
		}
	} while (next_permutation(perm.begin() + 1, perm.end()));
	if (res.empty()) {
		// cerr << "oh no 1" << endl;
		throw runtime_error("cannot find correct permutation?");
	}
	return res;
}
void Answer(vector<int> v) {
	int ans[6];
	for (int i = 1; i <= 6; i++) ans[v[i] - 1] = i;
	answer(ans);
}

/*
getHeaviest()
getLightest()
getMedian()
getNextLightest()
*/

void orderCoins() {
	clues.clear();
	for (int i = 1; i <= 6; i++) {
		for (int j = i + 1; j <= 6; j++) {
			for (int k = j + 1; k <= 6; k++) {
				clues.pb({1, {getHeaviest(i, j, k), i, j, k}});
				clues.pb({2, {getLightest(i, j, k), i, j, k}});
			}
		}
	}
	// for (pair<int, vector<int>> &cur : clues) {
	// 	cerr << "CLUE " << cur.ff << " | ";
	// 	for (int &x : cur.ss) cerr << x << ' ';
	// 	cerr << endl;
	// }
	Answer(IsUnique());
}
/*
15 edges to consider (know all -> must can sort)

*/

Compilation message (stderr)

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

• Subtask 1: 6.849315 / 100