제출 #150595

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
150595		서울대학교 연구공원 944동 삼성전자서울대연구소 (#200)	포도주 시음 (FXCUP4_wine)	C++17	0 / 100	1101 ms	1024 KiB

bartender

#include "bartender.h"

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


static __int128 fact[31];

__int128 P2I(std::vector<int> R)
{
	if(R.size() == 0) return 0;
	__int128 ans = R[0]*fact[R.size()-1];
	vector<int> R2;
	for(int i=1; i<(int)R.size(); ++i)
	{
		if(R[i] > R[0]) R2.push_back(R[i]-1);
		else R2.push_back(R[i]);
	}
	return ans + P2I(R2);
}

vector<int> I2D(int K, int N, __int128 x)
{
	vector<int> V(N);
	for(int i=N-1; i>=0; --i)
	{
		V[i] = x%K;
		x /= K;
	}
	return V;
}

static void Init(int N)
{
	fact[0] = 1;
	for(int i=1; i<=N; ++i)
		fact[i] = i*fact[i-1];
}

std::vector<int> BlendWines(int K, std::vector<int> R){
	Init(R.size());
	for(auto&x:R) --x;
	vector<int> A = I2D(K, R.size(), P2I(R));
	for(auto&x:A)++x;
	return A;
}

taster

#include "taster.h"


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

static __int128 fact[31];

vector<int> I2P(int N, __int128 v)
{
	if(N == 0)
	{
		vector<int> R2;
		return R2;
	}
	vector<int> R2 = I2P(N-1, v%fact[N-1]);
	vector<int> R; R.push_back(v/fact[N-1]);
	for(int i=0; i<N-1; ++i)
	{
		if(R2[i] >= R[0]) R.push_back(R2[i]+1);
		else R.push_back(R2[i]);
	}
	return R;
}

__int128 D2I(int K, vector<int> V)
{
	__int128 ans = 0;
	for(int i=0; i<(int)V.size(); ++i)
		ans = ans*K+V[i];
	return ans;
}

static void Init(int N)
{
	fact[0] = 1;
	for(int i=1; i<=N; ++i)
		fact[i] = i*fact[i-1];
}

__int128 p(int a, int b)
{
	__int128 x = 1;
	for(int i=0; i<b; ++i)
		x *= a;
	return x;
}

vector<tuple<int, int, int> > TR;

bool test(vector<int> R)
{
	for(auto x: TR)
	{
		auto [a,b,c] = x;
		if( (R[a]<R[b]) != (c==-1)) return false;
	}
	return true;
}

std::vector<int> SortWines(int K, std::vector<int> A) {
	Init(A.size());
	for(auto&x:A) --x;
	__int128 aa =  D2I(K, A);

	vector<pair<int, int> > tt;
	for(int i=0; i<(int)A.size(); ++i)
		for(int j=0; j<i; ++j)
			if(A[i]+A[j] <= K-2)
			{
				//printf("%d %d\n", A[i], A[j]);
				tt.emplace_back(i, j);
			}
	
	mt19937_64 rng(573);
	shuffle(tt.begin(), tt.end(), rng);

	for(int i=0; i<min((int)tt.size(),30); ++i)
	{
		//printf("%d %d\n",A[tt[i].first], A[tt[i].second]);
		TR.emplace_back(tt[i].first, tt[i].second, Compare(tt[i].first, tt[i].second));
	}

	while(true)
	{	
		vector<int> R = I2P(A.size(), aa);
		for(auto&x:R)++x;
		if(test(R)) return R;
		aa += p(K, A.size());
	}
}

• Subtask 1: 0 / 100