#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;
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;
| ~~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
19588 KB |
Correct |
| 2 |
Correct |
9 ms |
19592 KB |
Correct |
| 3 |
Incorrect |
9 ms |
19584 KB |
Wrong |
| 4 |
Halted |
0 ms |
0 KB |
- |
