Submission #148921

#	Time	Username	Problem	Language	Result	Execution time	Memory
148921		Dopatii (#200)	Wine Tasting (FXCUP4_wine)	C++17	43 / 100	11 ms	1072 KiB

bartender

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

using namespace std;

vector<int> BlendWines(int K, vector<int> R)
{
	int N = R.size();
	vector<int> pos;
	pos.resize(R.size());
	for(int i = 0; i < R.size(); i++)	R[i]--;
	for(int i = 0; i < R.size(); i++) pos[ R[i] ] = i;

	vector<int> ret;
	ret.resize(R.size());

	int cnt = (K + 1) / 2;
	for(int i = 0; i < cnt && i < N; i++)
		ret[ pos[i] ] = K - i;

	vector<int> order;
	for(int i = 0; i < N; i++)
		if(ret[i] == 0)	order.push_back(i);

	sort(order.begin(), order.end(),
			[&](int a, int b) { return R[a] < R[b]; });

	int myk = K / 2;
	for(int i = 0; i < order.size(); i++)
		ret[ order[i] ] = (myk - (i % myk));
	return ret;
}

taster

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

using namespace std;

map<int, int> mp[35];

int myCompare(int x, int y)
{
	if(mp[x].count(y))	return mp[x][y];
	int ans = Compare(x, y);
	mp[x][y] = (ans == -1 ? 1 : 0);
	mp[y][x] = (ans == 1 ? 1 : 0);
	return mp[x][y];
}

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

	vector<int> pos[35];
	for(int i = 0; i < N; i++)
		pos[ A[i] ].push_back(i);

	mt19937 g(chrono::high_resolution_clock::now().time_since_epoch().count());
	for(int i = 1; i <= K; i++)
		shuffle(pos[i].begin(), pos[i].end(), g);

	for(int i = 1; i <= K; i++)
		sort(pos[i].begin(), pos[i].end(),
			[&](int a, int b) { return myCompare(a, b); } );

	int val = 1;
	for(int i = 0; i < 30; i++)
	{
		for(int j = K; j >= 1; j--)
			if(!pos[j].empty())
			{
				ret[ pos[j][0] ] = val;
				val++;
				pos[j].erase(pos[j].begin());
			}
	}

	return ret;
}

Compilation message (stderr)

bartender.cpp: In function 'std::vector<int> BlendWines(int, std::vector<int>)':
bartender.cpp:11:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < R.size(); i++) R[i]--;
                 ~~^~~~~~~~~~
bartender.cpp:12:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < R.size(); i++) pos[ R[i] ] = i;
                 ~~^~~~~~~~~~
bartender.cpp:29:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < order.size(); i++)
                 ~~^~~~~~~~~~~~~~

• Subtask 1: 43 / 100