Submission #149996

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
149996	2019-09-01T07:31:05 Z	Ian and 2-bit memory(#3648, percywtc, nhho, ulna)	Wine Tasting (FXCUP4_wine)	C++17	Compilation error	0 ms	0 KB

bartender

#include "bartender.h"
#include <bits/stdc++.h>
using namespace std;

const int LARGESTS_FILLED_UNTIL = 5;
const int RAND_SEED = 689;

int fill_largests(int K, vector<int>& R, vector<int>& magic, vector<int>& A, int pos[]) {
	int N = R.size();

	int cur_num = N;
	int cur_fill = K;
	int prv_magic = -1;

	while (cur_fill >= LARGESTS_FILLED_UNTIL && cur_num >= 1) {
		if (magic[pos[cur_num]] >= prv_magic) {
			A[pos[cur_num]] = cur_fill;
			prv_magic = magic[pos[cur_num]];
			cur_num--;
		} else {
			prv_magic = magic[pos[cur_num]];
			cur_fill--;
		}
	}

	return cur_num;
}

vector<int> BlendWines(int K, vector<int> R) {
	int N = R.size();

	srand(RAND_SEED);
	vector<int> magic;
	for (int i = 0; i < N; i++) {
		magic.push_back(i);
	}
	random_shuffle(magic.begin(), magic.end());

	int pos[35] = {};
	for (int i = 0; i < N; i++) {
		pos[R[i]] = i;
	}

	vector<int> A(N, 0);

	int unfilled_n = fill_largests(K, R, magic, A, pos);
	int filled_until = 0;

	for (int i = 1; i < LARGESTS_FILLED_UNTIL; i++) {
		int unfilled_cnt = (unfilled_n - filled_until);
		int group_size = min(unfilled_cnt, 6);
		if ((LARGESTS_FILLED_UNTIL - i) * 5 >= unfilled_cnt) {
			group_size = min(group_size, 5);
		}

		for (int j = filled_until + 1; j <= filled_until + group_size; j++) {
			A[pos[j]] = i;
		}

		filled_until += group_size;
	}
/*
	for (int i = 0; i < N; i++) {
		printf("%2d ", A[i]);
	}
	printf("\n");
*/
	return A;
}

taster

#include "taster.h"
#include <bits/stdc++.h>
using namespace std;

const int LARGESTS_FILLED_UNTIL = 5;
const int RAND_SEED = 689;

// merge insertion sort ---- merge insertion sort ---- merge insertion sort ---- merge insertion sort
const bool CONSIDER_INSERTION = true;
const bool CONSIDER_MERGE = true;
const bool CONSIDER_MI = true;

const bool INSERTION_BS = true;
const bool INSERTION_TS = false;

const bool MERGE_OPTIMIZE = true;

const bool MI_HALF = true;
const bool MI_OPTIMIZE = true;

int cmp(int u, int v) {
	int result = Compare(u, v);
	return result == 1;
}

vector<int> operator+ (const vector<int>& u, const vector<int>& v) {
	vector<int> result(u.begin(), u.end());
	result.insert(result.end(), v.begin(), v.end());

	return result;
}

vector<int> operator+ (const vector<int>& u, const int& v) {
	return u + vector<int>(1, v);
}

vector<int> operator+ (const int& u, const vector<int>& v) {
	return vector<int>(1, u) + v;
}

tuple<vector<int>, vector<int>, vector<int>> split(const vector<int>& T, int size1, int size2 = -1, int size3 = -1) {
	if (size2 == -1) {
		size2 = T.size() - size1;
		size3 = 0;
	} else
	if (size3 == -1) {
		size3 = T.size() - size1 - size2;
	}

	return make_tuple(vector<int>(T.begin(), T.begin() + size1),
						vector<int>(T.begin() + size1, T.begin() + size1 + size2),
						vector<int>(T.begin() + size1 + size2, T.end()));
}

const int INF = 123456;
int N;
vector<int> sortDP;

map<int, int> memInsertionCost;
map<pair<int, int>, int> memMultiInsertionsCost;
map<pair<int, int>, vector<pair<int, int>>> memMultiInsertionsDP;

// cost for inserting ONE element into a SORTED array of "size - 1" elements
int insertionCost(int size) {
	if (memInsertionCost.count(size)) {
		return memInsertionCost[size];
	}
	int result = INF;
	if (INSERTION_BS) {
		result = min(result, 2 + insertionCost(size - size / 2));
	}
	if (INSERTION_TS) {
		result = min(result, 3 + insertionCost((size - 1) / 3 + 1));
	}
	return memInsertionCost[size] = result;
}

// cost to sort two SORTED arrays of "size1" and "size2" elements
int mergeCost(int size1, int size2) {
	if (!MERGE_OPTIMIZE || !INSERTION_TS) {
		return 2 * (size1 + size2 - 1);
	}
	if (size1 == 1 && size2 == 1) {
		return 2;
	}
	return 2 * (size1 + size2 - 3) + 3;
}


// dp[i].first = value
// dp[i].second = backtrack
vector<pair<int, int>> multiInsertionsDP(int size1, int size2) {
	if (memMultiInsertionsDP.count(make_pair(size1, size2))) {
		return memMultiInsertionsDP[make_pair(size1, size2)];
	}
	vector<int> guaranteedPos(size2, 0);

	for (int i = 0; i < size2; i++) {
		guaranteedPos[i] = min(i + 3, size1 + 1);
	}

	vector<pair<int, int>> dp(size2, make_pair(INF, -1));

	for (int i = 0; i < size2; i++) {
		for (int j = 0; j <= i; j++) {
			int cost = (j > 0) ? dp[j - 1].first : 0;
			for (int k = 0; k <= i - j; k++) {
				cost += insertionCost(guaranteedPos[i - k] + k + j);
			}
			dp[i] = min(dp[i], make_pair(cost, j));
		}
	}

	return memMultiInsertionsDP[make_pair(size1, size2)] = dp;
}

// https://en.wikipedia.org/wiki/Merge-insertion_sort
// "size1" is the size of X
// "size2" is the size of Y
int multiInsertionsCost(int size1, int size2) {
	if (size2 == 0) {
		return 0;
	}
	if (memMultiInsertionsCost.count(make_pair(size1, size2))) {
		return memMultiInsertionsCost[make_pair(size1, size2)];
	}
	
	vector<pair<int, int> > dp = multiInsertionsDP(size1, size2);

	return memMultiInsertionsCost[make_pair(size1, size2)] = dp[size2 - 1].first;
}

void precompute(int N) {
	memInsertionCost[1] = 0;

	sortDP.push_back(0);
	sortDP.push_back(0);

	for (int i = sortDP.size(); sortDP.size() <= N; i = sortDP.size()) {
		sortDP.push_back(INF);

		if (CONSIDER_INSERTION) {
			// inserting ONE element into "i - 1" SORTED elements
			sortDP[i] = min(sortDP[i], sortDP[i - 1] + insertionCost(i));
		}

		if (CONSIDER_MERGE) {
			// merging TWO SORTED arrays of "j" and "i - j" elements
			for (int j = 1; j <= i - j; j++) {
				sortDP[i] = min(sortDP[i], sortDP[j] + sortDP[i - j] + mergeCost(j, i - j));
			}
		}

		if (CONSIDER_MI) {
			// merge-insertion sort with parition of "j" and "i - j" elements
			for (int j = MI_HALF ? i / 2 : 1; j <= i - j; j++) {
				int sizeOfX = j + 1;
				int sizeOfY = i - j - 1;
				int costX = 2 * j + sortDP[j];
				int costY = multiInsertionsCost(sizeOfX, sizeOfY);

				sortDP[i] = min(sortDP[i], costX + costY);
			}
		}
	}
}

vector<int> solve(const vector<int>& arr);

vector<int> insertion(const vector<int>& arr, int extra) {
	int len = arr.size();

	if (len == 0) {
		return vector<int>{extra};
	}

	if (INSERTION_BS && 2 + insertionCost(len + 1 - (len + 1) / 2) == insertionCost(len + 1)) {
		int verdict = cmp(arr[len / 2], extra);

		vector<int> prefix(arr.begin(), arr.begin() + len / 2);
		vector<int> suffix(arr.begin() + len / 2 + 1, arr.end());
		
		if (verdict == 1) {
			prefix = insertion(prefix, extra);
		} else {
			suffix = insertion(suffix, extra);
		}

		return prefix + arr[len / 2] + suffix;
	}

	assert(false);
}

vector<int> merge(const vector<int>& u, const vector<int>& v) {
	vector<int> result;
	int pu = 0, pv = 0;
	while (pu + MERGE_OPTIMIZE < u.size() && pv + MERGE_OPTIMIZE < v.size()) {
		int verdict = cmp(u[pu], v[pv]);

		if (verdict == 0) {
			result.push_back(u[pu++]);
		} else {
			result.push_back(v[pv++]);
		}
	}

	if (MERGE_OPTIMIZE) {
		if (pu + 1 == u.size()) {
			vector<int> vsuffix;
			tie(ignore, vsuffix, ignore) = split(v, pv);
			return result + insertion(vsuffix, u[pu]);
		}
		if (pv + 1 == v.size()) {
			vector<int> usuffix;
			tie(ignore, usuffix, ignore) = split(u, pu);
			return result + insertion(usuffix, v[pv]);
		}
	}

	while (pu < u.size()) {
		result.push_back(u[pu++]);
	}

	while (pv < v.size()) {
		result.push_back(v[pv++]);
	}

	return result;
}

vector<int> reorder(const vector<int>& elements, const vector<int>& from, const vector<int>& to) {
	map<int, int> originalPosition;
	for (int i = 0; i < from.size(); i++) {
		originalPosition[from[i]] = i;
	}

	vector<int> result = elements;

	for (int i = 0; i < to.size(); i++) {
		result[i] = elements[originalPosition[to[i]]];
	}

	return result;
}

vector<int> mergeInsertion(const vector<int>& arr, int partitionSize) {
	assert(partitionSize * 2 <= arr.size());

	vector<int> partitionX(arr.begin(), arr.begin() + partitionSize);
	vector<int> partitionY(arr.begin() + partitionSize, arr.end());

	for (int i = 0; i < partitionSize; i++) {
		int verdict = cmp(partitionX[i], partitionY[i]);

		if (!verdict) { // swapping larger elements to X
			swap(partitionX[i], partitionY[i]);
		}
	}

	vector<int> newPartitionX = solve(partitionX);
	vector<int> newPartitionY = reorder(partitionY, partitionX, newPartitionX);
	newPartitionX.insert(newPartitionX.begin(), newPartitionY[0]);
	newPartitionY.erase(newPartitionY.begin());

	if (newPartitionY.size() == 0) {
		return newPartitionX;
	}

	vector<pair<int, int>> dp = multiInsertionsDP(newPartitionX.size(), newPartitionY.size());
	vector<int> insertionOrder;

	int cur = newPartitionY.size() - 1;

	while (cur >= 0) {
		int to = dp[cur].second;
		for (int i = to; i <= cur; i++) {
			insertionOrder.push_back(i);
		}
		cur = to - 1;
	}

	reverse(insertionOrder.begin(), insertionOrder.end());

	vector<int> result(newPartitionX.begin(), newPartitionX.end());

	for (int i = 0; i < newPartitionY.size(); i++) {
		vector<int> prefix, suffix;
		int prefixSize = min((int)result.size(), i + insertionOrder[i] + 2);

		if (MI_OPTIMIZE) {
			if (insertionOrder[i] + 2 < newPartitionX.size()) {
				int relativeX = newPartitionX[insertionOrder[i] + 2];
				for (int j = 0; j < result.size(); j++) {
					if (result[j] == relativeX) {
						prefixSize = j;
					}
				}
			}
		}

		tie(prefix, suffix, ignore) = split(result, prefixSize);
		result = insertion(prefix, newPartitionY[insertionOrder[i]]) + suffix;
	}

	return result;
}

vector<int> solve(const vector<int>& arr) {
	int len = arr.size();

	if (len <= 1) {
		return arr;
	}

	if (CONSIDER_INSERTION) {
		if (sortDP[len] == sortDP[len - 1] + insertionCost(len)) {
			vector<int> prefix(arr.begin(), arr.end() - 1);
			return insertion(solve(prefix), arr[len - 1]);
		}
	}

	if (CONSIDER_MERGE) {
		for (int i = 1; i <= len - i; i++) {
			if (sortDP[len] == sortDP[i] + sortDP[len - i] + mergeCost(i, len - i)) {
				vector<int> prefix(arr.begin(), arr.begin() + i);
				vector<int> suffix(arr.begin() + i, arr.end());
				return merge(solve(prefix), solve(suffix));
			}
		}
	}

	if (CONSIDER_MI) {
		for (int i = MI_HALF ? len / 2 : 1; i <= len - i; i++) {
			int sizeOfX = i + 1;
			int sizeOfY = len - i - 1;
			int costX = 2 * i + sortDP[i];
			int costY = multiInsertionsCost(sizeOfX, sizeOfY);

			if (sortDP[len] == costX + costY) {
				return mergeInsertion(arr, i);
			}
		}
	}

	assert(false);
}
// merge insertion sort ---- merge insertion sort ---- merge insertion sort ---- merge insertion sort

int handle_largests(int K, vector<int>& A, vector<int>& magic, vector<int>& R) {
	int N = A.size();
	int next_num = N;
	for (int filled_as = K; filled_as >= LARGESTS_FILLED_UNTIL; filled_as--) {
		vector<pair<int, int> > filled_bingo;
		for (int i = 0; i < N; i++) {
			if (A[i] == filled_as) {
				filled_bingo.push_back(make_pair(magic[i], i));
			}
		}
		sort(filled_bingo.begin(), filled_bingo.end());

		for (int i = 0; i < filled_bingo.size(); i++) {
			R[filled_bingo[i].second] = next_num--;
		}
	}

	return next_num;
}

void handle_smallests(vector<int>& A, vector<int>& R) {
	int N = A.size();
	int next_num = 1;
	for (int filled_as = 1; filled_as < LARGESTS_FILLED_UNTIL; filled_as++) {
		vector<int> filled_bingo;
		for (int i = 0; i < N; i++) {
			if (A[i] == filled_as) {
				filled_bingo.push_back(i);
			}
		}

		random_shffule(filled_bingo.begin(), filled_bingo.end());
		filled_bingo = solve(filled_bingo);

		for (int i = 0; i < filled_bingo.size(); i++) {
			R[filled_bingo[i]] = next_num++;
		}
	}
}

vector<int> SortWines(int K, vector<int> A) {
	int N = A.size();
	precompute(N);

	srand(RAND_SEED);
	vector<int> magic;
	for (int i = 0; i < N; i++) {
		magic.push_back(i);
	}
	random_shuffle(magic.begin(), magic.end());

	vector<int> R(N, 0);

	handle_largests(K, A, magic, R);
	handle_smallests(A, R);
/*
	for (int i = 0; i < N; i++) {
		printf("%2d ", R[i]);
	}
	printf("\n");
*/
	return R;
}

Compilation message

taster.cpp: In function 'void precompute(int)':
taster.cpp:139:44: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = sortDP.size(); sortDP.size() <= N; i = sortDP.size()) {
                              ~~~~~~~~~~~~~~^~~~
taster.cpp: In function 'std::vector<int> merge(const std::vector<int>&, const std::vector<int>&)':
taster.cpp:198:29: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while (pu + MERGE_OPTIMIZE < u.size() && pv + MERGE_OPTIMIZE < v.size()) {
         ~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~
taster.cpp:198:63: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while (pu + MERGE_OPTIMIZE < u.size() && pv + MERGE_OPTIMIZE < v.size()) {
                                           ~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~
taster.cpp:209:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if (pu + 1 == u.size()) {
       ~~~~~~~^~~~~~~~~~~
taster.cpp:214:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if (pv + 1 == v.size()) {
       ~~~~~~~^~~~~~~~~~~
taster.cpp:221:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while (pu < u.size()) {
         ~~~^~~~~~~~~~
taster.cpp:225:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while (pv < v.size()) {
         ~~~^~~~~~~~~~
taster.cpp: In function 'std::vector<int> reorder(const std::vector<int>&, const std::vector<int>&, const std::vector<int>&)':
taster.cpp:234:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < from.size(); i++) {
                  ~~^~~~~~~~~~~~~
taster.cpp:240:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < to.size(); i++) {
                  ~~^~~~~~~~~~~
In file included from /usr/include/c++/7/cassert:44:0,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:33,
                 from taster.cpp:2:
taster.cpp: In function 'std::vector<int> mergeInsertion(const std::vector<int>&, int)':
taster.cpp:248:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  assert(partitionSize * 2 <= arr.size());
         ~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~
taster.cpp:287:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < newPartitionY.size(); i++) {
                  ~~^~~~~~~~~~~~~~~~~~~~~~
taster.cpp:292:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if (insertionOrder[i] + 2 < newPartitionX.size()) {
taster.cpp:294:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int j = 0; j < result.size(); j++) {
                     ~~^~~~~~~~~~~~~~~
taster.cpp: In function 'int handle_largests(int, std::vector<int>&, std::vector<int>&, std::vector<int>&)':
taster.cpp:362:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < filled_bingo.size(); i++) {
                   ~~^~~~~~~~~~~~~~~~~~~~~
taster.cpp: In function 'void handle_smallests(std::vector<int>&, std::vector<int>&)':
taster.cpp:381:3: error: 'random_shffule' was not declared in this scope
   random_shffule(filled_bingo.begin(), filled_bingo.end());
   ^~~~~~~~~~~~~~
taster.cpp:381:3: note: suggested alternative: 'random_r'
   random_shffule(filled_bingo.begin(), filled_bingo.end());
   ^~~~~~~~~~~~~~
   random_r
taster.cpp:384:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < filled_bingo.size(); i++) {
                   ~~^~~~~~~~~~~~~~~~~~~~~