답안 #802827

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
802827	2023-08-02T14:53:20 Z	happypotato	저울 (IOI15_scales)	C++17	55.5556 / 100	254 ms	312 KB

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<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());
	vector<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;
			res.pb(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 Heaviest(int a, int b, int c = 0) {
	if (c == 0) c = (min(a, b) != 1 ? 1 : max(a, b) != 2 ? 2 : 3);
	int res = getHeaviest(a, b, c);
	clues.pb({1, {res, a, b, c}});
	return res;
}
int Lightest(int a, int b, int c = 0) {
	if (c == 0) c = (min(a, b) != 1 ? 1 : max(a, b) != 2 ? 2 : 3);
	int res = getLightest(a, b, c);
	clues.pb({2, {res, a, b, c}});
	return res;
}
int Median(int a, int b, int c) {
	int res = getMedian(a, b, c);
	clues.pb({3, {res, a, b, c}});
	return res;
}
int NextLightest(int a, int b, int c, int d) {
	int res = getNextLightest(a, b, c, d);
	clues.pb({4, {res, a, b, c, d}});
	return res;
}
/*
getHeaviest()
getLightest()
getMedian()
getNextLightest()
*/
int TryHeaviest(int a, int b, int c) {
	int res = 0;
	clues.pb({1, {a, a, b, c}}); res = max(res, (int)FindAllPossible().size()); clues.pop_back();
	clues.pb({1, {b, a, b, c}}); res = max(res, (int)FindAllPossible().size()); clues.pop_back();
	clues.pb({1, {c, a, b, c}}); res = max(res, (int)FindAllPossible().size()); clues.pop_back();
	return res;
}
int TryLightest(int a, int b, int c) {
	int res = 0;
	clues.pb({2, {a, a, b, c}}); res = max(res, (int)FindAllPossible().size()); clues.pop_back();
	clues.pb({2, {b, a, b, c}}); res = max(res, (int)FindAllPossible().size()); clues.pop_back();
	clues.pb({2, {c, a, b, c}}); res = max(res, (int)FindAllPossible().size()); clues.pop_back();
	return res;
}
int TryMedian(int a, int b, int c) {
	int res = 0;
	clues.pb({3, {a, a, b, c}}); res = max(res, (int)FindAllPossible().size()); clues.pop_back();
	clues.pb({3, {b, a, b, c}}); res = max(res, (int)FindAllPossible().size()); clues.pop_back();
	clues.pb({3, {c, a, b, c}}); res = max(res, (int)FindAllPossible().size()); clues.pop_back();
	return res;
}
int TryNextLightest(int a, int b, int c, int d) {
	int res = 0;
	clues.pb({4, {a, a, b, c, d}}); res = max(res, (int)FindAllPossible().size()); clues.pop_back();
	clues.pb({4, {b, a, b, c, d}}); res = max(res, (int)FindAllPossible().size()); clues.pop_back();
	clues.pb({4, {c, a, b, c, d}}); res = max(res, (int)FindAllPossible().size()); clues.pop_back();
	return res;
}
// I'll end it here, 2:50 left next time

void orderCoins() {
	clues.clear();

	stack<int> s;
	for (int i = 1; i <= 6; i++) s.push(i);
	while (s.size() >= 3) {
		int a = s.top(); s.pop();
		int b = s.top(); s.pop();
		int c = s.top(); s.pop();
		int res = Lightest(a, b, c);
		if (a != res) s.push(a);
		if (b != res) s.push(b);
		if (c != res) s.push(c);
	}
	// 4 queries, 8 edges found
	// try pure exhaust?
	vector<vector<int>> fin = FindAllPossible();
	while (fin.size() > 1) {
		cerr << "Current size: " << fin.size() << ", ";
		cerr << "Current queries: " << clues.size() << endl;
		int cursz = fin.size(), res;
		vector<int> nxtquery;
		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) {
						cursz = res;
						nxtquery = {1, a, b, c};
					}

					res = TryLightest(a, b, c);
					if (res < cursz) {
						cursz = res;
						nxtquery = {2, a, b, c};
					}

					res = TryMedian(a, b, c);
					if (res < cursz) {
						cursz = res;
						nxtquery = {3, a, b, c};
					}

					for (int d = 1; d <= 6; d++) {
						if (d == a || d == b || d == c) continue;
						res = TryNextLightest(a, b, c, d);
						if (res < cursz) {
							cursz = res;
							nxtquery = {4, a, b, c, d};
						}
					}
				}
			}
		}
		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]);
		fin = FindAllPossible();
	}
	Answer(fin.front());
}
/*
15 edges to consider (know all -> must can sort)
full sol: 6 queries (by math)
(current sol: 9 queries)
*/

Compilation message

scales.cpp: In function 'void init(int)':
scales.cpp:10:15: warning: unused parameter 'T' [-Wunused-parameter]
   10 | void init(int T) {
      |           ~~~~^
scales.cpp: In function 'void orderCoins()':
scales.cpp:170:23: warning: conversion from 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
  170 |   int cursz = fin.size(), res;
      |               ~~~~~~~~^~

Subtask #1

55.555556 / 100.0

#	결과	실행 시간	메모리	Grader output
1	Partially correct	224 ms	292 KB	Output is partially correct
2	Partially correct	139 ms	212 KB	Output is partially correct
3	Partially correct	174 ms	292 KB	Output is partially correct
4	Partially correct	144 ms	296 KB	Output is partially correct
5	Partially correct	163 ms	292 KB	Output is partially correct
6	Partially correct	197 ms	292 KB	Output is partially correct
7	Partially correct	149 ms	296 KB	Output is partially correct
8	Partially correct	146 ms	288 KB	Output is partially correct
9	Partially correct	153 ms	292 KB	Output is partially correct
10	Partially correct	189 ms	292 KB	Output is partially correct
11	Partially correct	138 ms	288 KB	Output is partially correct
12	Partially correct	147 ms	296 KB	Output is partially correct
13	Partially correct	172 ms	300 KB	Output is partially correct
14	Partially correct	146 ms	288 KB	Output is partially correct
15	Partially correct	186 ms	288 KB	Output is partially correct
16	Partially correct	184 ms	288 KB	Output is partially correct
17	Partially correct	163 ms	304 KB	Output is partially correct
18	Partially correct	198 ms	296 KB	Output is partially correct
19	Partially correct	190 ms	288 KB	Output is partially correct
20	Partially correct	254 ms	212 KB	Output is partially correct
21	Partially correct	129 ms	300 KB	Output is partially correct
22	Partially correct	141 ms	300 KB	Output is partially correct
23	Partially correct	136 ms	300 KB	Output is partially correct
24	Partially correct	133 ms	288 KB	Output is partially correct
25	Partially correct	204 ms	308 KB	Output is partially correct
26	Partially correct	155 ms	312 KB	Output is partially correct
27	Partially correct	157 ms	288 KB	Output is partially correct
28	Partially correct	171 ms	212 KB	Output is partially correct
29	Partially correct	145 ms	300 KB	Output is partially correct
30	Partially correct	137 ms	292 KB	Output is partially correct
31	Partially correct	162 ms	296 KB	Output is partially correct
32	Partially correct	151 ms	308 KB	Output is partially correct
33	Partially correct	222 ms	300 KB	Output is partially correct
34	Partially correct	214 ms	288 KB	Output is partially correct
35	Partially correct	193 ms	292 KB	Output is partially correct
36	Partially correct	129 ms	292 KB	Output is partially correct
37	Partially correct	163 ms	212 KB	Output is partially correct
38	Partially correct	220 ms	288 KB	Output is partially correct
39	Partially correct	132 ms	292 KB	Output is partially correct
40	Partially correct	159 ms	304 KB	Output is partially correct