oj.uz

답안 #830348

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
830348 2023-08-19T04:11:56 Z skittles1412 저울 (IOI15_scales) C++17
100 / 100
 160 ms 2544 KB 
#include "bits/extc++.h"

using namespace std;

template <typename T, typename... U>
void dbgh(const T& t, const U&... u) {
cerr << t;
((cerr << " | " << u), ...);
cerr << endl;
}

#ifdef DEBUG
#define dbg(...)  \
cerr << "L" << __LINE__ << " [" << #__VA_ARGS__ << "]: "; \
dbgh(__VA_ARGS__)
#else
#define dbg(...)
#define cerr   \
if (false) \
cerr
#endif

using u64 = uint64_t;

#define endl "\n"
#define long int64_t
#define sz(x) int(std::size(x))

#ifdef __cplusplus
extern "C" {
#endif

void init(int T);
void orderCoins();
void answer(int W[]);

int getMedian(int A, int B, int C);
int getHeaviest(int A, int B, int C);
int getLightest(int A, int B, int C);
int getNextLightest(int A, int B, int C, int D);

#ifdef __cplusplus
}
#endif

struct G {
int q_median(int a, int b, int c) {
return getMedian(a + 1, b + 1, c + 1) - 1;
}
int q_heaviest(int a, int b, int c) {
return getHeaviest(a + 1, b + 1, c + 1) - 1;
}
int q_lightest(int a, int b, int c) {
return getLightest(a + 1, b + 1, c + 1) - 1;
}
int q_next_lightest(int a, int b, int c, int d) {
return getNextLightest(a + 1, b + 1, c + 1, d + 1) - 1;
}
} G;

template <typename Cb>
struct Cmp {
Cb cb;

Cmp(Cb cb) : cb(cb) {}

template <typename T>
bool operator()(const T& a, const T& b) const {
return cb(a) < cb(b);
}
};

template <typename T>
ostream& operator<<(ostream& out, const vector<T>& arr) {
out << "[";
for (int i = 0; i < sz(arr); i++) {
if (i) {
out << ", ";
}
out << arr[i];
}
return out << "]";
}

vector<vector<int>> perms;

array<int, 3> sorted(int o, int a, int b, int c) {
array<int, 3> ans {a, b, c};
sort(begin(ans), end(ans), Cmp([&](int u) -> int { return perms[o][u]; }));
return ans;
}

int q_median(int o, int a, int b, int c) {
return sorted(o, a, b, c)[1];
}

int q_lightest(int o, int a, int b, int c) {
return sorted(o, a, b, c)[0];
}

int q_heaviest(int o, int a, int b, int c) {
return sorted(o, a, b, c)[2];
}

int q_next_lightest(int o, int a, int b, int c, int d) {
Cmp cmp([&](int u) -> int { return perms[o][u]; });

vector<int> gt;
for (auto& i : {a, b, c}) {
if (perms[o][i] > perms[o][d]) {
gt.push_back(i);
}
}
if (sz(gt)) {
return *min_element(begin(gt), end(gt), cmp);
}

return q_lightest(o, a, b, c);
}

u64 r_vals[720];
int p_mul[720][720];
map<u64, int> memo;

int dp(const vector<int>& arr) {
if (sz(arr) <= 1) {
return 0;
}
int p3 = 1, log3 = 0;
while (p3 < sz(arr)) {
p3 *= 3;
log3++;
}

u64 k_hash = 0;
for (auto& a : arr) {
k_hash += r_vals[a];
}

auto [it, inserted] = memo.emplace(k_hash, 0);
int& ans = it->second;
if (!inserted) {
return ans;
}

ans = 1e9;

for (int i = 0; i < 6; i++) {
for (int j = i + 1; j < 6; j++) {
for (int k = j + 1; k < 6; k++) {
auto go = [&](auto cb) -> void {
if (ans == log3) {
return;
}

vector<int> out[3];

for (auto& o : arr) {
int res = cb(o);
if (res == i) {
out[0].push_back(o);
} else if (res == j) {
out[1].push_back(o);
} else {
assert(res == k);
out[2].push_back(o);
}
}

if (max({sz(out[0]), sz(out[1]), sz(out[2])}) > p3 / 3) {
return;
}

assert(sz(out[0]) + sz(out[1]) + sz(out[2]) == sz(arr));
ans =
min(ans, 1 + max({dp(out[0]), dp(out[1]), dp(out[2])}));
};

go([&](int o) -> int { return q_lightest(o, i, j, k); });
go([&](int o) -> int { return q_heaviest(o, i, j, k); });
go([&](int o) -> int { return q_median(o, i, j, k); });
for (int d = 0; d < 6; d++) {
if (d == i || d == j || d == k) {
continue;
}
go([&](int o) -> int {
return q_next_lightest(o, i, j, k, d);
});
}
}
}
}

return ans;
}

void init(int) {
{
mt19937_64 cowng(1412);
for (auto& a : r_vals) {
a = cowng();
}
}

vector<int> perm(6);
iota(begin(perm), end(perm), 0);
do {
perms.push_back(perm);
} while (next_permutation(begin(perm), end(perm)));

for (int i = 0; i < 720; i++) {
for (int j = 0; j < 720; j++) {
auto tmp = perms[i];
for (auto& a : tmp) {
a = perms[j][a];
}
p_mul[i][j] =
int(lower_bound(begin(perms), end(perms), tmp) - perms.begin());
}
}

vector<int> arr(720);
iota(begin(arr), end(arr), 0);

arr.erase(remove_if(begin(arr), end(arr),
[&](int o) -> bool {
return q_next_lightest(o, 0, 1, 2, 3) != 0;
}),
  arr.end());

dbg(dp({}));
dbg(sz(arr));
dbg(dp(arr));
dbg(sz(memo));
}

void print(vector<int> arr) {
if (sz(arr) <= 1) {
vector<int> ans(6);
auto c_arr = perms[arr[0]];
for (int i = 0; i < 6; i++) {
ans[c_arr[i]] = i + 1;
}
answer(ans.data());
return;
}
int p3 = 1;
while (p3 < sz(arr)) {
p3 *= 3;
}

int ans = dp(arr);
dbg(ans);

for (int i = 0; i < 6; i++) {
for (int j = i + 1; j < 6; j++) {
for (int k = j + 1; k < 6; k++) {
auto go = [&](auto cb) -> bool {
vector<int> out[3];

for (auto& o : arr) {
int res = cb(o);
if (res == i) {
out[0].push_back(o);
} else if (res == j) {
out[1].push_back(o);
} else {
assert(res == k);
out[2].push_back(o);
}
}

if (max({sz(out[0]), sz(out[1]), sz(out[2])}) > p3 / 3) {
return false;
}

assert(sz(out[0]) + sz(out[1]) + sz(out[2]) == sz(arr));
if (1 + max({dp(out[0]), dp(out[1]), dp(out[2])}) == ans) {
return true;
}
return false;
};

if (go([&](int o) -> int { return q_lightest(o, i, j, k); })) {
int res = G.q_lightest(i, j, k);
arr.erase(remove_if(begin(arr), end(arr),
[&](int o) -> bool {
return q_lightest(o, i, j, k) !=
   res;
}),
  arr.end());
print(arr);
return;
}
if (go([&](int o) -> int { return q_heaviest(o, i, j, k); })) {
int res = G.q_heaviest(i, j, k);
arr.erase(remove_if(begin(arr), end(arr),
[&](int o) -> bool {
return q_heaviest(o, i, j, k) !=
   res;
}),
  arr.end());
print(arr);
return;
}
if (go([&](int o) -> int { return q_median(o, i, j, k); })) {
int res = G.q_median(i, j, k);
arr.erase(remove_if(begin(arr), end(arr),
[&](int o) -> bool {
return q_median(o, i, j, k) != res;
}),
  arr.end());
print(arr);
return;
}
for (int d = 0; d < 6; d++) {
if (d == i || d == j || d == k) {
continue;
}
if (go([&](int o) -> int {
return q_next_lightest(o, i, j, k, d);
})) {
int res = G.q_next_lightest(i, j, k, d);
arr.erase(remove_if(begin(arr), end(arr),
[&](int o) -> bool {
return q_next_lightest(o, i, j,
   k, d) !=
   res;
}),
  arr.end());
print(arr);
return;
}
}
}
}
}

assert(false);
}

void orderCoins() {
vector<int> arr(720);
iota(begin(arr), end(arr), 0);
print(arr);
}

Compilation message

scales.cpp: In constructor 'Cmp<Cb>::Cmp(Cb)':
scales.cpp:65:8: warning: declaration of 'cb' shadows a member of 'Cmp<Cb>' [-Wshadow]
   65 | Cmp(Cb cb) : cb(cb) {}
      |     ~~~^~
scales.cpp:63:4: note: shadowed declaration is here
   63 | Cb cb;
      |    ^~
scales.cpp: In instantiation of 'Cmp<Cb>::Cmp(Cb) [with Cb = sorted(int, int, int, int)::<lambda(int)>]':
scales.cpp:89:73:   required from here
scales.cpp:65:8: warning: declaration of 'cb' shadows a member of 'Cmp<sorted(int, int, int, int)::<lambda(int)> >' [-Wshadow]
   65 | Cmp(Cb cb) : cb(cb) {}
      |     ~~~^~
scales.cpp:63:4: note: shadowed declaration is here
   63 | Cb cb;
      |    ^~
scales.cpp:65:8: warning: declaration of 'cb' shadows a member of 'Cmp<sorted(int, int, int, int)::<lambda(int)> >' [-Wshadow]
   65 | Cmp(Cb cb) : cb(cb) {}
      |     ~~~^~
scales.cpp:63:4: note: shadowed declaration is here
   63 | Cb cb;
      |    ^~
scales.cpp:65:8: warning: declaration of 'cb' shadows a member of 'Cmp<sorted(int, int, int, int)::<lambda(int)> >' [-Wshadow]
   65 | Cmp(Cb cb) : cb(cb) {}
      |     ~~~^~
scales.cpp:63:4: note: shadowed declaration is here
   63 | Cb cb;
      |    ^~
scales.cpp: In instantiation of 'Cmp<Cb>::Cmp(Cb) [with Cb = q_next_lightest(int, int, int, int, int)::<lambda(int)>]':
scales.cpp:106:50:   required from here
scales.cpp:65:8: warning: declaration of 'cb' shadows a member of 'Cmp<q_next_lightest(int, int, int, int, int)::<lambda(int)> >' [-Wshadow]
   65 | Cmp(Cb cb) : cb(cb) {}
      |     ~~~^~
scales.cpp:63:4: note: shadowed declaration is here
   63 | Cb cb;
      |    ^~
scales.cpp:65:8: warning: declaration of 'cb' shadows a member of 'Cmp<q_next_lightest(int, int, int, int, int)::<lambda(int)> >' [-Wshadow]
   65 | Cmp(Cb cb) : cb(cb) {}
      |     ~~~^~
scales.cpp:63:4: note: shadowed declaration is here
   63 | Cb cb;
      |    ^~
scales.cpp:65:8: warning: declaration of 'cb' shadows a member of 'Cmp<q_next_lightest(int, int, int, int, int)::<lambda(int)> >' [-Wshadow]
   65 | Cmp(Cb cb) : cb(cb) {}
      |     ~~~^~
scales.cpp:63:4: note: shadowed declaration is here
   63 | Cb cb;
      |    ^~

Subtask #1
100.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 133 ms 2348 KB Output is correct
2 Correct 136 ms 2364 KB Output is correct
3 Correct 134 ms 2420 KB Output is correct
4 Correct 134 ms 2344 KB Output is correct
5 Correct 134 ms 2544 KB Output is correct
6 Correct 138 ms 2504 KB Output is correct
7 Correct 134 ms 2412 KB Output is correct
8 Correct 134 ms 2376 KB Output is correct
9 Correct 133 ms 2428 KB Output is correct
10 Correct 140 ms 2508 KB Output is correct
11 Correct 134 ms 2368 KB Output is correct
12 Correct 134 ms 2372 KB Output is correct
13 Correct 140 ms 2388 KB Output is correct
14 Correct 137 ms 2512 KB Output is correct
15 Correct 133 ms 2312 KB Output is correct
16 Correct 133 ms 2312 KB Output is correct
17 Correct 138 ms 2392 KB Output is correct
18 Correct 135 ms 2480 KB Output is correct
19 Correct 135 ms 2344 KB Output is correct
20 Correct 134 ms 2336 KB Output is correct
21 Correct 133 ms 2316 KB Output is correct
22 Correct 134 ms 2332 KB Output is correct
23 Correct 133 ms 2412 KB Output is correct
24 Correct 134 ms 2380 KB Output is correct
25 Correct 137 ms 2384 KB Output is correct
26 Correct 135 ms 2352 KB Output is correct
27 Correct 135 ms 2428 KB Output is correct
28 Correct 160 ms 2344 KB Output is correct
29 Correct 133 ms 2336 KB Output is correct
30 Correct 144 ms 2380 KB Output is correct
31 Correct 137 ms 2428 KB Output is correct
32 Correct 150 ms 2392 KB Output is correct
33 Correct 134 ms 2344 KB Output is correct
34 Correct 144 ms 2468 KB Output is correct
35 Correct 134 ms 2360 KB Output is correct
36 Correct 155 ms 2384 KB Output is correct
37 Correct 134 ms 2396 KB Output is correct
38 Correct 134 ms 2360 KB Output is correct
39 Correct 138 ms 2312 KB Output is correct
40 Correct 134 ms 2420 KB Output is correct