#include "bartender.h"
using namespace std;
typedef long long lld;
static int seq[22], scn;
static lld fac=1, su, s4, s3;
// 4 1 3 2 5 => 0 0 1 1 4 => 0*5*4*3*2 + 0*5*4*3 + 1*5*4 + 1*5 + 4 => a * 3^12 + b
void BlendWines(int N, int K, vector<int> R, vector<int> &A){
if(N <= 12){
for(int i=0; i<N; i++) A.push_back(1);
return;
}
for(int i=0; i<N; i++){
if(R[i] > 12) seq[scn++] = R[i];
}
for(int i=1; i<=scn; i++) fac*=i;
for(int i=0; i<scn; i++){
int c=0;
for(int j=0; j<i; j++){
if(seq[i]>seq[j]) c++;
}
su += fac*c;
fac /= i+2;
}
s4 = su/531441, s3 = su%531441;
for(int i=0; i<N; i++){
if(R[i] <= 12) A.push_back(s3%3+1), s3/=3;
else A.push_back(s4%4+4), s4/=4;
}
}
#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);
}
typedef long long lld;
static lld su, s4, s3, p4=1, p3=1;
static int seq[22], scn, fs[22];
void SortWines(int N_, int K, vector<int> A, vector<int> &R) {
dfs(0,0,"");
getdepth(ss,1,10);
N = N_;
if(N <= 12){
for(int i=1; i<=12; i++) ba[i-1]=i;
smsort(ba, 12);
R.resize(N);
for(int i=0; i<N; i++) R[ba[i]-1]=i+1;
return;
}
for(int i=0; i<N; i++){
if(A[i]<=3) s3 += (A[i]-1)*p3, p3*=3, ba[bcn++]=i+1;
else s4 += (A[i]-4)*p4, p4*=4, scn++;
}
su = s4*531441 + s3;
smsort(ba, 12);
R.resize(N);
for(int i=0; i<12; i++) R[ba[i]-1]=i+1;
for(int i=scn-1; i>=0; i--) fs[i]=su%(i+1), su/=i+1;
for(int i=0; i<scn; i++){
int a;
for(a=scn-1; a>=0; a--){
if(!fs[a]) break;
}
seq[a]=13+i;
for(int j=a; j<scn; j++) fs[j]--;
}
scn=0;
for(int i=0; i<N; i++){
if(A[i]>3) R[i]=seq[scn++];
}
}
Compilation message
/tmp/ccGgdzNW.o: In function `main':
grader_b.cpp:(.text.startup+0x1a1): undefined reference to `BlendWines(int, std::vector<int, std::allocator<int> >)'
collect2: error: ld returned 1 exit status
/tmp/ccleXR0F.o: In function `main':
grader_t.cpp:(.text.startup+0x1b4): undefined reference to `SortWines(int, std::vector<int, std::allocator<int> >)'
collect2: error: ld returned 1 exit status
