답안 #150621

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
150621	2019-09-01T08:44:07 Z	서울대학교 연구공원 944동 삼성전자서울대연구소(#3600, ho94949, dotorya, zigui)	포도주 시음 (FXCUP4_wine)	C++17	75 / 100	905 ms	1016 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(clock()<0.9*CLOCKS_PER_SEC)
	{	
		vector<int> R = I2P(A.size(), aa);
		for(auto&x:R)++x;
		if(test(R)) return R;
		aa += p(K, A.size());
	}
	return I2P(A.size(), aa);
}

Subtask #1
75.0 / 100.0

#	결과	실행 시간	메모리	Grader output
1	Correct	10 ms	644 KB	Correct
2	Correct	8 ms	780 KB	Correct
3	Correct	10 ms	908 KB	Correct
4	Correct	10 ms	868 KB	Correct
5	Correct	9 ms	784 KB	Correct
6	Correct	10 ms	908 KB	Correct
7	Correct	10 ms	812 KB	Correct
8	Correct	9 ms	908 KB	Correct
9	Correct	9 ms	772 KB	Correct
10	Correct	10 ms	772 KB	Correct
11	Correct	10 ms	908 KB	Correct
12	Correct	10 ms	772 KB	Correct
13	Correct	9 ms	772 KB	Correct
14	Correct	9 ms	780 KB	Correct
15	Correct	10 ms	908 KB	Correct
16	Correct	10 ms	772 KB	Correct
17	Correct	10 ms	908 KB	Correct
18	Correct	10 ms	772 KB	Correct
19	Correct	10 ms	772 KB	Correct
20	Correct	9 ms	772 KB	Correct
21	Correct	10 ms	1012 KB	Correct
22	Correct	10 ms	772 KB	Correct
23	Correct	9 ms	772 KB	Correct
24	Correct	9 ms	772 KB	Correct
25	Correct	9 ms	804 KB	Correct
26	Correct	10 ms	784 KB	Correct
27	Correct	9 ms	644 KB	Correct
28	Correct	10 ms	756 KB	Correct
29	Correct	9 ms	960 KB	Correct
30	Correct	10 ms	644 KB	Correct
31	Correct	10 ms	692 KB	Correct
32	Correct	10 ms	772 KB	Correct
33	Correct	8 ms	772 KB	Correct
34	Correct	9 ms	644 KB	Correct
35	Correct	10 ms	960 KB	Correct
36	Correct	9 ms	716 KB	Correct
37	Correct	10 ms	772 KB	Correct
38	Correct	10 ms	1012 KB	Correct
39	Correct	12 ms	644 KB	Correct
40	Correct	9 ms	772 KB	Correct
41	Correct	9 ms	960 KB	Correct
42	Correct	10 ms	772 KB	Correct
43	Correct	9 ms	772 KB	Correct
44	Correct	9 ms	776 KB	Correct
45	Correct	8 ms	780 KB	Correct
46	Correct	9 ms	772 KB	Correct
47	Correct	10 ms	644 KB	Correct
48	Correct	10 ms	772 KB	Correct
49	Correct	10 ms	1012 KB	Correct
50	Correct	8 ms	888 KB	Correct
51	Correct	11 ms	772 KB	Correct
52	Correct	9 ms	780 KB	Correct
53	Correct	9 ms	908 KB	Correct
54	Correct	9 ms	784 KB	Correct
55	Correct	10 ms	772 KB	Correct
56	Correct	10 ms	1016 KB	Correct
57	Correct	9 ms	644 KB	Correct
58	Correct	10 ms	932 KB	Correct
59	Correct	10 ms	644 KB	Correct
60	Correct	10 ms	644 KB	Correct
61	Correct	9 ms	908 KB	Correct
62	Correct	10 ms	772 KB	Correct
63	Correct	10 ms	908 KB	Correct
64	Correct	9 ms	772 KB	Correct
65	Correct	10 ms	772 KB	Correct
66	Correct	9 ms	932 KB	Correct
67	Correct	9 ms	772 KB	Correct
68	Correct	10 ms	908 KB	Correct
69	Correct	9 ms	772 KB	Correct
70	Correct	9 ms	772 KB	Correct
71	Correct	10 ms	908 KB	Correct
72	Correct	9 ms	644 KB	Correct
73	Correct	10 ms	772 KB	Correct
74	Correct	10 ms	908 KB	Correct
75	Correct	9 ms	772 KB	Correct
76	Correct	9 ms	860 KB	Correct
77	Correct	9 ms	780 KB	Correct
78	Correct	9 ms	924 KB	Correct
79	Correct	9 ms	772 KB	Correct
80	Correct	10 ms	772 KB	Correct
81	Correct	10 ms	772 KB	Correct
82	Correct	75 ms	684 KB	Correct
83	Correct	38 ms	684 KB	Correct
84	Correct	84 ms	644 KB	Correct
85	Correct	86 ms	776 KB	Correct
86	Correct	10 ms	644 KB	Correct
87	Correct	10 ms	908 KB	Correct
88	Correct	9 ms	792 KB	Correct
89	Correct	10 ms	956 KB	Correct
90	Correct	8 ms	644 KB	Correct
91	Correct	9 ms	908 KB	Correct
92	Correct	8 ms	908 KB	Correct
93	Correct	9 ms	772 KB	Correct
94	Partially correct	905 ms	908 KB	Wrong
95	Partially correct	904 ms	772 KB	Wrong
96	Partially correct	904 ms	780 KB	Wrong
97	Partially correct	905 ms	772 KB	Wrong
98	Correct	841 ms	772 KB	Correct
99	Partially correct	905 ms	792 KB	Wrong
100	Partially correct	904 ms	780 KB	Wrong
101	Partially correct	905 ms	776 KB	Wrong
102	Correct	8 ms	772 KB	Correct
103	Correct	8 ms	908 KB	Correct
104	Correct	9 ms	772 KB	Correct
105	Correct	10 ms	772 KB	Correct
106	Correct	10 ms	872 KB	Correct
107	Correct	10 ms	780 KB	Correct
108	Correct	10 ms	772 KB	Correct
109	Partially correct	905 ms	908 KB	Wrong
110	Partially correct	905 ms	784 KB	Wrong
111	Partially correct	904 ms	772 KB	Wrong
112	Partially correct	904 ms	1016 KB	Wrong
113	Partially correct	905 ms	776 KB	Wrong
114	Partially correct	905 ms	908 KB	Wrong
115	Partially correct	905 ms	796 KB	Wrong
116	Partially correct	905 ms	684 KB	Wrong
117	Correct	9 ms	732 KB	Correct
118	Partially correct	904 ms	688 KB	Wrong
119	Partially correct	904 ms	772 KB	Wrong
120	Partially correct	904 ms	792 KB	Wrong

답안 #150621

Compilation message

Subtask #1 75.0 / 100.0

Subtask #1
75.0 / 100.0