oj.uz

답안 #802957

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
802957 2023-08-02T16:25:23 Z happypotato 저울 (IOI15_scales) C++17
100 / 100
 988 ms 344 KB 
#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 (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;
			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

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.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 913 ms 300 KB Output is correct
2 Correct 857 ms 288 KB Output is correct
3 Correct 965 ms 292 KB Output is correct
4 Correct 913 ms 292 KB Output is correct
5 Correct 879 ms 288 KB Output is correct
6 Correct 840 ms 296 KB Output is correct
7 Correct 873 ms 296 KB Output is correct
8 Correct 865 ms 300 KB Output is correct
9 Correct 922 ms 344 KB Output is correct
10 Correct 969 ms 292 KB Output is correct
11 Correct 878 ms 296 KB Output is correct
12 Correct 932 ms 292 KB Output is correct
13 Correct 802 ms 296 KB Output is correct
14 Correct 862 ms 292 KB Output is correct
15 Correct 808 ms 300 KB Output is correct
16 Correct 881 ms 212 KB Output is correct
17 Correct 912 ms 288 KB Output is correct
18 Correct 842 ms 300 KB Output is correct
19 Correct 840 ms 296 KB Output is correct
20 Correct 827 ms 304 KB Output is correct
21 Correct 866 ms 288 KB Output is correct
22 Correct 879 ms 304 KB Output is correct
23 Correct 824 ms 304 KB Output is correct
24 Correct 867 ms 308 KB Output is correct
25 Correct 896 ms 304 KB Output is correct
26 Correct 857 ms 296 KB Output is correct
27 Correct 808 ms 300 KB Output is correct
28 Correct 857 ms 288 KB Output is correct
29 Correct 837 ms 296 KB Output is correct
30 Correct 836 ms 288 KB Output is correct
31 Correct 833 ms 288 KB Output is correct
32 Correct 959 ms 292 KB Output is correct
33 Correct 887 ms 312 KB Output is correct
34 Correct 988 ms 292 KB Output is correct
35 Correct 819 ms 332 KB Output is correct
36 Correct 859 ms 304 KB Output is correct
37 Correct 826 ms 332 KB Output is correct
38 Correct 964 ms 332 KB Output is correct
39 Correct 846 ms 292 KB Output is correct
40 Correct 835 ms 292 KB Output is correct