#include "bartender.h"
using namespace std;
vector<int> BlendWines(int K, vector<int> R){
int N = R.size();
vector<int> A(N);
if(N <= K/2){
for(int i = 0; i < N; i++) A[i] = (R[i] - 1) % 9 + 1;
return A;
}
for(int i = 0; i < N; i++) A[i] = (R[i] == N-1 ? 10 : (R[i]-1) % 9 + 1);
return A;
}
#include "taster.h"
#include <bits/stdc++.h>
#define all(v) (v).begin(),(v).end()
using namespace std;
vector<int> g[31];
vector<int> alc;
int cmp[31][31], N;
vector<int> bf(){
for(int i = 0; i < N; i++){
for(int j = i + 1; j < N; j++){
cmp[i][j] = Compare(i, j);
cmp[j][i] = -cmp[i][j];
}
}
vector<int> R(N), I(N);
iota(all(I), 0);
sort(all(I), [](int u, int v){return cmp[u][v] == -1;});
for(int i = 0; i < N; i++){
R[I[i]] = i + 1;
}
return R;
}
vector<int> SortWines(int K, vector<int> A) {
//cout << "asdf\n";
N = A.size();
alc = A;
vector<int> R(N);
for(int i = 0; i < N; i++) g[A[i]].push_back(i);
if(N <= K/2){
return bf();
}
vector<vector<int>> Pms;
vector<int> P[3];
vector<int> gmr;
int r = 0;
for(int i = 0; i < 3; i++){
P[i].resize(g[i+1].size());
r += g[i+1].size();
iota(all(P[i]), 0);
copy(all(g[i+1]), back_inserter(gmr));
}
//for(int u : gmr) cout << u << ' '; cout << '\n';
do{
do{
do{
Pms.emplace_back();
for(int i = 0; i < 3; i++){
for(int j = 0; j < P[i].size(); j++) Pms.back().push_back(P[i][j] * 1000 + i);
}
}while(next_permutation(all(P[2])));
}while(next_permutation(all(P[1])));
}while(next_permutation(all(P[0])));
//cout << "permdict " << Pms.size() << "\n";
vector<vector<int>> sel[2];
int dep = 0;
while(Pms.size() > 1){
int diff = INT_MAX, di, dj;
for(int i = 0; i < r; i++){
for(int j = i + 1; j < r; j++){
int ldiff = 0;
for(vector<int> &p : Pms){
if(p[i] < p[j]) ldiff += 1;
else ldiff -= 1;
}
if(abs(ldiff) < diff){
diff = abs(ldiff);
di = i;
dj = j;
}
}
}
sel[0].clear();
sel[1].clear();
for(vector<int>& p : Pms){
sel[p[di] < p[dj]].push_back(p);
}
++dep;
//cout << "decision tree " << dep << " : " << sel[0].size() << ' ' << sel[1].size() << '\n';
bool s = (Compare(gmr[di], gmr[dj]) == -1);
Pms = sel[s];
sel[!s].clear();
}
for(int &q : Pms.back()) q /= 1000;
int cur = 0;
for(int i = 1; i <= 3; i++){
vector<int> tmp(g[i].size());
for(int j = 0; j < g[i].size(); j++) tmp[Pms.back()[cur + j]] = g[i][j];
g[i] = tmp;
cur += g[i].size();
}
for(int i = 4; i <= K; i++){
vector<vector<int>> ps;
int r = g[i].size();
vector<int> U(r);
iota(all(U), 0);
do{
vector<int> cU = U;
ps.push_back(cU);
}while(next_permutation(all(U)));
vector<vector<int>> sel[2];
int dep = 0;
while(ps.size() > 1){
int diff = INT_MAX, di, dj;
for(int i = 0; i < r; i++){
for(int j = 1; j < r; j++){
int ldiff = 0;
for(vector<int> &p : ps){
if(p[i] < j) ldiff += 1;
else ldiff -= 1;
}
if(abs(ldiff) < diff){
diff = abs(ldiff);
di = i;
dj = j;
}
}
}
sel[0].clear();
sel[1].clear();
for(vector<int>& p : ps){
sel[p[di] < dj].push_back(p);
}
++dep;
//cout << "decision tree " << dep << " : " << sel[0].size() << ' ' << sel[1].size() << '\n';
bool s = (Compare(g[i][di], g[1][dj]) == -1);
ps = sel[s];
sel[!s].clear();
}
vector<int> tmp(r);
for(int j = 0; j < r; j++) tmp[ps.back()[j]] = g[i][j];
g[i] = tmp;
}
for(int i = 1; i <= K; i++){
for(int j = 0; j < g[i].size(); j++){
R[g[i][j]] = j * 9 + i;
}
}
if(g[10].size()) R[g[10][0]] = N-1;
return R;
}
Compilation message
taster.cpp: In function 'std::vector<int> SortWines(int, std::vector<int>)':
taster.cpp:51:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j = 0; j < P[i].size(); j++) Pms.back().push_back(P[i][j] * 1000 + i);
~~^~~~~~~~~~~~~
taster.cpp:92:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j = 0; j < g[i].size(); j++) tmp[Pms.back()[cur + j]] = g[i][j];
~~^~~~~~~~~~~~~
taster.cpp:139:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j = 0; j < g[i].size(); j++){
~~^~~~~~~~~~~~~
taster.cpp:126:15: warning: 'dj' may be used uninitialized in this function [-Wmaybe-uninitialized]
sel[p[di] < dj].push_back(p);
taster.cpp:108:24: warning: 'di' may be used uninitialized in this function [-Wmaybe-uninitialized]
int diff = INT_MAX, di, dj;
^~
taster.cpp:61:27: warning: 'dj' may be used uninitialized in this function [-Wmaybe-uninitialized]
int diff = INT_MAX, di, dj;
^~
taster.cpp:61:23: warning: 'di' may be used uninitialized in this function [-Wmaybe-uninitialized]
int diff = INT_MAX, di, dj;
^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
772 KB |
Correct |
| 2 |
Correct |
10 ms |
772 KB |
Correct |
| 3 |
Correct |
8 ms |
692 KB |
Correct |
| 4 |
Incorrect |
9 ms |
872 KB |
Wrong |
| 5 |
Halted |
0 ms |
0 KB |
- |
