oj.uz

답안 #782826

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
782826 2023-07-14T09:57:49 Z Sohsoh84 저울 (IOI15_scales) C++17
100 / 100
 400 ms 720 KB 
#include "scales.h"
#include <bits/stdc++.h>

#define sep			' '
#define debug(x)	cerr << #x << ": " << x << endl;

using namespace std;

const int n = 6;
typedef map<int, vector<vector<int>>> space;

namespace S {
	inline int get(const vector<int>& a, int x) {
		for (int i = 0; i < n; i++)
			if (a[i] == x)
				return i;

		return -1;
	}

	inline int getHeaviest(const vector<int>& a, int i, int j, int k) {
		int x = get(a, i), y = get(a, j), z = get(a, k);
		if (x > y && x > z) return i;
		if (y > x && y > z) return j;
		if (z > x && z > y) return k; 

		return -1;
	}

	inline int median(int x, int y, int z) {
		int a[3] = {x, y, z};
		sort(a, a + 3);
		return a[1];
	}

	inline int getMedian(const vector<int>& a, int i, int j, int k) {
		int x = get(a, i), y = get(a, j), z = get(a, k);
		int m = median(x, y, z);
		if (x == m) return i;
		if (y == m) return j;
		if (z == m) return k; 
		
		return -1;
	}

	inline int getLightest(const vector<int>& a, int i, int j, int k) {
		int x = get(a, i), y = get(a, j), z = get(a, k);
		if (x < y && x < z) return i;
		if (y < x && y < z) return j;
		if (z < x && z < y) return k; 
		
		return -1;
	}

	inline int getNextLightest(const vector<int>& a, int i, int j, int k, int r) {
		int x = get(a, i), y = get(a, j), z = get(a, k), f = get(a, r);
		if (max({x, y, z}) < f) return getLightest(a, i, j, k);
		int t = max({x, y, z});
		if (x > f && x < t) t = x;
		if (y > f && y < t) t = y;
		if (z > f && z < t) t = z;

		if (t == x) return i;
		if (t == y) return j;
		if (t == z) return k;

		return -1;
	}

	inline space D0(vector<vector<int>>& a, int i, int j, int k) {
		space ans;
		for (const vector<int>& e : a)
			ans[getHeaviest(e, i, j, k)].push_back(e);
		
		return ans;
	}

	inline space D1(vector<vector<int>>& a, int i, int j, int k) {
		space ans;
		for (const vector<int>& e : a)
			ans[getMedian(e, i, j, k)].push_back(e);
		
		return ans;
	} 
	
	inline space D2(vector<vector<int>>& a, int i, int j, int k) {
		space ans;
		for (const vector<int>& e : a)
			ans[getLightest(e, i, j, k)].push_back(e);
		
		return ans;
	} 

	inline space D3(vector<vector<int>>& a, int i, int j, int k, int r) {
		space ans;
		for (const vector<int>& e : a)
			ans[getNextLightest(e, i, j, k, r)].push_back(e);
		
		return ans;
	} 
}

inline int spaceScore(const space& a) {
	int score = 0;
	for (auto [x, y] : a)
		score = max(score, int(y.size()));

	return score;
}

inline void solve(vector<vector<int>> F) {
	if (F.size() == 1) {
		int ans[6];
		for (int i = 0; i < n; i++)
			ans[i] = F[0][i];
	
		answer(ans);
		return;
	}

	int best_score = 100000;
	space best_space;



	int ft = 0, fi = 0, fj = 1, fk = 2, fr = 3;

	for (int i = 1; i <= n; i++) {
		for (int j = i + 1; j <= n; j++) {
			for (int k = j + 1; k <= n; k++) {
				space tmp = S::D0(F, i, j, k);
				int s = spaceScore(tmp);
				if (s <= best_score) {
					best_score = s;
					best_space = tmp;
					
					ft = 0;
					fi = i;
					fj = j;
					fk = k;
				}
			}
		}
	}

	for (int i = 1; i <= n; i++) {
		for (int j = i + 1; j <= n; j++) {
			for (int k = j + 1; k <= n; k++) {
				space tmp = S::D2(F, i, j, k);
				int s = spaceScore(tmp);
				if (s <= best_score) {
					best_score = s;
					best_space = tmp;
					
					ft = 2;
					fi = i;
					fj = j;
					fk = k;
				}
			}
		}
	}


	for (int i = 1; i <= n; i++) {
		for (int j = i + 1; j <= n; j++) {
			for (int k = j + 1; k <= n; k++) {
				space tmp = S::D1(F, i, j, k);
				int s = spaceScore(tmp);
				if (s <= best_score) {
					best_score = s;
					best_space = tmp;
					
					ft = 1;
					fi = i;
					fj = j;
					fk = k;
				}
			}
		}
	}


	for (int r = 1; r <= n; r++) {
		for (int i = 1; i <= n; i++) {
			for (int j = i + 1; j <= n; j++) {
				for (int k = j + 1; k <= n; k++) {
					if (r == i || r == j || r == k) continue;
					space tmp = S::D3(F, i, j, k, r);
					int s = spaceScore(tmp);
					if (s <= best_score) {
						best_score = s;
						best_space = tmp;
						
						ft = 3;
						fi = i;
						fj = j;
						fk = k;
						fr = r;
					}
				}
			}
		}
	}

	int ans = 0;
	if (ft == 0) ans = getHeaviest(fi, fj, fk);
	if (ft == 1) ans = getMedian(fi, fj, fk);
	if (ft == 2) ans = getLightest(fi, fj, fk);
	if (ft == 3) ans = getNextLightest(fi, fj, fk, fr);
	
	F = best_space[ans];
	solve(F);
}

void init(int T) {}

void orderCoins() {
	/* ... */
	vector<vector<int>> F;
	vector<int> vec;
	for (int i = 1; i <= n; i++) vec.push_back(i);
	do {
		F.push_back(vec);
	} while (next_permutation(vec.begin(), vec.end()));

	solve(F);
}

Compilation message

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

Subtask #1
100.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 350 ms 496 KB Output is correct
2 Correct 349 ms 504 KB Output is correct
3 Correct 355 ms 492 KB Output is correct
4 Correct 349 ms 620 KB Output is correct
5 Correct 346 ms 500 KB Output is correct
6 Correct 353 ms 492 KB Output is correct
7 Correct 344 ms 468 KB Output is correct
8 Correct 345 ms 500 KB Output is correct
9 Correct 348 ms 720 KB Output is correct
10 Correct 375 ms 496 KB Output is correct
11 Correct 347 ms 500 KB Output is correct
12 Correct 348 ms 508 KB Output is correct
13 Correct 350 ms 500 KB Output is correct
14 Correct 344 ms 500 KB Output is correct
15 Correct 352 ms 612 KB Output is correct
16 Correct 351 ms 500 KB Output is correct
17 Correct 349 ms 504 KB Output is correct
18 Correct 347 ms 504 KB Output is correct
19 Correct 350 ms 508 KB Output is correct
20 Correct 344 ms 500 KB Output is correct
21 Correct 400 ms 468 KB Output is correct
22 Correct 347 ms 504 KB Output is correct
23 Correct 368 ms 468 KB Output is correct
24 Correct 382 ms 596 KB Output is correct
25 Correct 348 ms 592 KB Output is correct
26 Correct 399 ms 600 KB Output is correct
27 Correct 345 ms 492 KB Output is correct
28 Correct 359 ms 508 KB Output is correct
29 Correct 354 ms 500 KB Output is correct
30 Correct 353 ms 504 KB Output is correct
31 Correct 347 ms 500 KB Output is correct
32 Correct 378 ms 620 KB Output is correct
33 Correct 353 ms 500 KB Output is correct
34 Correct 368 ms 620 KB Output is correct
35 Correct 348 ms 500 KB Output is correct
36 Correct 346 ms 500 KB Output is correct
37 Correct 343 ms 468 KB Output is correct
38 Correct 344 ms 492 KB Output is correct
39 Correct 374 ms 620 KB Output is correct
40 Correct 349 ms 504 KB Output is correct