oj.uz

Submission #150343

# Submission time Handle Problem Language Result Execution time Memory
150343 2019-09-01T08:11:08 Z USA1(#3634, ecnerwala, scott_wu, ksun48) Wine Tasting (FXCUP4_wine) C++17
100 / 100
 11 ms 1148 KB 
#include "taster.h"
#include "bartender.h"
#include <bits/stdc++.h>

namespace {

using namespace std;

using big = __int128_t;

const int FOUR = 4;
const int THREE = 3;

const int TWELVE = 12;

int ncalls = 0;

big ep(int n, vector<int> perm){
	assert((int)perm.size() == n);
	big res = 0;
	for(int i = 0; i < n; i++){
		res *= (n - i);
		res += perm[i];
		for(int j = i+1; j < n; j++){
			if(perm[j] > perm[i]) perm[j] -= 1;
		}
	}
	return res;
}

vector<int> dp(int n, big val){
	vector<int> perm(n, 0);
	for(int i = n-1; i >= 0; i--){
		int ind = val % (n - i);
		val /= (n - i);
		perm[i] = ind;
		for(int j = i + 1; j < n; j++){
			if(perm[j] >= perm[i]) perm[j] += 1;
		}
	}
	return perm;
}

vector<int> encode_permutation(vector<int> perm, int fours, int threes){
	big a = 1;
	for(int i = 1; i <= fours; i++) a *= big(i);
	big c = 1;
	for(int i = 0; i < fours; i++) c *= FOUR;
	for(int i = 0; i < threes; i++) c *= THREE;
	assert(a <= c);

	assert(dp(fours, ep(fours, perm)) == perm);
	big val = ep(fours, perm);
	vector<int> z;
	for(int i = 0; i < threes; i++){
		z.push_back(int(val % THREE)); val /= THREE;
	}
	for(int i = 0; i < fours; i++){
		z.push_back(int(val % FOUR)); val /= FOUR;
	}
	assert(val == 0);
	reverse(z.begin(), z.end());
	return z;
}


vector<int> decode_permutation(vector<int> info, int fours, int threes){
	int n = (int)info.size();
	assert(n == fours + threes);
	big r = 0;
	for(int i = 0; i < fours; i++) r = r * FOUR + info[i];
	for(int i = 0; i < threes; i++) r = r * THREE + info[fours + i];

	vector<int> perm = dp(fours, r);
	assert(ep(fours, perm) == r);
	return perm;
}

vector<int> blendwines(int k, vector<int> r){
	for(int& x : r) x -= 1;
	int n = (int)r.size();
	int num_big = min(TWELVE, n); // num_big
	int num_small = n - num_big;
	vector<int> small_perm;
	for(int a : r){
		if(a < num_small) small_perm.push_back(a);
	}
	assert((int)small_perm.size() == num_small);

	vector<int> info = encode_permutation(small_perm, num_small, num_big);
	assert(decode_permutation(info, num_small, num_big) == small_perm);

	int j = 0;
	vector<int> a(n);
	for(int i = 0; i < n; i++){
		if(r[i] < num_small){
			a[i] = THREE + 1 + info[j];
			j += 1;
		}
	}
	for(int i = 0; i < n; i++){
		if(r[i] >= num_small){
			a[i] = 1 + info[j];
			j += 1;
		}
	}
	return a;
}

bool cmp(int x, int y){
	ncalls += 1;
	return (ncalls <= 30) ? (Compare(x, y) == -1) : false;
}

vector<int> merge_sort(vector<int> x){
	if(x.size() <= 1) return x;
	vector<int> a, b;
	int n = (int)x.size();
	for(int i = 0; i < n/2; i++) a.push_back(x[i]);
	for(int i = n/2; i < n; i++) b.push_back(x[i]);
	a = merge_sort(a);
	b = merge_sort(b);
	int i = 0;
	int j = 0;
	vector<int> res;
	while(i < (int)a.size() && j < (int)b.size()){
		if(cmp(a[i], b[j])){
			res.push_back(a[i]);
			i += 1;
		} else {
			res.push_back(b[j]);
			j += 1;
		}
	}
	for(int k = i; k < (int)a.size(); k++) res.push_back(a[k]);
	for(int k = j; k < (int)b.size(); k++) res.push_back(b[k]);
	return res;
}

vector<int> merge_insertion_sort(vector<int> x){
	if(x.size() <= 1) return x;
	for(int i = 0; i + 1 < (int)x.size(); i += 2){
		if(!cmp(x[i], x[i+1])){
			swap(x[i], x[i+1]);
		}
	}
	vector<int> smalls;
	for(int i = 0; i + 1 < (int)x.size(); i += 2){
		smalls.push_back(x[i+1]);
	}
	smalls = merge_insertion_sort(smalls);
	for(int i = 0; i + 1 < (int)x.size(); i += 2){
		if(smalls.front() == x[i+1]){
			smalls.insert(smalls.begin(), x[i]);
		}
	}
	vector<int> y;
	for(int b = 2; b < (int)smalls.size(); b++){
		for(int i = 0; i + 1 < (int)x.size(); i += 2){
			if(smalls[b] == x[i+1]){
				y.push_back(x[i]);
			}
		}
	}
	if((int)x.size() & 1){
		y.push_back(x.back());
	}
	vector<int> arr = {4, 3, 6, 5, 12, 11, 10, 9, 8, 7, 22, 21, 20, 19, 18, 17, 16, 15, 14, 13};
	for(int v : arr){
		v -= 3;
		if(v >= (int)y.size()) continue;
		int el = y[v];

		int pos = (int)smalls.size();
		for(int i = 0; i + 1 < (int)x.size(); i += 2){
			if(el == x[i]){
				for(int j = 0; j < (int)smalls.size(); j++){
					if(smalls[j] == x[i+1]) pos = j;
				}
			}
		}
		int s = -1;
		int e = pos;
		while(s + 1 < e){
			int mid = (s + e) / 2;
			if(cmp(el, smalls[mid])){
				e = mid;
			} else {
				s = mid;
			}
		}

		smalls.insert(smalls.begin() + e, el);
	}
	assert(smalls.size() == x.size());
	return smalls;
}

vector<int> sortwines(int k, vector<int> a) {
	int n = (int)a.size();
	int num_big = min(TWELVE, n); // num_big
	int num_small = n - num_big;
	vector<int> info;
	for(int i = 0; i < n; i++) if(a[i] > THREE) info.push_back(a[i] - THREE - 1);
	assert((int)info.size() == num_small);
	for(int i = 0; i < n; i++) if(a[i] <= THREE) info.push_back(a[i] - 1);
	assert((int)info.size() == n);

	vector<int> perm = decode_permutation(info, num_small, num_big);
	assert(encode_permutation(perm, num_small, num_big) == info);
	int j = 0;
	vector<int> r(n, -1);

	vector<int> unknowns;
	for(int i = 0; i < n; i++){
		if(a[i] > THREE){
			r[i] = perm[j];
			j += 1;
		} else {
			unknowns.push_back(i);
		}
	}
	assert((int)unknowns.size() == num_big);
	mt19937 mt(time(0));
	shuffle(unknowns.begin(), unknowns.end(), mt);
	unknowns = merge_insertion_sort(unknowns);
	for(int i = 0; i < (int)unknowns.size(); i++){
		r[unknowns[i]] = i + num_small;
	}
	for(int& x : r) x += 1;
	return r;
}
}

vector<int> BlendWines(int k, vector<int> r){
	return blendwines(k, r);
}

#include "taster.h"
#include "bartender.h"
#include <bits/stdc++.h>

namespace {

using namespace std;

using big = __int128_t;

const int FOUR = 4;
const int THREE = 3;

const int TWELVE = 12;

int ncalls = 0;

big ep(int n, vector<int> perm){
	assert((int)perm.size() == n);
	big res = 0;
	for(int i = 0; i < n; i++){
		res *= (n - i);
		res += perm[i];
		for(int j = i+1; j < n; j++){
			if(perm[j] > perm[i]) perm[j] -= 1;
		}
	}
	return res;
}

vector<int> dp(int n, big val){
	vector<int> perm(n, 0);
	for(int i = n-1; i >= 0; i--){
		int ind = val % (n - i);
		val /= (n - i);
		perm[i] = ind;
		for(int j = i + 1; j < n; j++){
			if(perm[j] >= perm[i]) perm[j] += 1;
		}
	}
	return perm;
}

vector<int> encode_permutation(vector<int> perm, int fours, int threes){
	big a = 1;
	for(int i = 1; i <= fours; i++) a *= big(i);
	big c = 1;
	for(int i = 0; i < fours; i++) c *= FOUR;
	for(int i = 0; i < threes; i++) c *= THREE;
	assert(a <= c);

	assert(dp(fours, ep(fours, perm)) == perm);
	big val = ep(fours, perm);
	vector<int> z;
	for(int i = 0; i < threes; i++){
		z.push_back(int(val % THREE)); val /= THREE;
	}
	for(int i = 0; i < fours; i++){
		z.push_back(int(val % FOUR)); val /= FOUR;
	}
	assert(val == 0);
	reverse(z.begin(), z.end());
	return z;
}


vector<int> decode_permutation(vector<int> info, int fours, int threes){
	int n = (int)info.size();
	assert(n == fours + threes);
	big r = 0;
	for(int i = 0; i < fours; i++) r = r * FOUR + info[i];
	for(int i = 0; i < threes; i++) r = r * THREE + info[fours + i];

	vector<int> perm = dp(fours, r);
	assert(ep(fours, perm) == r);
	return perm;
}

vector<int> blendwines(int k, vector<int> r){
	for(int& x : r) x -= 1;
	int n = (int)r.size();
	int num_big = min(TWELVE, n); // num_big
	int num_small = n - num_big;
	vector<int> small_perm;
	for(int a : r){
		if(a < num_small) small_perm.push_back(a);
	}
	assert((int)small_perm.size() == num_small);

	vector<int> info = encode_permutation(small_perm, num_small, num_big);
	assert(decode_permutation(info, num_small, num_big) == small_perm);

	int j = 0;
	vector<int> a(n);
	for(int i = 0; i < n; i++){
		if(r[i] < num_small){
			a[i] = THREE + 1 + info[j];
			j += 1;
		}
	}
	for(int i = 0; i < n; i++){
		if(r[i] >= num_small){
			a[i] = 1 + info[j];
			j += 1;
		}
	}
	return a;
}

bool cmp(int x, int y){
	ncalls += 1;
	return (ncalls <= 30) ? (Compare(x, y) == -1) : false;
}

vector<int> merge_sort(vector<int> x){
	if(x.size() <= 1) return x;
	vector<int> a, b;
	int n = (int)x.size();
	for(int i = 0; i < n/2; i++) a.push_back(x[i]);
	for(int i = n/2; i < n; i++) b.push_back(x[i]);
	a = merge_sort(a);
	b = merge_sort(b);
	int i = 0;
	int j = 0;
	vector<int> res;
	while(i < (int)a.size() && j < (int)b.size()){
		if(cmp(a[i], b[j])){
			res.push_back(a[i]);
			i += 1;
		} else {
			res.push_back(b[j]);
			j += 1;
		}
	}
	for(int k = i; k < (int)a.size(); k++) res.push_back(a[k]);
	for(int k = j; k < (int)b.size(); k++) res.push_back(b[k]);
	return res;
}

vector<int> merge_insertion_sort(vector<int> x){
	if(x.size() <= 1) return x;
	for(int i = 0; i + 1 < (int)x.size(); i += 2){
		if(!cmp(x[i], x[i+1])){
			swap(x[i], x[i+1]);
		}
	}
	vector<int> smalls;
	for(int i = 0; i + 1 < (int)x.size(); i += 2){
		smalls.push_back(x[i+1]);
	}
	smalls = merge_insertion_sort(smalls);
	for(int i = 0; i + 1 < (int)x.size(); i += 2){
		if(smalls.front() == x[i+1]){
			smalls.insert(smalls.begin(), x[i]);
		}
	}
	vector<int> y;
	for(int b = 2; b < (int)smalls.size(); b++){
		for(int i = 0; i + 1 < (int)x.size(); i += 2){
			if(smalls[b] == x[i+1]){
				y.push_back(x[i]);
			}
		}
	}
	if((int)x.size() & 1){
		y.push_back(x.back());
	}
	vector<int> arr = {4, 3, 6, 5, 12, 11, 10, 9, 8, 7, 22, 21, 20, 19, 18, 17, 16, 15, 14, 13};
	for(int v : arr){
		v -= 3;
		if(v >= (int)y.size()) continue;
		int el = y[v];

		int pos = (int)smalls.size();
		for(int i = 0; i + 1 < (int)x.size(); i += 2){
			if(el == x[i]){
				for(int j = 0; j < (int)smalls.size(); j++){
					if(smalls[j] == x[i+1]) pos = j;
				}
			}
		}
		int s = -1;
		int e = pos;
		while(s + 1 < e){
			int mid = (s + e) / 2;
			if(cmp(el, smalls[mid])){
				e = mid;
			} else {
				s = mid;
			}
		}

		smalls.insert(smalls.begin() + e, el);
	}
	assert(smalls.size() == x.size());
	return smalls;
}

vector<int> sortwines(int k, vector<int> a) {
	int n = (int)a.size();
	int num_big = min(TWELVE, n); // num_big
	int num_small = n - num_big;
	vector<int> info;
	for(int i = 0; i < n; i++) if(a[i] > THREE) info.push_back(a[i] - THREE - 1);
	assert((int)info.size() == num_small);
	for(int i = 0; i < n; i++) if(a[i] <= THREE) info.push_back(a[i] - 1);
	assert((int)info.size() == n);

	vector<int> perm = decode_permutation(info, num_small, num_big);
	assert(encode_permutation(perm, num_small, num_big) == info);
	int j = 0;
	vector<int> r(n, -1);

	vector<int> unknowns;
	for(int i = 0; i < n; i++){
		if(a[i] > THREE){
			r[i] = perm[j];
			j += 1;
		} else {
			unknowns.push_back(i);
		}
	}
	assert((int)unknowns.size() == num_big);
	mt19937 mt(time(0));
	shuffle(unknowns.begin(), unknowns.end(), mt);
	unknowns = merge_insertion_sort(unknowns);
	for(int i = 0; i < (int)unknowns.size(); i++){
		r[unknowns[i]] = i + num_small;
	}
	for(int& x : r) x += 1;
	return r;
}
}

vector<int> SortWines(int k, vector<int> r){
	return sortwines(k, r);
}

Compilation message

bartender.cpp:199:13: warning: 'std::vector<int> {anonymous}::sortwines(int, std::vector<int>)' defined but not used [-Wunused-function]
 vector<int> sortwines(int k, vector<int> a) {
             ^~~~~~~~~

taster.cpp:79:13: warning: 'std::vector<int> {anonymous}::blendwines(int, std::vector<int>)' defined but not used [-Wunused-function]
 vector<int> blendwines(int k, vector<int> r){
             ^~~~~~~~~~

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 908 KB Correct
2 Correct 8 ms 772 KB Correct
3 Correct 9 ms 644 KB Correct
4 Correct 8 ms 844 KB Correct
5 Correct 10 ms 940 KB Correct
6 Correct 9 ms 908 KB Correct
7 Correct 9 ms 772 KB Correct
8 Correct 10 ms 804 KB Correct
9 Correct 10 ms 908 KB Correct
10 Correct 10 ms 772 KB Correct
11 Correct 9 ms 780 KB Correct
12 Correct 9 ms 644 KB Correct
13 Correct 10 ms 780 KB Correct
14 Correct 10 ms 644 KB Correct
15 Correct 8 ms 772 KB Correct
16 Correct 9 ms 908 KB Correct
17 Correct 9 ms 692 KB Correct
18 Correct 10 ms 908 KB Correct
19 Correct 10 ms 908 KB Correct
20 Correct 9 ms 908 KB Correct
21 Correct 8 ms 908 KB Correct
22 Correct 9 ms 772 KB Correct
23 Correct 8 ms 772 KB Correct
24 Correct 9 ms 968 KB Correct
25 Correct 9 ms 780 KB Correct
26 Correct 9 ms 772 KB Correct
27 Correct 10 ms 780 KB Correct
28 Correct 10 ms 972 KB Correct
29 Correct 9 ms 908 KB Correct
30 Correct 10 ms 924 KB Correct
31 Correct 10 ms 800 KB Correct
32 Correct 9 ms 772 KB Correct
33 Correct 9 ms 780 KB Correct
34 Correct 8 ms 772 KB Correct
35 Correct 8 ms 644 KB Correct
36 Correct 10 ms 644 KB Correct
37 Correct 9 ms 772 KB Correct
38 Correct 10 ms 644 KB Correct
39 Correct 10 ms 908 KB Correct
40 Correct 9 ms 644 KB Correct
41 Correct 10 ms 780 KB Correct
42 Correct 9 ms 780 KB Correct
43 Correct 10 ms 772 KB Correct
44 Correct 11 ms 772 KB Correct
45 Correct 11 ms 780 KB Correct
46 Correct 9 ms 908 KB Correct
47 Correct 9 ms 784 KB Correct
48 Correct 10 ms 772 KB Correct
49 Correct 11 ms 772 KB Correct
50 Correct 10 ms 908 KB Correct
51 Correct 9 ms 1016 KB Correct
52 Correct 9 ms 876 KB Correct
53 Correct 10 ms 772 KB Correct
54 Correct 10 ms 792 KB Correct
55 Correct 9 ms 784 KB Correct
56 Correct 10 ms 844 KB Correct
57 Correct 8 ms 644 KB Correct
58 Correct 8 ms 908 KB Correct
59 Correct 9 ms 772 KB Correct
60 Correct 8 ms 772 KB Correct
61 Correct 10 ms 908 KB Correct
62 Correct 8 ms 780 KB Correct
63 Correct 9 ms 772 KB Correct
64 Correct 8 ms 880 KB Correct
65 Correct 9 ms 644 KB Correct
66 Correct 9 ms 780 KB Correct
67 Correct 9 ms 780 KB Correct
68 Correct 9 ms 772 KB Correct
69 Correct 9 ms 888 KB Correct
70 Correct 9 ms 1004 KB Correct
71 Correct 10 ms 908 KB Correct
72 Correct 8 ms 772 KB Correct
73 Correct 10 ms 756 KB Correct
74 Correct 9 ms 1148 KB Correct
75 Correct 9 ms 772 KB Correct
76 Correct 8 ms 772 KB Correct
77 Correct 8 ms 644 KB Correct
78 Correct 9 ms 780 KB Correct
79 Correct 10 ms 908 KB Correct
80 Correct 9 ms 908 KB Correct
81 Correct 10 ms 772 KB Correct
82 Correct 9 ms 780 KB Correct
83 Correct 9 ms 772 KB Correct
84 Correct 10 ms 908 KB Correct
85 Correct 9 ms 908 KB Correct
86 Correct 9 ms 644 KB Correct
87 Correct 9 ms 780 KB Correct
88 Correct 10 ms 772 KB Correct
89 Correct 9 ms 780 KB Correct
90 Correct 8 ms 772 KB Correct
91 Correct 9 ms 772 KB Correct
92 Correct 8 ms 644 KB Correct
93 Correct 9 ms 908 KB Correct
94 Correct 9 ms 908 KB Correct
95 Correct 10 ms 888 KB Correct
96 Correct 10 ms 644 KB Correct
97 Correct 10 ms 772 KB Correct
98 Correct 9 ms 780 KB Correct
99 Correct 9 ms 784 KB Correct
100 Correct 9 ms 908 KB Correct
101 Correct 8 ms 772 KB Correct
102 Correct 10 ms 908 KB Correct
103 Correct 9 ms 772 KB Correct
104 Correct 10 ms 772 KB Correct
105 Correct 9 ms 780 KB Correct
106 Correct 10 ms 772 KB Correct
107 Correct 9 ms 772 KB Correct
108 Correct 9 ms 772 KB Correct
109 Correct 9 ms 772 KB Correct
110 Correct 9 ms 644 KB Correct
111 Correct 8 ms 772 KB Correct
112 Correct 9 ms 908 KB Correct
113 Correct 8 ms 908 KB Correct
114 Correct 9 ms 908 KB Correct
115 Correct 9 ms 644 KB Correct
116 Correct 9 ms 908 KB Correct
117 Correct 8 ms 772 KB Correct
118 Correct 9 ms 784 KB Correct
119 Correct 8 ms 772 KB Correct
120 Correct 8 ms 772 KB Correct