답안 #150595

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
150595	2019-09-01T08:41:55 Z	서울대학교 연구공원 944동 삼성전자서울대연구소(#3600, ho94949, dotorya, zigui)	포도주 시음 (FXCUP4_wine)	C++17	0 / 100	1000 ms	1024 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-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.0

#	결과	실행 시간	메모리	Grader output
1	Correct	9 ms	772 KB	Correct
2	Correct	10 ms	924 KB	Correct
3	Correct	9 ms	772 KB	Correct
4	Correct	10 ms	772 KB	Correct
5	Correct	8 ms	772 KB	Correct
6	Correct	9 ms	772 KB	Correct
7	Correct	10 ms	772 KB	Correct
8	Correct	9 ms	780 KB	Correct
9	Correct	9 ms	908 KB	Correct
10	Correct	9 ms	772 KB	Correct
11	Correct	9 ms	644 KB	Correct
12	Correct	10 ms	780 KB	Correct
13	Correct	9 ms	772 KB	Correct
14	Correct	9 ms	780 KB	Correct
15	Correct	8 ms	908 KB	Correct
16	Correct	8 ms	644 KB	Correct
17	Correct	8 ms	772 KB	Correct
18	Correct	9 ms	772 KB	Correct
19	Correct	9 ms	772 KB	Correct
20	Correct	9 ms	644 KB	Correct
21	Correct	9 ms	644 KB	Correct
22	Correct	9 ms	764 KB	Correct
23	Correct	10 ms	772 KB	Correct
24	Correct	9 ms	644 KB	Correct
25	Correct	8 ms	772 KB	Correct
26	Correct	8 ms	780 KB	Correct
27	Correct	9 ms	908 KB	Correct
28	Correct	9 ms	844 KB	Correct
29	Correct	8 ms	780 KB	Correct
30	Correct	9 ms	780 KB	Correct
31	Correct	9 ms	908 KB	Correct
32	Correct	8 ms	772 KB	Correct
33	Correct	9 ms	772 KB	Correct
34	Correct	8 ms	772 KB	Correct
35	Correct	9 ms	772 KB	Correct
36	Correct	9 ms	772 KB	Correct
37	Correct	10 ms	784 KB	Correct
38	Correct	10 ms	772 KB	Correct
39	Correct	10 ms	772 KB	Correct
40	Correct	9 ms	772 KB	Correct
41	Correct	10 ms	644 KB	Correct
42	Correct	9 ms	644 KB	Correct
43	Correct	9 ms	772 KB	Correct
44	Correct	9 ms	772 KB	Correct
45	Correct	10 ms	884 KB	Correct
46	Correct	10 ms	772 KB	Correct
47	Correct	9 ms	780 KB	Correct
48	Correct	9 ms	772 KB	Correct
49	Correct	9 ms	772 KB	Correct
50	Correct	9 ms	788 KB	Correct
51	Correct	9 ms	780 KB	Correct
52	Correct	10 ms	908 KB	Correct
53	Correct	10 ms	844 KB	Correct
54	Correct	8 ms	772 KB	Correct
55	Correct	9 ms	908 KB	Correct
56	Correct	9 ms	1024 KB	Correct
57	Correct	10 ms	908 KB	Correct
58	Correct	8 ms	644 KB	Correct
59	Correct	8 ms	852 KB	Correct
60	Correct	8 ms	644 KB	Correct
61	Correct	9 ms	772 KB	Correct
62	Correct	8 ms	772 KB	Correct
63	Correct	8 ms	772 KB	Correct
64	Correct	9 ms	812 KB	Correct
65	Correct	8 ms	644 KB	Correct
66	Correct	11 ms	772 KB	Correct
67	Correct	10 ms	732 KB	Correct
68	Correct	9 ms	784 KB	Correct
69	Correct	9 ms	644 KB	Correct
70	Correct	10 ms	732 KB	Correct
71	Correct	9 ms	780 KB	Correct
72	Correct	10 ms	916 KB	Correct
73	Correct	8 ms	772 KB	Correct
74	Correct	10 ms	932 KB	Correct
75	Correct	11 ms	948 KB	Correct
76	Correct	10 ms	908 KB	Correct
77	Correct	8 ms	908 KB	Correct
78	Correct	8 ms	772 KB	Correct
79	Correct	9 ms	772 KB	Correct
80	Correct	8 ms	644 KB	Correct
81	Correct	8 ms	644 KB	Correct
82	Correct	70 ms	908 KB	Correct
83	Correct	40 ms	772 KB	Correct
84	Correct	86 ms	772 KB	Correct
85	Correct	78 ms	772 KB	Correct
86	Correct	9 ms	772 KB	Correct
87	Correct	9 ms	772 KB	Correct
88	Correct	10 ms	908 KB	Correct
89	Correct	9 ms	772 KB	Correct
90	Correct	10 ms	772 KB	Correct
91	Correct	8 ms	772 KB	Correct
92	Correct	10 ms	784 KB	Correct
93	Correct	10 ms	908 KB	Correct
94	Execution timed out	1101 ms	772 KB	Time limit exceeded
95	Halted	0 ms	0 KB	-

답안 #150595

Compilation message

Subtask #1 0 / 100.0

Subtask #1
0 / 100.0