Submission #150746

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

bartender

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

int f[35], used[35], pos[35];
std::vector<int> BlendWines(int K, std::vector<int> R){
	int N = R.size();
    if(K >= N) return R;
	vector <int> v(N);

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

	int NR = K / 2 + K % 2, ram = N;
	for(int val = N; val >= 1 && NR >= 1 ; --val){
        if(used[val]) continue ;
        --NR;
        int i = val;

        while(i >= 1){
            --ram;
            used[i] = 1;
            v[pos[i]] = K;
            if(pos[i] < pos[i - 1]) break ;
            --i;
        }

        --K;
	}


	int sz = ram / K, rest = ram % K;

    for(int i = ram; i >= 1 && K >= 1 ; --i, --K){
        int j = i - sz + 1;
        if(rest > 0) --j, --rest;

        for(int t = j; t <= i ; ++t) v[pos[t]] = K;

        i = j;
    }

    for(auto it : v) printf("%d ", it);

	return v;
}

taster

#include "taster.h"
#include <bits/stdc++.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];
}

std::vector<int> SortWines(int K, std::vector<int> A) {
	int N = A.size();
	if(N <= K) return A;
	vector <int> v(N);

	int cnt = K / 2 + K % 2, NR = N;

    while(cnt--){
        for(int i = A.size() - 1; i >= 0 ; --i) if(A[i] == K) v[i] = NR--;
        --K;
    }

    vector<int> pos[35];
	for(int i = 0; i < N; i++)
		if(A[i] <= K) 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 no = 0;
    for(int i = 1; i <= K ; ++i){
        for(auto it : pos[i])
            v[it] = ++no;

    }

    return v;
}

/**
    sort(pos[i].begin(), pos[i].end(),
    [&](int a, int b) { return myCompare(a, b); } );
**/

• Subtask 1: 4 / 100