Submission #148027

#	Time	Username	Problem	Language	Result	Execution time	Memory
148027		imsifile	Wine Tasting (FXCUP4_wine)	C++17	100 / 100	259 ms	1592 KiB

bartender

#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
 
vector<int> BlendWines(int K, vector<int> R){
	int N=R.size();
	vector<int> A;
	if(N <= 12){
		for(int i=0; i<N; i++) A.push_back(1);
		return A;
	}
	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;
	}
	return A;
}

taster

#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-1,b-1) < 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];
 
vector<int> SortWines(int K, vector<int> A) {
	dfs(0,0,"");
	getdepth(ss,1,10);

	vector<int> R;
	N = A.size();
	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 R;
	}
	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++];
	}
	return R;
}

• Subtask 1: 100 / 100