#include "bartender.h"
std::vector<int> BlendWines(int K, std::vector<int> R){
int N = R.size();
std::vector<int> a(N,1), b(N);
for (int i = 0; i < N; i++){
b[i] = 7 - i % 7;
}
b.back() = 8;
for (int i = 0; i < N; i++) a[i] = b[R[i] - 1];
return a;
}
#include "taster.h"
#include <algorithm>
#include <vector>
#include <map>
using namespace std;
int n = 5;
map<vector<int>, int> chk;
map<vector<int>, pair<int, int> > wow;
int c[6][6]; pair<int, int> h[36];
int minComp(vector<int> choose)
{
sort(choose.begin(), choose.end());
if (chk.count( choose )) return chk[choose ];
int& r = chk[choose];
int s[6], e[6];
for (int k = 0; k < n; k++){
s[k] = h[choose[k]].first;
e[k] = h[choose[k]].second;
}
int p[6];
for (int k = 0; k < n; k++){
p[k] = k;
}
int u = 0;
do{
int c = 0;
int v[6];
if (c == 0) for (int k = 0; k < n; k++){
if (s[k] <= p[k] && p[k] <= e[k]) c++;
else break;
}
if (c == n) ++u;
} while (next_permutation(p, p + n));
if (u == 0) r = 1000;
else if (u == 1) r = 0;
else{
auto& w = wow[choose];
r = 1000;
for (int k = 0; k < n; k++){
int last = choose[k];
for (int p = s[k]; p < e[k]; p++){
int u = c[p + 1][e[k]];
int v = c[s[k]][p];
choose[k] = u; int a = minComp(choose) + 1;
choose[k] = v; int b = minComp(choose) + 1;
if (r > max(a, b)){
r = max(a, b);
w = { last, p };
}
}
choose[k] = last;
}
}
return r;
}
std::vector<int> SortWines(int K, std::vector<int> A) {
for (int i = 0, u = 0; i < 6; i++){
for (int j = i; j < 6; j++){
c[i][j] = u;
h[u] = { i,j };
u++;
}
}
int N = A.size();
vector<int> b(N);
for (int i = 0; i < N; i++) b[i] = 7 - i % 7;
b.back() = 8;
vector<int> pos[10];
for (int i = 0; i < N; i++) pos[b[i]].push_back(i);
vector<int> P(N);
vector<int> one;
for (int i = 0; i < N; i++) if (A[i] == 1) one.push_back(i);
if (one.size() == 1){
P[one[0]] = pos[1][0];
}
if (one.size() == 2){
if (Compare(one[0], one[1]) == -1){
P[one[0]] = pos[1][0];
P[one[1]] = pos[1][1];
}
else{
P[one[0]] = pos[1][1];
P[one[1]] = pos[1][0];
}
}
if (one.size() == 3){
if (Compare(one[0], one[1]) == -1){
if (Compare(one[1], one[2]) == -1){
P[one[0]] = pos[1][0];
P[one[1]] = pos[1][1];
P[one[2]] = pos[1][2];
}
else{
if (Compare(one[0], one[2]) == -1){
P[one[0]] = pos[1][0];
P[one[1]] = pos[1][2];
P[one[2]] = pos[1][1];
}
else{
P[one[0]] = pos[1][2];
P[one[1]] = pos[1][0];
P[one[2]] = pos[1][1];
}
}
}
else{
if (Compare(one[2], one[1]) == -1){
P[one[0]] = pos[1][2];
P[one[1]] = pos[1][1];
P[one[2]] = pos[1][0];
}
else{
if (Compare(one[0], one[2]) == -1){
P[one[0]] = pos[1][1];
P[one[1]] = pos[1][0];
P[one[2]] = pos[1][2];
}
else{
P[one[0]] = pos[1][1];
P[one[1]] = pos[1][2];
P[one[2]] = pos[1][0];
}
}
}
}
for (int k = 2; k <= 8; k++){
vector<int> alc;
for (int i = 0; i < N; i++) if (A[i] == k) alc.push_back(i);
if (alc.empty()) continue;
if (alc.size() == 1){
P[alc[0]] = pos[k][0];
}
if (alc.size() == 2){
if (Compare(alc[0], one[0]) == -1){
P[alc[0]] = pos[k][0];
P[alc[1]] = pos[k][1];
}
else{
P[alc[0]] = pos[k][1];
P[alc[1]] = pos[k][0];
}
}
if (alc.size() >= 3){
n = alc.size();
vector<int> choose(n, c[0][n - 1]);
int u = minComp(choose);
while (1){
int s[6], e[6];
for (int k = 0; k < n; k++){
s[k] = h[choose[k]].first;
e[k] = h[choose[k]].second;
}
int p[6],q[6];
for (int k = 0; k < n; k++){
p[k] = k;
}
int u = 0;
do{
int c = 0;
int v[6];
if (c == 0) for (int k = 0; k < n; k++){
if (s[k] <= p[k] && p[k] <= e[k]) c++;
else break;
}
if (c == n){
++u;
for (int k = 0; k < n; k++) q[k] = p[k];
}
} while (next_permutation(p, p + n));
if (u <= 1){
for (int k = 0; k < n; k++){
P[alc[k]] = pos[k][q[k]];
}
}
else{
auto& w = wow[choose];
int last = w.first;
int p = w.second;
for (int k = 0; k < n; k++) if (choose[k] == last){
if (Compare(alc[k], one[p]) == -1){
e[k] = p;
}
else{
s[k] = p + 1;
}
choose[k] = c[s[k]][e[k]];
break;
}
}
}
}
}
vector<int> R(N);
for (int i = 0; i < N; i++) R[P[i]] = i + 1;
return R;
}
Compilation message
taster.cpp: In function 'int minComp(std::vector<int>)':
taster.cpp:32:7: warning: unused variable 'v' [-Wunused-variable]
int v[6];
^
taster.cpp: In function 'std::vector<int> SortWines(int, std::vector<int>)':
taster.cpp:177:10: warning: unused variable 'v' [-Wunused-variable]
int v[6];
^
taster.cpp:161:8: warning: unused variable 'u' [-Wunused-variable]
int u = minComp(choose);
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
780 KB |
Correct |
| 2 |
Correct |
10 ms |
680 KB |
Correct |
| 3 |
Incorrect |
8 ms |
644 KB |
Wrong |
| 4 |
Halted |
0 ms |
0 KB |
- |
