Submission #762606

#	Time	Username	Problem	Language	Result	Execution time	Memory
762606		goodbyehanbyeol	Wine Tasting (FXCUP4_wine)	C++17	49 / 100	13 ms	19760 KiB

bartender

#include "bartender.h"
#include <bits/stdc++.h>
using namespace std;

#define MAX 101010
typedef pair<int, int> pii;

int N;

std::vector<int> BlendWines(int K, std::vector<int> R){
	vector<int> v;
	for (auto x : R) {
		x--;
		if (x >= 24) v.push_back(x - 17);
		else v.push_back(x / 4 + 1);
	}
	return v;
}

taster

#include "taster.h"
#include <bits/stdc++.h>
using namespace std;

#define MAX 101010
typedef pair<int, int> pii;

int cnt = 0;
int query(int a, int b) {
	cnt++;
	int res = Compare(a, b);
	if (res == -1) return 1;
	else return 0;
}

vector<int> endv[8][MAX];
pii question[8][MAX];
int isend[8][MAX];
bool getTree(int n, int loc, vector<vector<int>> arr, int t = 6) {
	isend[n][loc] = 0;
	if (arr.size() == 1) {
		endv[n][loc] = arr[0];
		isend[n][loc] = 1;
		return true;
	}
	if (!t) {
		if (arr[0].size() > 1) return false;
		endv[n][loc] = arr[0];
		isend[n][loc] = 1;
		return true;
	}
	else {
		int a, b;
		for (a = 0; a < n; a++) for (b = a + 1; b < n; b++) {
			vector<vector<int>> tv, fv;
			for (auto& v : arr) {
				if (v[a] < v[b]) tv.push_back(v);
				else fv.push_back(v);
			}
			if (tv.empty()) continue;
			if (fv.empty()) continue;
			if (tv.size() > (1 << (t - 1))) continue;
			if (fv.size() > (1 << (t - 1))) continue;
			question[n][loc] = pii(a, b);
			if (getTree(n, loc * 2, tv, t - 1) && getTree(n, loc * 2 + 1, fv, t - 1)) return true;
		}
		return false;
	}
}
void init_tree(int n) {
	int i;
	vector<int> v;
	for (i = 0; i < n; i++) v.push_back(i);
	int T = 1;
	for (i = 1; i <= n; i++) T *= i;
	vector<vector<int>> all;
	while (T--) {
		int c = 1;
		if (n > 5) {
			if (v[0] > v[1]) c = 0;
			if (v[2] > v[3]) c = 0;
			if (v[4] > v[5]) c = 0;
			if (v[0] > v[2]) c = 0;
		}
		if (c) all.push_back(v);
		next_permutation(v.begin(), v.end());
	}
	int t = 7;
	if (n == 3) t = 3;
	if (n == 4) t = 5;
	if (n == 6) t = 6;
	if (n == 7) t = 9;
	assert(getTree(n, 1, all, t));
}

vector<int> sort(vector<int> v) {
	int n = v.size();
	if (n == 1) return v;
	if (n == 2) {
		if (query(v[0], v[1])) return v;
		else {
			swap(v[0], v[1]);
			return v;
		}
	}
	if (n > 5) {
		if (!query(v[0], v[1])) swap(v[0], v[1]);
		if (!query(v[2], v[3])) swap(v[2], v[3]);
		if (!query(v[4], v[5])) swap(v[4], v[5]);
		if (!query(v[0], v[2])) swap(v[0], v[2]), swap(v[1], v[3]);
	}
	int loc = 1;
	while (1) {
		if (query(v[question[n][loc].first], v[question[n][loc].second])) loc *= 2;
		else loc = loc * 2 + 1;
		if (isend[n][loc]) break;
	}
	vector<int> ans;
	int i;
	vector<int> rev(n);
	for (i = 0; i < n; i++) rev[endv[n][loc][i]] = i;
	for (i = 0; i < n; i++) ans.push_back(v[rev[i]]);
	return ans;
}

vector<int> v[31];

std::vector<int> SortWines(int K, std::vector<int> A) {
	init_tree(3);
	init_tree(4);
	int N = A.size(), i;
	for (i = 0; i < N; i++) v[A[i]].push_back(i);
	vector<int> ans(N);
	for (i = 1; i <= 6; i++) {
		if (v[i].empty()) continue;
		v[i] = sort(v[i]);
		for (int j = 0; j < v[i].size(); j++) ans[v[i][j]] = (i - 1) * 4 + j + 1;
	}
	for (i = 0; i < N; i++) if (A[i] > 6) ans[i] = A[i] + 18;
	return ans;
}

Compilation message (stderr)

taster.cpp: In function 'bool getTree(int, int, std::vector<std::vector<int> >, int)':
taster.cpp:42:18: warning: comparison of integer expressions of different signedness: 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   42 |    if (tv.size() > (1 << (t - 1))) continue;
      |        ~~~~~~~~~~^~~~~~~~~~~~~~~~
taster.cpp:43:18: warning: comparison of integer expressions of different signedness: 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   43 |    if (fv.size() > (1 << (t - 1))) continue;
      |        ~~~~~~~~~~^~~~~~~~~~~~~~~~
taster.cpp: In function 'std::vector<int> SortWines(int, std::vector<int>)':
taster.cpp:117:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  117 |   for (int j = 0; j < v[i].size(); j++) ans[v[i][j]] = (i - 1) * 4 + j + 1;
      |                   ~~^~~~~~~~~~~~~

• Subtask 1: 49 / 100