Submission #150343

#	Time	Username	Problem	Language	Result	Execution time	Memory
150343		USA1 (#200)	Wine Tasting (FXCUP4_wine)	C++17	100 / 100	11 ms	1148 KiB

bartender

#include "taster.h"
#include "bartender.h"
#include <bits/stdc++.h>

namespace {

using namespace std;

using big = __int128_t;

const int FOUR = 4;
const int THREE = 3;

const int TWELVE = 12;

int ncalls = 0;

big ep(int n, vector<int> perm){
	assert((int)perm.size() == n);
	big res = 0;
	for(int i = 0; i < n; i++){
		res *= (n - i);
		res += perm[i];
		for(int j = i+1; j < n; j++){
			if(perm[j] > perm[i]) perm[j] -= 1;
		}
	}
	return res;
}

vector<int> dp(int n, big val){
	vector<int> perm(n, 0);
	for(int i = n-1; i >= 0; i--){
		int ind = val % (n - i);
		val /= (n - i);
		perm[i] = ind;
		for(int j = i + 1; j < n; j++){
			if(perm[j] >= perm[i]) perm[j] += 1;
		}
	}
	return perm;
}

vector<int> encode_permutation(vector<int> perm, int fours, int threes){
	big a = 1;
	for(int i = 1; i <= fours; i++) a *= big(i);
	big c = 1;
	for(int i = 0; i < fours; i++) c *= FOUR;
	for(int i = 0; i < threes; i++) c *= THREE;
	assert(a <= c);

	assert(dp(fours, ep(fours, perm)) == perm);
	big val = ep(fours, perm);
	vector<int> z;
	for(int i = 0; i < threes; i++){
		z.push_back(int(val % THREE)); val /= THREE;
	}
	for(int i = 0; i < fours; i++){
		z.push_back(int(val % FOUR)); val /= FOUR;
	}
	assert(val == 0);
	reverse(z.begin(), z.end());
	return z;
}


vector<int> decode_permutation(vector<int> info, int fours, int threes){
	int n = (int)info.size();
	assert(n == fours + threes);
	big r = 0;
	for(int i = 0; i < fours; i++) r = r * FOUR + info[i];
	for(int i = 0; i < threes; i++) r = r * THREE + info[fours + i];

	vector<int> perm = dp(fours, r);
	assert(ep(fours, perm) == r);
	return perm;
}

vector<int> blendwines(int k, vector<int> r){
	for(int& x : r) x -= 1;
	int n = (int)r.size();
	int num_big = min(TWELVE, n); // num_big
	int num_small = n - num_big;
	vector<int> small_perm;
	for(int a : r){
		if(a < num_small) small_perm.push_back(a);
	}
	assert((int)small_perm.size() == num_small);

	vector<int> info = encode_permutation(small_perm, num_small, num_big);
	assert(decode_permutation(info, num_small, num_big) == small_perm);

	int j = 0;
	vector<int> a(n);
	for(int i = 0; i < n; i++){
		if(r[i] < num_small){
			a[i] = THREE + 1 + info[j];
			j += 1;
		}
	}
	for(int i = 0; i < n; i++){
		if(r[i] >= num_small){
			a[i] = 1 + info[j];
			j += 1;
		}
	}
	return a;
}

bool cmp(int x, int y){
	ncalls += 1;
	return (ncalls <= 30) ? (Compare(x, y) == -1) : false;
}

vector<int> merge_sort(vector<int> x){
	if(x.size() <= 1) return x;
	vector<int> a, b;
	int n = (int)x.size();
	for(int i = 0; i < n/2; i++) a.push_back(x[i]);
	for(int i = n/2; i < n; i++) b.push_back(x[i]);
	a = merge_sort(a);
	b = merge_sort(b);
	int i = 0;
	int j = 0;
	vector<int> res;
	while(i < (int)a.size() && j < (int)b.size()){
		if(cmp(a[i], b[j])){
			res.push_back(a[i]);
			i += 1;
		} else {
			res.push_back(b[j]);
			j += 1;
		}
	}
	for(int k = i; k < (int)a.size(); k++) res.push_back(a[k]);
	for(int k = j; k < (int)b.size(); k++) res.push_back(b[k]);
	return res;
}

vector<int> merge_insertion_sort(vector<int> x){
	if(x.size() <= 1) return x;
	for(int i = 0; i + 1 < (int)x.size(); i += 2){
		if(!cmp(x[i], x[i+1])){
			swap(x[i], x[i+1]);
		}
	}
	vector<int> smalls;
	for(int i = 0; i + 1 < (int)x.size(); i += 2){
		smalls.push_back(x[i+1]);
	}
	smalls = merge_insertion_sort(smalls);
	for(int i = 0; i + 1 < (int)x.size(); i += 2){
		if(smalls.front() == x[i+1]){
			smalls.insert(smalls.begin(), x[i]);
		}
	}
	vector<int> y;
	for(int b = 2; b < (int)smalls.size(); b++){
		for(int i = 0; i + 1 < (int)x.size(); i += 2){
			if(smalls[b] == x[i+1]){
				y.push_back(x[i]);
			}
		}
	}
	if((int)x.size() & 1){
		y.push_back(x.back());
	}
	vector<int> arr = {4, 3, 6, 5, 12, 11, 10, 9, 8, 7, 22, 21, 20, 19, 18, 17, 16, 15, 14, 13};
	for(int v : arr){
		v -= 3;
		if(v >= (int)y.size()) continue;
		int el = y[v];

		int pos = (int)smalls.size();
		for(int i = 0; i + 1 < (int)x.size(); i += 2){
			if(el == x[i]){
				for(int j = 0; j < (int)smalls.size(); j++){
					if(smalls[j] == x[i+1]) pos = j;
				}
			}
		}
		int s = -1;
		int e = pos;
		while(s + 1 < e){
			int mid = (s + e) / 2;
			if(cmp(el, smalls[mid])){
				e = mid;
			} else {
				s = mid;
			}
		}

		smalls.insert(smalls.begin() + e, el);
	}
	assert(smalls.size() == x.size());
	return smalls;
}

vector<int> sortwines(int k, vector<int> a) {
	int n = (int)a.size();
	int num_big = min(TWELVE, n); // num_big
	int num_small = n - num_big;
	vector<int> info;
	for(int i = 0; i < n; i++) if(a[i] > THREE) info.push_back(a[i] - THREE - 1);
	assert((int)info.size() == num_small);
	for(int i = 0; i < n; i++) if(a[i] <= THREE) info.push_back(a[i] - 1);
	assert((int)info.size() == n);

	vector<int> perm = decode_permutation(info, num_small, num_big);
	assert(encode_permutation(perm, num_small, num_big) == info);
	int j = 0;
	vector<int> r(n, -1);

	vector<int> unknowns;
	for(int i = 0; i < n; i++){
		if(a[i] > THREE){
			r[i] = perm[j];
			j += 1;
		} else {
			unknowns.push_back(i);
		}
	}
	assert((int)unknowns.size() == num_big);
	mt19937 mt(time(0));
	shuffle(unknowns.begin(), unknowns.end(), mt);
	unknowns = merge_insertion_sort(unknowns);
	for(int i = 0; i < (int)unknowns.size(); i++){
		r[unknowns[i]] = i + num_small;
	}
	for(int& x : r) x += 1;
	return r;
}
}

vector<int> BlendWines(int k, vector<int> r){
	return blendwines(k, r);
}

taster

#include "taster.h"
#include "bartender.h"
#include <bits/stdc++.h>

namespace {

using namespace std;

using big = __int128_t;

const int FOUR = 4;
const int THREE = 3;

const int TWELVE = 12;

int ncalls = 0;

big ep(int n, vector<int> perm){
	assert((int)perm.size() == n);
	big res = 0;
	for(int i = 0; i < n; i++){
		res *= (n - i);
		res += perm[i];
		for(int j = i+1; j < n; j++){
			if(perm[j] > perm[i]) perm[j] -= 1;
		}
	}
	return res;
}

vector<int> dp(int n, big val){
	vector<int> perm(n, 0);
	for(int i = n-1; i >= 0; i--){
		int ind = val % (n - i);
		val /= (n - i);
		perm[i] = ind;
		for(int j = i + 1; j < n; j++){
			if(perm[j] >= perm[i]) perm[j] += 1;
		}
	}
	return perm;
}

vector<int> encode_permutation(vector<int> perm, int fours, int threes){
	big a = 1;
	for(int i = 1; i <= fours; i++) a *= big(i);
	big c = 1;
	for(int i = 0; i < fours; i++) c *= FOUR;
	for(int i = 0; i < threes; i++) c *= THREE;
	assert(a <= c);

	assert(dp(fours, ep(fours, perm)) == perm);
	big val = ep(fours, perm);
	vector<int> z;
	for(int i = 0; i < threes; i++){
		z.push_back(int(val % THREE)); val /= THREE;
	}
	for(int i = 0; i < fours; i++){
		z.push_back(int(val % FOUR)); val /= FOUR;
	}
	assert(val == 0);
	reverse(z.begin(), z.end());
	return z;
}


vector<int> decode_permutation(vector<int> info, int fours, int threes){
	int n = (int)info.size();
	assert(n == fours + threes);
	big r = 0;
	for(int i = 0; i < fours; i++) r = r * FOUR + info[i];
	for(int i = 0; i < threes; i++) r = r * THREE + info[fours + i];

	vector<int> perm = dp(fours, r);
	assert(ep(fours, perm) == r);
	return perm;
}

vector<int> blendwines(int k, vector<int> r){
	for(int& x : r) x -= 1;
	int n = (int)r.size();
	int num_big = min(TWELVE, n); // num_big
	int num_small = n - num_big;
	vector<int> small_perm;
	for(int a : r){
		if(a < num_small) small_perm.push_back(a);
	}
	assert((int)small_perm.size() == num_small);

	vector<int> info = encode_permutation(small_perm, num_small, num_big);
	assert(decode_permutation(info, num_small, num_big) == small_perm);

	int j = 0;
	vector<int> a(n);
	for(int i = 0; i < n; i++){
		if(r[i] < num_small){
			a[i] = THREE + 1 + info[j];
			j += 1;
		}
	}
	for(int i = 0; i < n; i++){
		if(r[i] >= num_small){
			a[i] = 1 + info[j];
			j += 1;
		}
	}
	return a;
}

bool cmp(int x, int y){
	ncalls += 1;
	return (ncalls <= 30) ? (Compare(x, y) == -1) : false;
}

vector<int> merge_sort(vector<int> x){
	if(x.size() <= 1) return x;
	vector<int> a, b;
	int n = (int)x.size();
	for(int i = 0; i < n/2; i++) a.push_back(x[i]);
	for(int i = n/2; i < n; i++) b.push_back(x[i]);
	a = merge_sort(a);
	b = merge_sort(b);
	int i = 0;
	int j = 0;
	vector<int> res;
	while(i < (int)a.size() && j < (int)b.size()){
		if(cmp(a[i], b[j])){
			res.push_back(a[i]);
			i += 1;
		} else {
			res.push_back(b[j]);
			j += 1;
		}
	}
	for(int k = i; k < (int)a.size(); k++) res.push_back(a[k]);
	for(int k = j; k < (int)b.size(); k++) res.push_back(b[k]);
	return res;
}

vector<int> merge_insertion_sort(vector<int> x){
	if(x.size() <= 1) return x;
	for(int i = 0; i + 1 < (int)x.size(); i += 2){
		if(!cmp(x[i], x[i+1])){
			swap(x[i], x[i+1]);
		}
	}
	vector<int> smalls;
	for(int i = 0; i + 1 < (int)x.size(); i += 2){
		smalls.push_back(x[i+1]);
	}
	smalls = merge_insertion_sort(smalls);
	for(int i = 0; i + 1 < (int)x.size(); i += 2){
		if(smalls.front() == x[i+1]){
			smalls.insert(smalls.begin(), x[i]);
		}
	}
	vector<int> y;
	for(int b = 2; b < (int)smalls.size(); b++){
		for(int i = 0; i + 1 < (int)x.size(); i += 2){
			if(smalls[b] == x[i+1]){
				y.push_back(x[i]);
			}
		}
	}
	if((int)x.size() & 1){
		y.push_back(x.back());
	}
	vector<int> arr = {4, 3, 6, 5, 12, 11, 10, 9, 8, 7, 22, 21, 20, 19, 18, 17, 16, 15, 14, 13};
	for(int v : arr){
		v -= 3;
		if(v >= (int)y.size()) continue;
		int el = y[v];

		int pos = (int)smalls.size();
		for(int i = 0; i + 1 < (int)x.size(); i += 2){
			if(el == x[i]){
				for(int j = 0; j < (int)smalls.size(); j++){
					if(smalls[j] == x[i+1]) pos = j;
				}
			}
		}
		int s = -1;
		int e = pos;
		while(s + 1 < e){
			int mid = (s + e) / 2;
			if(cmp(el, smalls[mid])){
				e = mid;
			} else {
				s = mid;
			}
		}

		smalls.insert(smalls.begin() + e, el);
	}
	assert(smalls.size() == x.size());
	return smalls;
}

vector<int> sortwines(int k, vector<int> a) {
	int n = (int)a.size();
	int num_big = min(TWELVE, n); // num_big
	int num_small = n - num_big;
	vector<int> info;
	for(int i = 0; i < n; i++) if(a[i] > THREE) info.push_back(a[i] - THREE - 1);
	assert((int)info.size() == num_small);
	for(int i = 0; i < n; i++) if(a[i] <= THREE) info.push_back(a[i] - 1);
	assert((int)info.size() == n);

	vector<int> perm = decode_permutation(info, num_small, num_big);
	assert(encode_permutation(perm, num_small, num_big) == info);
	int j = 0;
	vector<int> r(n, -1);

	vector<int> unknowns;
	for(int i = 0; i < n; i++){
		if(a[i] > THREE){
			r[i] = perm[j];
			j += 1;
		} else {
			unknowns.push_back(i);
		}
	}
	assert((int)unknowns.size() == num_big);
	mt19937 mt(time(0));
	shuffle(unknowns.begin(), unknowns.end(), mt);
	unknowns = merge_insertion_sort(unknowns);
	for(int i = 0; i < (int)unknowns.size(); i++){
		r[unknowns[i]] = i + num_small;
	}
	for(int& x : r) x += 1;
	return r;
}
}

vector<int> SortWines(int k, vector<int> r){
	return sortwines(k, r);
}

Compilation message (stderr)

bartender.cpp:199:13: warning: 'std::vector<int> {anonymous}::sortwines(int, std::vector<int>)' defined but not used [-Wunused-function]
 vector<int> sortwines(int k, vector<int> a) {
             ^~~~~~~~~

taster.cpp:79:13: warning: 'std::vector<int> {anonymous}::blendwines(int, std::vector<int>)' defined but not used [-Wunused-function]
 vector<int> blendwines(int k, vector<int> r){
             ^~~~~~~~~~

• Subtask 1: 100 / 100