#include "bartender.h"
#include <bits/stdc++.h>
using namespace std;
const int LARGESTS_FILLED_UNTIL = 6;
int fill_largests(int K, vector<int>& R, vector<int>& magic, vector<int>& A, int pos[]) {
int N = R.size();
int cur_num = N;
int cur_fill = K;
int prv_magic = -1;
while (cur_fill >= LARGESTS_FILLED_UNTIL && cur_num >= 1) {
if (magic[pos[cur_num]] >= prv_magic) {
A[pos[cur_num]] = cur_fill;
prv_magic = magic[pos[cur_num]];
cur_num--;
} else {
prv_magic = magic[pos[cur_num]];
cur_fill--;
}
}
return cur_num;
}
vector<int> BlendWines(int K, vector<int> R) {
srand(882);
int N = R.size();
int pos[35] = {};
for (int i = 0; i < N; i++) {
pos[R[i]] = i;
}
vector<int> magic;
for (int i = 0; i < N; i++) {
magic.push_back(i);
}
random_shuffle(magic.begin(), magic.end());
vector<int> A(N, 0);
int unfilled_n = fill_largests(K, R, magic, A, pos);
int filled_until = 0;
for (int i = 1; i < LARGESTS_FILLED_UNTIL; i++) {
int unfilled_cnt = (unfilled_n - filled_until);
int group_size = min(unfilled_cnt, 5);
if ((6 - i) * 4 >= unfilled_cnt) {
group_size = min(group_size, 4);
}
for (int j = filled_until + 1; j <= filled_until + group_size; j++) {
A[pos[j]] = i;
}
filled_until += group_size;
}
/*
for (int i = 0; i < N; i++) {
printf("%2d ", A[i]);
}
printf("\n");
*/
return A;
}
#include "taster.h"
#include <bits/stdc++.h>
using namespace std;
const int LARGESTS_FILLED_UNTIL = 6;
int handle_largests(int K, vector<int>& A, vector<int>& magic, vector<int>& R) {
int N = A.size();
int next_num = N;
for (int filled_as = K; filled_as >= LARGESTS_FILLED_UNTIL; filled_as--) {
vector<pair<int, int> > filled_bingo;
for (int i = 0; i < N; i++) {
if (A[i] == filled_as) {
filled_bingo.push_back(make_pair(magic[i], i));
}
}
sort(filled_bingo.begin(), filled_bingo.end());
for (int i = 0; i < filled_bingo.size(); i++) {
R[filled_bingo[i].second] = next_num--;
}
}
return next_num;
}
int cmp_cnt = 0;
bool cmp(int u, int v) {
cmp_cnt++;
return Compare(u, v) == -1;
}
void handle_smallests(vector<int>& A, vector<int>& R) {
int N = A.size();
int next_num = 1;
for (int filled_as = 1; filled_as < LARGESTS_FILLED_UNTIL; filled_as++) {
vector<int> filled_bingo;
for (int i = 0; i < N; i++) {
if (A[i] == filled_as) {
filled_bingo.push_back(i);
}
}
make_heap(filled_bingo.begin(), filled_bingo.end(), cmp);
sort_heap(filled_bingo.begin(), filled_bingo.end(), cmp);
for (int i = 0; i < filled_bingo.size(); i++) {
R[filled_bingo[i]] = next_num++;
}
}
}
vector<int> SortWines(int K, vector<int> A) {
srand(882);
int N = A.size();
vector<int> magic;
for (int i = 0; i < N; i++) {
magic.push_back(i);
}
random_shuffle(magic.begin(), magic.end());
vector<int> R(N, 0);
handle_largests(K, A, magic, R);
handle_smallests(A, R);
/*
for (int i = 0; i < N; i++) {
printf("%2d ", R[i]);
}
printf("\n");
*/
return R;
}
