| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 112982 | imsifile | Wine Tasting (FXCUP4_wine) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "bartender.h"
using namespace std;
void BlendWines(int N, int K, vector<int> R, vector<int> &A){
A.resize(N);
for(int i=0; i<N; i++){
if(R[i] > 12) A[i] = R[i]-11;
else A[i] = 1;
}
// 1 ~ 19
}
#include "taster.h"
#include <algorithm>
#include <string>
using namespace std;
int N, ba[22], bcn;
int comp(int a, int b){ // if a<b, 1.
if(a>N || b>N) return a<b;
return Compare(a,b) < 0;
}
vector<string> ss;
void dfs(int ix, int chk, string s){
if(ix==10){
ss.push_back(s);
return;
}
int mi=0;
if(ix>=5) mi=s[ix-5]-'0'+1;
else if(ix) mi=s[ix-1]-'0'+1;
for(int i=mi; i<=9; i++){
if(chk&(1<<i)) continue;
dfs(ix+1, chk|(1<<i), s+char('0'+i));
}
}
int cmd[9999][2]; string res[9999];
int getdepth(vector<string> v, int ix, int req){
if(v.size() <= 1){
if(v.size() == 1) res[ix] = v[0];
return 1;
}
if((int)v.size() > (1<<req)) return 0;
vector<string> v1, v2;
for(int i=0; i<10; i++){
for(int j=i+1; j<10; j++){
v1.clear(), v2.clear();
for(auto &s: v){
if(s[i]<s[j]) v1.push_back(s);
else v2.push_back(s);
}
if(getdepth(v1, ix*2, req-1) && getdepth(v2, ix*2+1, req-1)){
cmd[ix][0]=i, cmd[ix][1]=j;
return 1;
}
}
}
return 0;
}
void ins(int *v, int sz){
int mi=0, mx=sz-1, md, cu=sz;
while(mi<=mx){
md=(mi+mx)/2;
if(comp(v[sz],v[md])) cu=md, mx=md-1;
else mi=md+1;
}
reverse(v+cu, v+sz+1);
reverse(v+cu+1, v+sz+1);
}
void swap2(int *v, int ix1, int ix2){
swap(v[ix1], v[ix2]);
swap(v[ix1+5], v[ix2+5]);
}
void smsort(int *v, int sz){
if(sz == 5){
if(!comp(v[0], v[1])) swap2(v, 0, 1);
if(!comp(v[2], v[3])) swap2(v, 2, 3);
if(!comp(v[0], v[2])) swap2(v, 0, 2), swap2(v, 1, 3);
if(comp(v[2], v[4])){
if(!comp(v[3], v[4])) swap2(v, 3, 4);
// a b cde
if(comp(v[1], v[3])){
if(!comp(v[1], v[2])) swap2(v, 1, 2);
}
else{
swap2(v, 1, 2); swap2(v, 2, 3); // acd b e
if(!comp(v[3], v[4])) swap2(v, 3, 4);
}
}
else{
swap2(v, 3, 4); swap2(v, 2, 3);
if(comp(v[0], v[2])){
// a b ecd
if(comp(v[1], v[3])){
if(!comp(v[1], v[2])) swap2(v, 1, 2);
}
else{
swap2(v, 1, 2); swap2(v, 2, 3); // aec b d
if(!comp(v[3], v[4])) swap2(v, 3, 4);
}
}
else{
swap2(v, 1, 2), swap2(v, 0, 1); // ea b cd
if(!comp(v[2], v[3])){
swap2(v, 2, 3);
if(!comp(v[3], v[4])) swap2(v, 3, 4);
}
}
}
}
if(sz == 10){
for(int i=0; i<5; i++){
if(!comp(v[i],v[i+5])) swap(v[i],v[i+5]);
}
smsort(v,5);
int st=1;
while(cmd[st][0]!=cmd[st][1]){
if(comp(v[cmd[st][0]], v[cmd[st][1]])) st=st*2;
else st=st*2+1;
}
string x = res[st];
for(int i=0; i<9; i++){
int j;
for(j=i; j<10; j++){
if(x[j]==i+'0') break;
}
swap(v[i],v[j]), swap(x[i],x[j]);
}
}
if(sz == 12) smsort(v,10), ins(v,10), ins(v,11);
}
void SortWines(int N_, int K, vector<int> A, vector<int> &R) {
dfs(0,0,"");
getdepth(ss,1,10);
N = N_;
R.resize(N);
if(N <= 12){
for(int i=1; i<=12; i++) ba[i-1]=i;
smsort(ba, 12);
for(int i=0; i<N; i++) R[ba[i]-1]=i+1;
return;
}
for(int i=0; i<N; i++){
if(A[i]==1) ba[bcn++]=i+1;
else R[i]=A[i]+11;
}
smsort(ba, 12);
for(int i=0; i<12; i++) R[ba[i]-1]=i+1;
}