Submission #150754

#	Time	Username	Problem	Language	Result	Execution time	Memory
150754		mit한의대지망생 (#200)	Wine Tasting (FXCUP4_wine)	C++17	65 / 100	13 ms	1700 KiB

bartender

#include "bartender.h"
using namespace std;

vector<int> BlendWines(int K, vector<int> R){
	int N = R.size();
	vector<int> A(N);
	if(N <= 5){
		for(int i = 0; i < N; i++) A[i] = (R[i] - 1) % 9 + 1;
		return A;
	}
	for(int i = 0; i < N; i++) A[i] = (R[i] == N-1 ? 10 : (R[i]-1) % 9 + 1);
	return A;
}

taster

#include "taster.h"
#include <bits/stdc++.h>
#define all(v) (v).begin(),(v).end()
using namespace std;

vector<int> g[31];
vector<int> alc;
int cmp[31][31], N;
vector<int> bf(){
	for(int i = 0; i < N; i++){
		for(int j = i + 1; j < N; j++){
			cmp[i][j] = Compare(i, j);
			cmp[j][i] = -cmp[i][j];
		}
	}
	vector<int> R(N), I(N);
	iota(all(I), 0);
	sort(all(I), [](int u, int v){return cmp[u][v] == -1;});
	for(int i = 0; i < N; i++){
		R[I[i]] = i + 1;
	}
	return R;
}

vector<int> SortWines(int K, vector<int> A) {
	//cout << "asdf\n";
	N = A.size();
	alc = A;
	vector<int> R(N);
	for(int i = 0; i < N; i++) g[A[i]].push_back(i);

	if(N <= 5){
		return bf();
	}
	vector<vector<int>> Pms;
	vector<int> P[3];
	vector<int> gmr;
	int r = 0;
	for(int i = 0; i < 3; i++){
		P[i].resize(g[i+1].size());
		r += g[i+1].size();
		iota(all(P[i]), 0);
		copy(all(g[i+1]), back_inserter(gmr));
	}
	//for(int u : gmr) cout << u << ' '; cout << '\n';
	do{
		do{
			do{
				Pms.emplace_back();
				for(int i = 0; i < 3; i++){
					for(int j = 0; j < P[i].size(); j++) Pms.back().push_back(P[i][j] * 1000 + i);
				}
			}while(next_permutation(all(P[2])));
		}while(next_permutation(all(P[1])));
	}while(next_permutation(all(P[0]))); 
	//cout << "permdict " << Pms.size() << "\n";
	vector<vector<int>> sel[2];

	int dep = 0;
	while(Pms.size() > 1){
		int diff = INT_MAX, di, dj;
		for(int i = 0; i < r; i++){
			for(int j = i + 1; j < r; j++){
				int ldiff = 0;
				for(vector<int> &p : Pms){
					if(p[i] < p[j]) ldiff += 1;
					else ldiff -= 1;
				}
				if(abs(ldiff) < diff){
					diff = abs(ldiff);
					di = i;
					dj = j;
				}
			}
		}
		sel[0].clear();
		sel[1].clear();
		for(vector<int>& p : Pms){
			sel[p[di] < p[dj]].push_back(p);
		}
		++dep;
		//cout << "decision tree " << dep << " : " << sel[0].size() << ' ' << sel[1].size() << '\n';
		bool s = (Compare(gmr[di], gmr[dj]) == -1);
		Pms = sel[s];
		sel[!s].clear();
	}

	for(int &q : Pms.back()) q /= 1000;
	int cur = 0;
	for(int i = 1; i <= 3; i++){
		vector<int> tmp(g[i].size());
		for(int j = 0; j < g[i].size(); j++) tmp[Pms.back()[cur + j]] = g[i][j];
		g[i] = tmp;
		cur += g[i].size();
	}
	for(int i = 4; i <= K; i++){
		vector<vector<int>> ps;
		int r = g[i].size();
		vector<int> U(r);
		iota(all(U), 0);
		do{
			vector<int> cU = U;
			ps.push_back(cU);
		}while(next_permutation(all(U)));
		vector<vector<int>> sel[2];
		int dep = 0;
		while(ps.size() > 1){
			int diff = INT_MAX, di, dj;
			for(int i = 0; i < r; i++){
				for(int j = 1; j < r; j++){
					int ldiff = 0;
					for(vector<int> &p : ps){
						if(p[i] < j) ldiff += 1;
						else ldiff -= 1;
					}
					if(abs(ldiff) < diff){
						diff = abs(ldiff);
						di = i;
						dj = j;
					}
				}
			}
			sel[0].clear();
			sel[1].clear();
			for(vector<int>& p : ps){
				sel[p[di] < dj].push_back(p);
			}
			++dep;
			//cout << "decision tree " << dep << " : " << sel[0].size() << ' ' << sel[1].size() << '\n';
			bool s = (Compare(g[i][di], g[1][dj]) == -1);
			ps = sel[s];
			sel[!s].clear();
		}
		vector<int> tmp(r);
		for(int j = 0; j < r; j++) tmp[ps.back()[j]] = g[i][j];
		g[i] = tmp;
	}
	for(int i = 1; i <= K; i++){
		for(int j = 0; j < g[i].size(); j++){
			R[g[i][j]] = j * 9 + i;
		}
	}
	if(g[10].size()) R[g[10][0]] = N-1;
	return R;
}

Compilation message (stderr)

taster.cpp: In function 'std::vector<int> SortWines(int, std::vector<int>)':
taster.cpp:51:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
      for(int j = 0; j < P[i].size(); j++) Pms.back().push_back(P[i][j] * 1000 + i);
                     ~~^~~~~~~~~~~~~
taster.cpp:92:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j = 0; j < g[i].size(); j++) tmp[Pms.back()[cur + j]] = g[i][j];
                  ~~^~~~~~~~~~~~~
taster.cpp:139:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j = 0; j < g[i].size(); j++){
                  ~~^~~~~~~~~~~~~
taster.cpp:126:15: warning: 'dj' may be used uninitialized in this function [-Wmaybe-uninitialized]
     sel[p[di] < dj].push_back(p);
taster.cpp:108:24: warning: 'di' may be used uninitialized in this function [-Wmaybe-uninitialized]
    int diff = INT_MAX, di, dj;
                        ^~
taster.cpp:61:27: warning: 'dj' may be used uninitialized in this function [-Wmaybe-uninitialized]
   int diff = INT_MAX, di, dj;
                           ^~
taster.cpp:61:23: warning: 'di' may be used uninitialized in this function [-Wmaybe-uninitialized]
   int diff = INT_MAX, di, dj;
                       ^~

• Subtask 1: 65 / 100