oj.uz

Submission #150291

# Submission time Handle Problem Language Result Execution time Memory
150291 2019-09-01T08:04:40 Z 1 WA = 5 Push Up(#3624, BaaaaaaaaaaaaaaaarkingDog, IohcEjnim, 0xrgb) Wine Tasting (FXCUP4_wine) C++17
57 / 100
 14 ms 1036 KB 
// K = 11
#include <vector>

#include "bartender.h"

std::vector<int> BlendWines(int K, std::vector<int> R) {
	const int N = R.size();
	std::vector<int> v(N, 1);

	constexpr int DATA[] = {
		0,
		1, 10, 1, 10, 1, 10,
		2, 9, 2, 9, 2, 9,
		3, 8, 3, 8, 3, 8,
		4, 7, 4, 7, 4, 7,
		5, 6, 5, 6, 5, 6,
	};

	if (K < 11) return v; // lol
	for (int i = 0; i < N; ++i) v[i] = DATA[R[i]];
	return v;
}

// K = 11
#include <algorithm>
#include <vector>

#include "taster.h"

static std::vector<int> chk2(int a, int b) {
	if (Compare(a, b) < 0) return { a, b };
	return { b, a };
}

static std::vector<int> chk3(int a, int b, int c) {
	const int r1 = Compare(a, b);
	const int r2 = Compare(b, c);
	const int r3 = Compare(c, a);

	if (r1 < 0 && r2 < 0) return { a, b, c };
	if (r2 < 0 && r3 < 0) return { b, c, a };
	if (r1 < 0 && r3 < 0) return { c, a, b };
	if (r1 < 0) return { a, c, b };
	if (r2 < 0) return { b, a, c };
	return { c, b, a };
}

static std::vector<int> chk33(int a, int b, int c, int x, int y, int z) {
	if (Compare(a, y) < 0) {
		// x < a < y
		if (Compare(b, z) < 0) return { a, b, c };
		else return { a, c, b };
	}
	else if (Compare(a, z) < 0) {
		// y < a < z
		if (Compare(b, y) < 0) return { b, a, c };
		else return { c, a, b };
	}
	else {
		// z < a
		if (Compare(b, y) < 0) return { b, c, a };
		else return { c, b, a };
	}
}

std::vector<int> SortWines(int K, std::vector<int> A) {
	int N = A.size();
	std::vector<int> ans(N);

	if (K < 11) {
		std::vector<int> rank(N);
		for (int i = 0; i < N; ++i) rank[i] = i;
		std::sort(rank.begin(), rank.end(), [](int x, int y) {
			return (Compare(x, y) < 0);
		});
		for (int i = 0; i < N; ++i) ans[rank[i]] = i + 1;
		return ans;
	}

	int cnt = 0;
	for (int i = 1; i <= 5; ++i) {
		std::vector<int> sm, lg;
		for (int j = 0; j < N; ++j) {
			if (A[j] == i) sm.push_back(j);
			if (A[j] == 11 - i) lg.push_back(j);
		}

		if (sm.size() == 0) break;
		else if (sm.size() == 1) {
			ans[sm[0]] = ++cnt;
			if (lg.size() == 1) ans[lg[0]] = ++cnt;
		}
		else if (sm.size() == 2) {
			auto tmp = chk2(sm[0], sm[1]);
			if (lg.size() == 1) {
				ans[tmp[0]] = ++cnt;
				ans[lg[0]] = ++cnt;
				ans[tmp[1]] = ++cnt;
			}
			else { // lg.size() == 2
				if (Compare(lg[0], tmp[1]) < 0) {
					// tmp[0] lg[0] tmp[1] lg[1]
					ans[tmp[0]] = ++cnt;
					ans[lg[0]] = ++cnt;
					ans[tmp[1]] = ++cnt;
					ans[lg[1]] = ++cnt;
				}
				else {
					ans[tmp[0]] = ++cnt;
					ans[lg[1]] = ++cnt;
					ans[tmp[1]] = ++cnt;
					ans[lg[0]] = ++cnt;
				}
			}
		}
		else {
			auto tmp = chk3(sm[0], sm[1], sm[2]);
			std::vector<int> rr;
			if (lg.size() == 3) {
				rr = chk33(lg[0], lg[1], lg[2], tmp[0], tmp[1], tmp[2]);
			}
			else {
				rr = chk33(lg[0], lg[1], -1, tmp[0], tmp[1], tmp[2]);
			}

			ans[tmp[0]] = ++cnt;
			if (rr[0] >= 0) ans[rr[0]] = ++cnt;
			ans[tmp[1]] = ++cnt;
			if (rr[1] >= 0) ans[rr[1]] = ++cnt;
			ans[tmp[2]] = ++cnt;
			if (rr[2] >= 0) ans[rr[2]] = ++cnt;
		}
	}

	return ans;
}

Subtask #1
57.0 / 100.0

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