Submission #149502

#	Time	Username	Problem	Language	Result	Execution time	Memory
149502		Ian and 2-bit memory (#200)	Wine Tasting (FXCUP4_wine)	C++17	57 / 100	11 ms	1064 KiB

bartender

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

const int LARGESTS_FILLED_UNTIL = 6;

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) {
	srand(882);
	int N = R.size();
	int pos[35] = {};
	for (int i = 0; i < N; i++) {
		pos[R[i]] = i;
	}

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

	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, 5);
		if ((6 - i) * 4 >= unfilled_cnt) {
			group_size = min(group_size, 4);
		}

		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 = 6;

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;
}

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

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);
			}
		}

		stable_sort(filled_bingo.begin(), filled_bingo.end(), cmp);

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

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

	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 (stderr)

taster.cpp: In function 'int handle_largests(int, std::vector<int>&, std::vector<int>&, std::vector<int>&)':
taster.cpp:19: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:44:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < filled_bingo.size(); i++) {
                   ~~^~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 57 / 100