Submission #149739

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

bartender

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

namespace {

using namespace std;

using big = __int128_t;

const int FOUR = 13;
const int THREE = 13;

const int TWELVE = 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;
}

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);
		}
	}
	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 <bits/stdc++.h>

namespace {

using namespace std;

using big = __int128_t;

const int FOUR = 13;
const int THREE = 13;

const int TWELVE = 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;
}

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);
		}
	}
	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:107: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:76: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: 7 / 100