oj.uz

Submission #762606

# Submission time Handle Problem Language Result Execution time Memory
762606 2023-06-21T14:38:29 Z goodbyehanbyeol Wine Tasting (FXCUP4_wine) C++17
49 / 100
 13 ms 19760 KB 
#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;
}

#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

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

# Verdict Execution time Memory Grader output
1 Correct 9 ms 19580 KB Correct
2 Correct 9 ms 19600 KB Correct
3 Correct 8 ms 19588 KB Correct
4 Correct 9 ms 19584 KB Correct
5 Correct 9 ms 19620 KB Correct
6 Correct 9 ms 19584 KB Correct
7 Correct 9 ms 19592 KB Correct
8 Correct 9 ms 19592 KB Correct
9 Correct 9 ms 19584 KB Correct
10 Correct 9 ms 19584 KB Correct
11 Correct 9 ms 19508 KB Correct
12 Correct 9 ms 19592 KB Correct
13 Correct 9 ms 19584 KB Correct
14 Correct 9 ms 19600 KB Correct
15 Correct 9 ms 19576 KB Correct
16 Correct 9 ms 19592 KB Correct
17 Correct 9 ms 19584 KB Correct
18 Correct 9 ms 19592 KB Correct
19 Correct 9 ms 19584 KB Correct
20 Correct 9 ms 19592 KB Correct
21 Correct 9 ms 19568 KB Correct
22 Correct 9 ms 19592 KB Correct
23 Correct 9 ms 19584 KB Correct
24 Correct 12 ms 19676 KB Correct
25 Correct 9 ms 19528 KB Correct
26 Correct 10 ms 19584 KB Correct
27 Correct 9 ms 19744 KB Correct
28 Correct 9 ms 19676 KB Correct
29 Correct 9 ms 19584 KB Correct
30 Correct 9 ms 19660 KB Correct
31 Correct 9 ms 19596 KB Correct
32 Correct 9 ms 19592 KB Correct
33 Correct 9 ms 19584 KB Correct
34 Correct 9 ms 19588 KB Correct
35 Correct 9 ms 19624 KB Correct
36 Correct 9 ms 19672 KB Correct
37 Correct 9 ms 19584 KB Correct
38 Correct 9 ms 19676 KB Correct
39 Correct 9 ms 19684 KB Correct
40 Correct 9 ms 19608 KB Correct
41 Correct 11 ms 19624 KB Correct
42 Correct 12 ms 19560 KB Correct
43 Correct 9 ms 19668 KB Correct
44 Correct 9 ms 19584 KB Correct
45 Correct 9 ms 19584 KB Correct
46 Correct 8 ms 19584 KB Correct
47 Correct 9 ms 19592 KB Correct
48 Correct 9 ms 19584 KB Correct
49 Correct 9 ms 19668 KB Correct
50 Correct 9 ms 19696 KB Correct
51 Correct 9 ms 19584 KB Correct
52 Correct 9 ms 19668 KB Correct
53 Correct 9 ms 19584 KB Correct
54 Correct 9 ms 19516 KB Correct
55 Correct 11 ms 19548 KB Correct
56 Correct 9 ms 19708 KB Correct
57 Correct 9 ms 19564 KB Correct
58 Correct 11 ms 19600 KB Correct
59 Correct 9 ms 19584 KB Correct
60 Correct 9 ms 19592 KB Correct
61 Correct 9 ms 19580 KB Correct
62 Correct 9 ms 19508 KB Correct
63 Correct 9 ms 19584 KB Correct
64 Correct 9 ms 19664 KB Correct
65 Correct 12 ms 19592 KB Correct
66 Correct 11 ms 19672 KB Correct
67 Correct 9 ms 19672 KB Correct
68 Correct 9 ms 19508 KB Correct
69 Correct 9 ms 19592 KB Correct
70 Partially correct 9 ms 19584 KB Wrong
71 Partially correct 9 ms 19592 KB Wrong
72 Partially correct 9 ms 19592 KB Wrong
73 Partially correct 8 ms 19672 KB Wrong
74 Partially correct 9 ms 19584 KB Wrong
75 Partially correct 9 ms 19676 KB Wrong
76 Correct 9 ms 19592 KB Correct
77 Correct 9 ms 19760 KB Correct
78 Correct 9 ms 19592 KB Correct
79 Correct 9 ms 19584 KB Correct
80 Partially correct 9 ms 19592 KB Wrong
81 Partially correct 9 ms 19584 KB Wrong
82 Partially correct 9 ms 19584 KB Wrong
83 Partially correct 9 ms 19584 KB Wrong
84 Partially correct 9 ms 19592 KB Wrong
85 Partially correct 8 ms 19476 KB Wrong
86 Partially correct 8 ms 19496 KB Wrong
87 Partially correct 9 ms 19464 KB Wrong
88 Correct 9 ms 19592 KB Correct
89 Correct 9 ms 19668 KB Correct
90 Correct 9 ms 19592 KB Correct
91 Correct 8 ms 19592 KB Correct
92 Partially correct 12 ms 19584 KB Wrong
93 Partially correct 9 ms 19656 KB Wrong
94 Partially correct 11 ms 19440 KB Wrong
95 Partially correct 9 ms 19448 KB Wrong
96 Partially correct 9 ms 19592 KB Wrong
97 Partially correct 9 ms 19592 KB Wrong
98 Partially correct 8 ms 19584 KB Wrong
99 Partially correct 9 ms 19540 KB Wrong
100 Partially correct 9 ms 19712 KB Wrong
101 Partially correct 9 ms 19584 KB Wrong
102 Partially correct 11 ms 19592 KB Wrong
103 Correct 9 ms 19584 KB Correct
104 Correct 9 ms 19588 KB Correct
105 Correct 9 ms 19672 KB Correct
106 Correct 9 ms 19672 KB Correct
107 Partially correct 9 ms 19576 KB Wrong
108 Partially correct 9 ms 19628 KB Wrong
109 Partially correct 9 ms 19588 KB Wrong
110 Partially correct 9 ms 19584 KB Wrong
111 Partially correct 9 ms 19584 KB Wrong
112 Partially correct 9 ms 19584 KB Wrong
113 Partially correct 9 ms 19584 KB Wrong
114 Partially correct 11 ms 19552 KB Wrong
115 Partially correct 9 ms 19672 KB Wrong
116 Partially correct 9 ms 19584 KB Wrong
117 Partially correct 13 ms 19592 KB Wrong
118 Partially correct 9 ms 19584 KB Wrong
119 Partially correct 9 ms 19584 KB Wrong
120 Partially correct 9 ms 19592 KB Wrong