oj.uz

Submission #150542

# Submission time Handle Problem Language Result Execution time Memory
150542 2019-09-01T08:36:40 Z 서울대학교 연구공원 944동 삼성전자서울대연구소(#3600, ho94949, dotorya, zigui) Wine Tasting (FXCUP4_wine) C++17
0 / 100
 10 ms 908 KB 
#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;
}

#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)
				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)
	{
		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.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 908 KB Correct
2 Correct 9 ms 772 KB Correct
3 Correct 8 ms 644 KB Correct
4 Correct 9 ms 772 KB Correct
5 Correct 9 ms 772 KB Correct
6 Correct 9 ms 872 KB Correct
7 Incorrect 10 ms 908 KB Wrong
8 Halted 0 ms 0 KB -