結果
| 問題 | No.5020 Averaging |
| ユーザー |
 さはら
|
| 提出日時 | 2024-02-25 17:18:25 |
| 言語 | C++23 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 55,641 bytes |
| コンパイル時間 | 5,663 ms |
| コンパイル使用メモリ | 260,092 KB |
| 実行使用メモリ | 26,676 KB |
| スコア | 0 |
| 最終ジャッジ日時 | 2024-02-25 17:19:18 |
| 合計ジャッジ時間 | 51,366 ms |
|
ジャッジサーバーID （参考情報） |
judge15 / judge14 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | WA | - |
| testcase_01 | WA | - |
| testcase_02 | WA | - |
| testcase_03 | WA | - |
| testcase_04 | WA | - |
| testcase_05 | WA | - |
| testcase_06 | WA | - |
| testcase_07 | WA | - |
| testcase_08 | WA | - |
| testcase_09 | WA | - |
| testcase_10 | WA | - |
| testcase_11 | WA | - |
| testcase_12 | WA | - |
| testcase_13 | WA | - |
| testcase_14 | WA | - |
| testcase_15 | WA | - |
| testcase_16 | WA | - |
| testcase_17 | WA | - |
| testcase_18 | WA | - |
| testcase_19 | WA | - |
| testcase_20 | WA | - |
| testcase_21 | WA | - |
| testcase_22 | WA | - |
| testcase_23 | WA | - |
| testcase_24 | WA | - |
| testcase_25 | WA | - |
| testcase_26 | WA | - |
| testcase_27 | WA | - |
| testcase_28 | WA | - |
| testcase_29 | WA | - |
| testcase_30 | WA | - |
| testcase_31 | WA | - |
| testcase_32 | WA | - |
| testcase_33 | WA | - |
| testcase_34 | WA | - |
| testcase_35 | WA | - |
| testcase_36 | WA | - |
| testcase_37 | WA | - |
| testcase_38 | WA | - |
| testcase_39 | WA | - |
| testcase_40 | WA | - |
| testcase_41 | WA | - |
| testcase_42 | WA | - |
| testcase_43 | WA | - |
| testcase_44 | WA | - |
| testcase_45 | WA | - |
| testcase_46 | WA | - |
| testcase_47 | WA | - |
| testcase_48 | WA | - |
| testcase_49 | WA | - |
ソースコード
#ifdef ONLINE_JUDGE
#define NDEBUG
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#else
#undef NDEBUG
#endif
#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <chrono>
#include <cmath>
#include <complex>
#include <concepts>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <fstream>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <memory>
#include <mutex>
#include <numeric>
#include <optional>
#include <queue>
#include <ranges>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <thread>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
namespace shr {
namespace basic {
using namespace std;
using uchar = unsigned char;
using uint = unsigned int;
using ushort = unsigned short;
using ull = unsigned long long;
using ll = long long;
using pii = pair<int, int>;
using pdi = pair<double, int>;
template <class T>
concept printable = requires(T t, ostream& out) { out << t; };
int len(const string& a) {
return (int) a.length();
}
template <class T>
int len(const vector<T>& a) {
return (int) a.size();
}
template <class T>
int len(const set<T>& a) {
return (int) a.size();
}
template <class T>
int len(const deque<T>& a) {
return (int) a.size();
}
template <class T>
int len(const priority_queue<T>& a) {
return (int) a.size();
}
template <class T, int N>
int len(const T (&a)[N]) {
return N;
}
template <class T, int N>
void clear_with(T (&a)[N], int val) {
memset(a, val, sizeof(a));
}
template <totally_ordered T>
bool update_min(T candidate, T& current_min) {
if (candidate < current_min) {
current_min = candidate;
return true;
}
return false;
}
template <totally_ordered T>
bool update_min_eq(T candidate, T& current_min) {
if (candidate <= current_min) {
current_min = candidate;
return true;
}
return false;
}
template <totally_ordered T>
bool update_max(T candidate, T& current_max) {
if (candidate > current_max) {
current_max = candidate;
return true;
}
return false;
}
template <totally_ordered T>
bool update_max_eq(T candidate, T& current_max) {
if (candidate >= current_max) {
current_max = candidate;
return true;
}
return false;
}
template <class T>
string tos(T a) {
return to_string(a);
}
template <printable T>
string tos(T a) {
ostringstream os;
os << a;
return os.str();
}
constexpr double linearstep(double edge0, double edge1, double t) {
return clamp((t - edge0) / (edge1 - edge0), 0.0, 1.0);
}
constexpr double smoothstep(double edge0, double edge1, double t) {
t = linearstep(edge0, edge1, t);
return t * t * (3 - 2 * t);
}
double exp_interp(double from, double to, double t) {
return pow(from, 1 - t) * pow(to, t);
}
} // namespace basic
using namespace basic;
namespace timer {
double time_scale = 1.0;
// return in ms
int timer(bool reset = false) {
static auto st = chrono::system_clock::now();
if (reset) {
st = chrono::system_clock::now();
return 0;
} else {
auto en = chrono::system_clock::now();
int elapsed = (int) chrono::duration_cast<chrono::milliseconds>(en - st).count();
return (int) round(elapsed / time_scale);
}
}
} // namespace timer
namespace tracer {
bool debug = true;
template <class T>
concept is_pair = requires(T t) {
t.first;
t.second;
};
template <class T>
concept has_str = requires(T t) {
{ t.str() } -> convertible_to<string>;
};
template <printable T>
void tracen(T&& t) {
if (!debug)
return;
cerr << t;
}
template <class T>
requires(has_str<T> && !printable<T>)
void tracen(T&& t) {
if (!debug)
return;
cerr << t.str();
}
template <class T, class U>
void tracen(pair<T, U>& t) { // <- ?????????????????????? need this for trace(<iterable of pairs>)
if (!debug)
return;
cerr << "(";
tracen(t.first);
cerr << ", ";
tracen(t.second);
cerr << ")";
}
template <class T, class U>
void tracen(pair<T, U>&& t) { // <- ?????????????????????? need this for trace(make_pair(1, 2))
if (!debug)
return;
cerr << "(";
tracen(t.first);
cerr << ", ";
tracen(t.second);
cerr << ")";
}
template <class T>
requires(!printable<T>)
void tracen(T&& t) {
if (!debug)
return;
bool first = true;
auto from = t.begin();
auto until = t.end();
cerr << "{";
while (from != until) {
if (first) {
first = false;
} else {
cerr << ", ";
}
tracen(*from);
from++;
}
cerr << "}";
}
template <class T, int N>
requires(!same_as<decay_t<T>, char>)
void tracen(T (&a)[N]) {
if (!debug)
return;
cerr << "{";
for (int i = 0; i < N; i++) {
if (i > 0)
cerr << ", ";
tracen(a[i]);
}
cerr << "}";
}
template <class T1, class T2, class... Rest>
void tracen(T1&& t1, T2&& t2, Rest&&... rest) {
if (!debug)
return;
tracen(forward<T1>(t1));
tracen(forward<T2>(t2), forward<Rest>(rest)...);
}
void trace() {
if (!debug)
return;
cerr << endl;
}
template <class T, class... Rest>
void trace(T&& t, Rest&&... rest) {
if (!debug)
return;
tracen(forward<T>(t), forward<Rest>(rest)...);
cerr << endl;
}
template <class T>
requires(!printable<T>)
void trace2d(T&& t, int h, int w) {
if (!debug)
return;
bool first = true;
auto from = t.begin();
auto until = t.end();
for (int i = 0; i < h; i++) {
for (int j = 0; j < w; j++) {
if (j > 0)
tracen(" ");
tracen(*from);
from++;
if (j == w - 1)
trace();
}
}
}
template <class T, int N>
requires(!same_as<decay_t<T>, char>)
void trace2d(T (&a)[N], int h, int w) {
if (!debug)
return;
int idx = 0;
for (int i = 0; i < h; i++) {
for (int j = 0; j < w; j++) {
if (j > 0)
tracen(" ");
tracen(a[idx]);
idx++;
if (j == w - 1)
trace();
}
}
}
} // namespace tracer
using namespace tracer;
namespace random {
class rngen {
public:
rngen() {
}
rngen(int s) {
seed(s);
}
ull get_state() {
return state;
}
void set_state(ull state) {
this->state = state;
}
void seed(int s) {
state = s + INCR;
next32();
}
int next_int() {
return next31();
}
int next_int(int mod) {
assert(mod > 0);
return (int) ((ull) next31() * mod >> 31);
}
int next_int(int min, int max) {
return min + next_int(max - min + 1);
}
uint next_uint() {
return next32();
}
ull next_ull() {
return (ull) next32() << 32 | next32();
}
double next_float() {
return (double) next31() / 0x80000000;
}
double next_float(double min, double max) {
return min + next_float() * (max - min);
}
double next_normal() {
return sqrt(-2 * log(next_float())) * cos(6.283185307179586 * next_float());
}
double next_normal(double mean, double sigma) {
return mean + next_normal() * sigma;
}
private:
static constexpr ull MULT = 0x8b46ad15ae59daadull;
static constexpr ull INCR = 0xf51827be20401689ull;
ull state = (ull) chrono::duration_cast<chrono::nanoseconds>(
chrono::system_clock::now().time_since_epoch())
.count();
uint next32() {
uint r = (uint) (state >> 59);
state = state * MULT + INCR;
state ^= state >> 18;
uint t = (uint) (state >> 27);
return t >> r | t << (-r & 31);
}
int next31() {
return (int) (next32() & 0x7fffffff);
}
};
void random_permutation(int* a, int n, rngen& rng) {
assert(n >= 0);
if (n == 0)
return;
a[0] = 0;
for (int i = 1; i < n; i++) {
a[i] = i;
swap(a[i], a[rng.next_int(i + 1)]);
}
}
template <class RandomAccessContainer>
auto& random_pick(RandomAccessContainer& c, rngen& rng) {
return c[rng.next_int(len(c))];
}
template <class RandomAccessContainer>
const auto& random_pick(const RandomAccessContainer& c, rngen& rng) {
return c[rng.next_int(len(c))];
}
template <class T, int N>
T& random_pick(T (&c)[N], rngen& rng) {
return c[rng.next_int(N)];
}
template <class T, int N>
const T& random_pick(const T (&c)[N], rngen& rng) {
return c[rng.next_int(N)];
}
} // namespace random
using namespace random;
namespace ds {
// random access: O(1)
// push: O(1)
// insert: n/a
// erase by position: O(1)
// erase by element: n/a
// max size: fixed
template <class T, int N>
class fast_vector {
private:
T data[N];
int num = 0;
public:
using iterator = T*;
using const_iterator = const T*;
iterator begin() {
return data;
}
iterator end() {
return data + num;
}
const_iterator begin() const {
return data;
}
const_iterator end() const {
return data + num;
}
void push_back(T a) {
assert(num < N);
data[num++] = a;
}
template <class... Args>
void emplace_back(Args&&... args) {
push_back(T(forward<Args>(args)...));
}
void erase(iterator where) {
assert(where >= begin() && where < end());
*where = data[--num];
}
void pop_back() {
assert(num > 0);
num--;
}
T& operator[](int i) {
assert(i >= 0 && i < num);
return data[i];
}
const T& operator[](int i) const {
assert(i >= 0 && i < num);
return data[i];
}
int size() const {
return num;
}
};
// random access: O(1)
// push: O(1)
// insert: n/a
// erase: n/a
// reallocation: never
template <class T, int UnitBits = 20>
class increasing_vector {
private:
static constexpr int UNIT_SIZE = 1 << UnitBits;
static constexpr int UNIT_MASK = UNIT_SIZE - 1;
T** packs;
int num_packs = 0;
int num_total = 0;
public:
increasing_vector(const increasing_vector& vec) = delete;
increasing_vector& operator=(const increasing_vector& vec) = delete;
increasing_vector() : packs(new T*[65536]) {
}
~increasing_vector() {
for (int i = 0; i < num_packs; i++) {
delete[] packs[i];
}
delete[] packs;
}
T* next_pointer() {
if ((num_total++ & UNIT_MASK) == 0) {
packs[num_packs++] = new T[UNIT_SIZE];
}
return &(*this)[num_total - 1];
}
void push_back(T a) {
*next_pointer() = a;
}
template <class... Args>
void emplace_back(Args&&... args) {
push_back(T(forward<Args>(args)...));
}
T& operator[](int i) {
assert(i >= 0 && i < num_total);
return packs[i >> UnitBits][i & UNIT_MASK];
}
const T& operator[](int i) const {
assert(i >= 0 && i < num_total);
return packs[i >> UnitBits][i & UNIT_MASK];
}
int size() const {
return num_total;
}
};
// random access: O(1)
// insert: O(1)
// erase: O(1)
// check: O(1)
// max value: fixed
template <int N>
class fast_iset {
private:
int data[N];
int indices[N];
int num = 0;
public:
using iterator = int*;
using const_iterator = const int*;
fast_iset() {
memset(indices, -1, sizeof(indices));
}
iterator begin() {
return data;
}
iterator end() {
return data + num;
}
const_iterator begin() const {
return data;
}
const_iterator end() const {
return data + num;
}
bool insert(int a) {
assert(a >= 0 && a < N);
if (indices[a] != -1)
return false;
data[num] = a;
indices[a] = num;
num++;
return true;
}
bool erase(int a) {
assert(a >= 0 && a < N);
int index = indices[a];
if (index == -1)
return false;
assert(num > 0);
indices[data[index] = data[--num]] = index;
indices[a] = -1;
return true;
}
void clear() {
memset(indices, -1, sizeof(indices));
num = 0;
}
bool contains(int a) const {
return indices[a] != -1;
}
const int& operator[](int i) const {
assert(i >= 0 && i < num);
return data[i];
}
int size() const {
return num;
}
bool empty() const {
return num == 0;
}
};
// insert: O(1)
// get/set: O(1)
// clear: O(1)
// erase: n/a
template <class T, int BucketBits = 20>
class hash_imap {
private:
static constexpr int BUCKET_SIZE = 1 << BucketBits;
static constexpr int BUCKET_MASK = BUCKET_SIZE - 1;
ull* keys;
T* values;
ushort* access_time;
ushort time = (ushort) -1;
int num_elements = 0;
int last_index = -1;
ull last_key = -1;
bool last_found = false;
public:
hash_imap()
: keys(new ull[BUCKET_SIZE]), values(new T[BUCKET_SIZE]),
access_time(new ushort[BUCKET_SIZE]) {
}
~hash_imap() {
delete[] keys;
delete[] values;
delete[] access_time;
}
hash_imap(const hash_imap& map)
: keys(new ull[BUCKET_SIZE]), values(new T[BUCKET_SIZE]),
access_time(new ushort[BUCKET_SIZE]) {
memcpy(keys, map.keys, sizeof(ull[BUCKET_SIZE]));
memcpy(values, map.values, sizeof(T[BUCKET_SIZE])); // can be potentially dangerous?
memcpy(access_time, map.access_time, sizeof(ushort[BUCKET_SIZE]));
time = map.time;
num_elements = map.num_elements;
last_index = map.last_index;
last_key = map.last_key;
last_found = map.last_found;
}
hash_imap& operator=(const hash_imap& map) {
if (this == &map)
return *this;
delete[] keys;
delete[] values;
delete[] access_time;
keys = new ull[BUCKET_SIZE];
values = new T[BUCKET_SIZE];
access_time = new ushort[BUCKET_SIZE];
memcpy(keys, map.keys, sizeof(ull[BUCKET_SIZE]));
memcpy(values, map.values, sizeof(T[BUCKET_SIZE])); // can be potentially dangerous?
memcpy(access_time, map.access_time, sizeof(ushort[BUCKET_SIZE]));
time = map.time;
num_elements = map.num_elements;
last_index = map.last_index;
last_key = map.last_key;
last_found = map.last_found;
return *this;
}
void clear() {
num_elements = 0;
last_found = false;
last_index = -1;
if (++time == 0) {
memset(access_time, 0, sizeof(ushort[BUCKET_SIZE]));
time = 1;
}
}
bool access(ull key) {
last_key = key;
last_index = (int) (key & BUCKET_MASK);
bool debug = false;
while (true) {
if (access_time[last_index] != time) {
return last_found = false;
} else if (keys[last_index] == key) {
return last_found = true;
}
last_index = (last_index + 1) & BUCKET_MASK;
}
}
T get() const {
assert(last_found);
return values[last_index];
}
void set(T value) {
assert(last_index != -1);
access_time[last_index] = time;
keys[last_index] = last_key;
values[last_index] = value;
num_elements += !last_found;
assert(("bucket size is too small", num_elements < 0.85 * BUCKET_SIZE));
}
};
// a bitset, but cooler than std::bitset
template <int Size>
class rich_bitset {
private:
using word = ull;
static_assert(has_single_bit(sizeof(word)));
static constexpr int WORD_SHIFT = std::countr_zero(8 * sizeof(word));
static constexpr int WORD_SIZE = 1 << WORD_SHIFT;
static constexpr int WORD_MASK = WORD_SIZE - 1;
static constexpr int NUM_WORDS = (Size + WORD_SIZE - 1) / WORD_SIZE;
static constexpr int LAST_WORD = NUM_WORDS - 1;
static constexpr word LAST_WORD_MASK =
(Size & WORD_MASK) == 0 ? word(-1) : (word(1) << (Size & WORD_MASK)) - 1;
#define REP_WORDS(i) for (int i = 0; i < NUM_WORDS; i++)
#define REP_INNER_WORDS(i) for (int i = 0; i < NUM_WORDS - 1; i++)
#define REP_WORDS_REV(i) for (int i = NUM_WORDS - 1; i >= 0; i--)
#define REP_INNER_WORDS_REV(i) for (int i = NUM_WORDS - 2; i >= 0; i--)
// [LAST_WORD] [LAST_WORD - 1] [...] [1] [0]
// <- higher bits lower bits ->
word data[NUM_WORDS];
struct ref {
rich_bitset<Size>& bs;
const int pos;
ref(rich_bitset<Size>& bs, int pos) : bs(bs), pos(pos) {
}
ref& operator=(bool val) {
bs.set(pos, val);
return *this;
}
operator bool() const {
return bs.test(pos);
}
};
void trim() {
if constexpr ((Size & WORD_MASK) != 0) {
data[LAST_WORD] &= LAST_WORD_MASK;
}
}
public:
rich_bitset(ull value = 0) {
constexpr int BITS = sizeof(ull) * 8;
for (int i = 0; i < (BITS + WORD_SIZE - 1) / WORD_SIZE; i++) {
data[i] = value >> i * WORD_SIZE;
}
constexpr int OFFSET = (BITS + WORD_SIZE - 1) / WORD_SIZE;
if constexpr (OFFSET < NUM_WORDS) {
memset(data + OFFSET, 0, sizeof(word) * (NUM_WORDS - OFFSET));
}
}
bool all() const {
bool res = true;
REP_INNER_WORDS(i) {
res &= data[i] == word(-1);
}
res &= data[LAST_WORD] == LAST_WORD_MASK;
return res;
}
bool none() const {
bool res = true;
REP_WORDS(i) {
res &= data[i] == 0;
}
return res;
}
bool any() const {
bool res = false;
REP_WORDS(i) {
res |= data[i] != 0;
}
return res;
}
int count() const {
int res = 0;
REP_WORDS(i) {
res += popcount(data[i]);
}
return res;
}
int countr_zero() const {
if constexpr (LAST_WORD == 0) {
return std::countr_zero(word(data[LAST_WORD] | ~LAST_WORD_MASK));
} else {
int res = std::countr_zero(data[0]);
int mask = -(res == WORD_SIZE); // continue adding if -1
for (int i = 1; i < NUM_WORDS - 1; i++) {
int count = std::countr_zero(data[i]);
res += count & mask;
mask &= -(count == WORD_SIZE);
}
int count = std::countr_zero(word(data[LAST_WORD] | ~LAST_WORD_MASK));
res += count & mask;
return res;
}
}
int countl_zero() const {
constexpr int LAST_WORD_SIZE = popcount(LAST_WORD_MASK);
int res = std::countl_zero(word(~(~data[LAST_WORD] << (WORD_SIZE - LAST_WORD_SIZE))));
int mask = -(res == LAST_WORD_SIZE); // continue adding if -1
for (int i = NUM_WORDS - 2; i >= 0; i--) {
int count = std::countl_zero(data[i]);
res += count & mask;
mask &= -(count == WORD_SIZE);
}
return res;
}
int countr_one() const {
if constexpr (LAST_WORD == 0) {
return std::countr_one(data[LAST_WORD]);
} else {
int res = std::countr_one(data[0]);
int mask = -(res == WORD_SIZE); // continue adding if -1
for (int i = 1; i < NUM_WORDS - 1; i++) {
int count = std::countr_one(data[i]);
res += count & mask;
mask &= -(count == WORD_SIZE);
}
int count = std::countr_one(data[LAST_WORD]);
res += count & mask;
return res;
}
}
int countl_one() const {
constexpr int LAST_WORD_SIZE = popcount(LAST_WORD_MASK);
int res = std::countl_one(word(data[LAST_WORD] << (WORD_SIZE - LAST_WORD_SIZE)));
int mask = -(res == LAST_WORD_SIZE); // continue adding if -1
for (int i = NUM_WORDS - 2; i >= 0; i--) {
int count = std::countl_one(data[i]);
res += count & mask;
mask &= -(count == WORD_SIZE);
}
return res;
}
int size() const {
return Size;
}
bool test(int pos) const {
assert(pos >= 0 && pos < Size);
return (data[pos >> WORD_SHIFT] >> (pos & WORD_MASK)) & 1;
}
uint to_uint() const {
constexpr int BITS = sizeof(uint) * 8;
for (int i = (BITS + WORD_SIZE - 1) / WORD_SIZE; i < NUM_WORDS; i++) {
assert(("uint overflow", data[i] == 0));
}
if constexpr (WORD_SIZE > BITS) {
assert(("uint overflow", (data[0] >> BITS) == 0));
}
uint res = (uint) data[0];
for (int i = 1; i < (BITS + WORD_SIZE - 1) / WORD_SIZE && i < NUM_WORDS; i++) {
res |= (uint) data[i] << i * WORD_SIZE;
}
return res;
}
ull to_ull() const {
constexpr int BITS = sizeof(ull) * 8;
for (int i = (BITS + WORD_SIZE - 1) / WORD_SIZE; i < NUM_WORDS; i++) {
assert(("ull overflow", data[i] == 0));
}
if constexpr (WORD_SIZE > BITS) {
assert(("ull overflow", (data[0] >> BITS) == 0));
}
ull res = (ull) data[0];
for (int i = 1; i < (BITS + WORD_SIZE - 1) / WORD_SIZE && i < NUM_WORDS; i++) {
res |= (ull) data[i] << i * WORD_SIZE;
}
return res;
}
rich_bitset& set(int pos, bool val = true) {
assert(pos >= 0 && pos < Size);
word bit = word(1) << (pos & WORD_MASK);
if (val) {
data[pos >> WORD_SHIFT] |= bit;
} else {
data[pos >> WORD_SHIFT] &= ~bit;
}
return *this;
}
rich_bitset& reset(int pos) {
assert(pos >= 0 && pos < Size);
return set(pos, false);
}
rich_bitset& flip(int pos) {
assert(pos >= 0 && pos < Size);
word bit = word(1) << (pos & WORD_MASK);
data[pos >> WORD_SHIFT] ^= bit;
return *this;
}
rich_bitset& set() {
clear_with(data, -1);
trim();
return *this;
}
rich_bitset& reset() {
clear_with(data, 0);
return *this;
}
rich_bitset& flip() {
REP_INNER_WORDS(i) {
data[i] ^= word(-1);
}
data[LAST_WORD] ^= LAST_WORD_MASK;
return *this;
}
rich_bitset& operator&=(const rich_bitset& a) {
REP_WORDS(i) {
data[i] &= a.data[i];
}
return *this;
}
rich_bitset& operator|=(const rich_bitset& a) {
REP_WORDS(i) {
data[i] |= a.data[i];
}
return *this;
}
rich_bitset& operator^=(const rich_bitset& a) {
REP_WORDS(i) {
data[i] ^= a.data[i];
}
return *this;
}
rich_bitset& operator<<=(int amount) {
assert(amount >= 0 && amount < Size);
int nw = amount >> WORD_SHIFT;
if (nw > 0) {
REP_WORDS_REV(i) {
data[i] = i - nw < 0 ? 0 : data[i - nw];
}
}
int nb = amount & WORD_MASK;
if (nb) {
for (int i = NUM_WORDS - 1; i > 0; i--) {
data[i] = data[i] << nb | data[i - 1] >> (WORD_SIZE - nb);
}
data[0] <<= nb;
}
trim();
return *this;
}
rich_bitset& operator>>=(int amount) {
assert(amount >= 0 && amount < Size);
int nw = amount >> WORD_SHIFT;
if (nw > 0) {
REP_WORDS(i) {
data[i] = i + nw >= NUM_WORDS ? 0 : data[i + nw];
}
}
int nb = amount & WORD_MASK;
if (nb) {
REP_INNER_WORDS(i) {
data[i] = data[i] >> nb | data[i + 1] << (WORD_SIZE - nb);
}
data[LAST_WORD] >>= nb;
}
return *this;
}
rich_bitset& operator+=(const rich_bitset& a) {
word carry = 0;
REP_WORDS(i) {
word l = data[i];
word r = a.data[i];
word sum = l + r;
data[i] = sum + carry;
carry = (sum < l) | (data[i] < sum);
}
trim();
return *this;
}
rich_bitset& operator-=(const rich_bitset& a) {
word carry = 1;
REP_WORDS(i) {
word l = data[i];
word r = ~a.data[i];
word sum = l + r;
data[i] = sum + carry;
carry = (sum < l) | (data[i] < sum);
}
trim();
return *this;
}
rich_bitset& operator++() {
word carry = 1;
REP_WORDS(i) {
word l = data[i];
data[i] = l + carry;
carry = (data[i] < l);
}
trim();
return *this;
}
rich_bitset operator++(int) {
rich_bitset res = *this;
operator++();
return res;
}
rich_bitset& operator--() {
word carry = 0;
REP_WORDS(i) {
word l = data[i];
data[i] = l - 1 + carry;
carry = (l | carry) != 0;
}
trim();
return *this;
}
rich_bitset operator--(int) {
rich_bitset res = *this;
operator--();
return res;
}
rich_bitset operator~() const {
rich_bitset res = *this;
res.flip();
return res;
}
friend rich_bitset operator&(const rich_bitset& a, const rich_bitset& b) {
rich_bitset res = a;
res &= b;
return res;
}
friend rich_bitset operator|(const rich_bitset& a, const rich_bitset& b) {
rich_bitset res = a;
res |= b;
return res;
}
friend rich_bitset operator^(const rich_bitset& a, const rich_bitset& b) {
rich_bitset res = a;
res ^= b;
return res;
}
friend rich_bitset operator<<(const rich_bitset& a, int amount) {
rich_bitset res = a;
res <<= amount;
return res;
}
friend rich_bitset operator>>(const rich_bitset& a, int amount) {
rich_bitset res = a;
res >>= amount;
return res;
}
friend rich_bitset operator+(const rich_bitset& a, const rich_bitset& b) {
rich_bitset res = a;
res += b;
return res;
}
friend rich_bitset operator-(const rich_bitset& a, const rich_bitset& b) {
rich_bitset res = a;
res -= b;
return res;
}
friend bool operator==(const rich_bitset& a, const rich_bitset& b) {
return memcmp(a.data, b.data, sizeof(a.data)) == 0;
}
friend bool operator!=(const rich_bitset& a, const rich_bitset& b) {
return memcmp(a.data, b.data, sizeof(a.data)) != 0;
}
friend int operator<=>(const rich_bitset& a, const rich_bitset& b) {
REP_WORDS_REV(i) {
if (a.data[i] != b.data[i])
return a.data[i] < b.data[i] ? -1 : 1;
}
return 0;
}
ref operator[](int pos) {
return {*this, pos};
}
bool operator[](int pos) const {
return test(pos);
}
string str() const {
ostringstream oss;
oss << *this;
return oss.str();
}
friend ostream& operator<<(ostream& out, const rich_bitset& bs) {
for (int i = Size - 1; i >= 0; i--) {
out << (bs.test(i) ? '1' : '0');
}
return out;
}
#undef REP_WORDS
#undef REP_INNER_WORDS
#undef REP_WORDS_REV
#undef REP_INNER_WORDS_REV
};
template <class T>
class easy_stack {
private:
vector<T> data;
public:
auto begin() {
return data.begin();
}
auto end() {
return data.end();
}
auto begin() const {
return data.begin();
}
auto end() const {
return data.end();
}
void push_back(T a) {
data.push_back(a);
}
template <class... Args>
void emplace(Args&&... args) {
data.emplace_back(forward<Args>(args)...);
}
T pop_back() {
T res = data.back();
data.pop_back();
return res;
}
int size() const {
return (int) data.size();
}
bool empty() const {
return data.empty();
}
};
template <int N>
int len(const fast_iset<N>& a) {
return a.size();
}
template <class T, int N>
int len(const fast_vector<T, N>& a) {
return a.size();
}
template <class T, int BucketBits>
int len(const hash_imap<T, BucketBits>& a) {
return a.size();
}
template <class T>
int len(const easy_stack<T>& a) {
return a.size();
}
} // namespace ds
using namespace ds;
namespace beam_search {
// (state) -> score
template <class T, class State, class Score>
concept get_score =
totally_ordered<Score> && invocable<T, State&> && same_as<invoke_result_t<T, State&>, Score>;
// (state, move) -> void
template <class T, class State, class MoveId>
concept apply_move =
invocable<T, State&, MoveId> && same_as<invoke_result_t<T, State&, MoveId>, void>;
// (state) -> void
template <class T, class State>
concept undo_move = invocable<T, State&> && same_as<invoke_result_t<T, State&>, void>;
// (state) -> void
// see also: add_candidate
template <class T, class State>
concept enumerate_candidates = invocable<T, State&> && same_as<invoke_result_t<T, State&>, void>;
// (turn) -> void
// see also: candidates_to_filter
template <class T>
concept filter_candidates = invocable<T, int> && same_as<invoke_result_t<T, int>, void>;
template <class State, totally_ordered Score, class MoveId, MoveId UnusedMoveId, class CandidateData,
class Direction = greater<Score>, int HashBucketBits = 20>
class beam_search {
private:
struct candidate {
int index; // index in orig_candidates
int parent;
MoveId move_id;
CandidateData data;
ull hash;
};
struct orig_candidate {
int parent;
MoveId move_id;
bool chosen;
};
Direction dir = {};
int current_parent = 0;
hash_imap<int, HashBucketBits> best_indices;
bool enumerating = false;
bool filtering = false;
vector<candidate> candidates;
vector<orig_candidate> orig_candidates;
void clear_candidates() {
candidates.clear();
orig_candidates.clear();
}
public:
Score best_score = 0;
int max_turn = -1;
beam_search() {
}
beam_search(Direction dir) : dir(dir) {
}
void add_candidate(MoveId move_id, CandidateData data, ull hash) {
assert(("not enumerating now", enumerating));
candidates.emplace_back((int) candidates.size(), current_parent, move_id, data, hash);
orig_candidates.emplace_back(current_parent, move_id);
}
vector<candidate>& candidates_to_filter() {
assert(("not filtering now", filtering));
return candidates;
}
// CAUTION: not stable
template <predicate<candidate&, candidate&> CandidateDirection>
void remove_duplicates(CandidateDirection candidate_direction) {
assert(("not filtering now", filtering));
best_indices.clear();
int n = (int) candidates.size();
for (int i = 0; i < n; i++) {
candidate& cand = candidates[i];
if (best_indices.access(cand.hash)) {
int j = best_indices.get();
candidate& cand2 = candidates[j];
if (candidate_direction(cand, cand2)) {
swap(candidates[i], candidates[j]);
}
swap(candidates[i], candidates[--n]);
i--;
} else {
best_indices.set(i);
}
}
candidates.resize(n);
}
template <get_score<State, Score> GetScore, apply_move<State, MoveId> ApplyMove,
enumerate_candidates<State> EnumerateCandidates, filter_candidates FilterCandidates>
vector<MoveId> run(const State& initial_state, GetScore get_score, ApplyMove apply_move,
EnumerateCandidates enumerate_candidates, FilterCandidates filter_candidates) {
struct node {
State state;
int history_index;
};
struct history {
MoveId move_id;
int parent;
};
vector<node> src;
vector<node> dst;
increasing_vector<history> hs;
int turn = 0;
// set initial state
src.emplace_back(initial_state, -1);
while (true) {
int num_states = (int) src.size();
clear_candidates();
if (max_turn == -1 || turn < max_turn) {
// enumerate candidates
enumerating = true;
for (int i = 0; i < num_states; i++) {
current_parent = i;
enumerate_candidates(src[i].state);
}
enumerating = false;
// filer candiadtes
filtering = true;
filter_candidates(turn);
filtering = false;
}
// check if finished
if (candidates.empty()) {
assert(("no states at the end", num_states > 0));
// pick the best state
best_score = get_score(src[0].state);
int best_index = 0;
for (int i = 1; i < num_states; i++) {
Score score = get_score(src[i].state);
if (dir(score, best_score)) {
best_score = score;
best_index = i;
}
}
// restore moves
vector<MoveId> res;
int history_top = src[best_index].history_index;
while (history_top != -1) {
history& h = hs[history_top];
res.push_back(h.move_id);
history_top = h.parent;
}
reverse(res.begin(), res.end());
return res;
}
// compute next states
dst.clear();
for (const auto& cand : candidates) {
const auto& src_node = src[cand.parent];
dst.emplace_back(src_node.state, hs.size());
apply_move(dst.back().state, cand.move_id);
hs.emplace_back(cand.move_id, src_node.history_index);
}
src.swap(dst);
turn++;
}
}
template <get_score<State, Score> GetScore, apply_move<State, MoveId> ApplyMove,
undo_move<State> UndoMove, enumerate_candidates<State> EnumerateCandidates,
filter_candidates FilterCandidates>
vector<MoveId> run_tree(const State& initial_state, GetScore get_score, ApplyMove apply_move,
UndoMove undo_move, EnumerateCandidates enumerate_candidates,
FilterCandidates filter_candidates) {
constexpr MoveId UNDO = UnusedMoveId;
struct tour {
vector<MoveId> src;
vector<MoveId> dst;
void move(const MoveId& move_id) {
dst.push_back(move_id);
}
int position() {
return (int) dst.size();
}
void swap() {
src.swap(dst);
dst.clear();
}
} tour;
vector<MoveId> global_path;
vector<MoveId> path;
vector<orig_candidate> leaves;
State st = initial_state;
int turn = 0;
int level = 0;
int next_start_pos = 0;
auto global_move = [&](const MoveId& move_id) {
apply_move(st, move_id);
global_path.push_back(move_id);
level++;
};
auto global_undo = [&]() {
undo_move(st);
global_path.pop_back();
level--;
};
while (true) {
bool has_next_turn = max_turn == -1 || turn < max_turn;
// compute the next tour
int pos = next_start_pos;
int prev_root_level = level;
int next_root_level = numeric_limits<int>::max();
orig_candidate best_leaf = {-1, MoveId{}, false};
enumerating = true;
clear_candidates();
if (turn == 0) {
best_score = get_score(st);
best_leaf.chosen = true;
if (has_next_turn) {
current_parent = tour.position();
enumerate_candidates(st);
}
} else {
for (const orig_candidate& leaf : leaves) {
int parent_pos = leaf.parent;
// visit the parent of the leaf node
if (pos < parent_pos) {
// visit the LCA
path.clear();
do {
auto move = tour.src[pos++];
if (move == UNDO) {
if (path.empty()) {
global_undo();
tour.move(UNDO);
next_root_level = min(next_root_level, level);
} else {
path.pop_back();
}
} else {
path.push_back(move);
}
} while (pos < parent_pos);
// go directly to the parent
for (auto move : path) {
global_move(move);
tour.move(move);
}
} // now we are at the parent of the leaf node
// visit the leaf node
apply_move(st, leaf.move_id);
tour.move(leaf.move_id);
Score score = get_score(st);
if (!best_leaf.chosen || dir(score, best_score)) {
best_score = score;
best_leaf = leaf;
}
if (has_next_turn) {
current_parent = tour.position();
enumerate_candidates(st);
}
// leave the leaf node
undo_move(st);
tour.move(UNDO);
}
}
next_root_level = min(next_root_level, level);
enumerating = false;
filtering = true;
filter_candidates(turn);
filtering = false;
if (candidates.empty()) {
assert(best_leaf.chosen);
// undo to the root level
while (level > prev_root_level) {
global_undo();
}
// visit the best leaf
pos = next_start_pos;
while (pos < best_leaf.parent) {
auto move = tour.src[pos++];
if (move == UNDO) {
global_undo();
} else {
global_move(move);
}
}
if (best_leaf.parent != -1) {
global_move(best_leaf.move_id);
}
return global_path;
}
// finalize the next tour
tour.swap();
turn++;
// collect the next leaf nodes, in the original order
leaves.clear();
for (const candidate& cand : candidates) {
orig_candidates[cand.index].chosen = true;
}
for (const orig_candidate& cand : orig_candidates) {
if (!cand.chosen)
continue;
leaves.push_back(cand);
}
// undo to the next root level
while (level > next_root_level) {
global_undo();
}
// adjust the next starting position
next_start_pos = next_root_level - prev_root_level;
}
}
};
class beam_width_manager {
private:
double prev_time = 0;
double moving_average_time = 0;
vector<double> progress_history;
vector<double> time_history;
vector<int> width_history;
int last_width = 0;
int count = 0;
public:
int window_size = 50;
int default_width;
beam_width_manager(int default_width) : default_width(default_width) {
}
int next(double progress, double time, double time_limit) {
progress_history.push_back(progress);
time_history.push_back(time);
width_history.push_back(last_width);
count++;
if (count <= window_size) {
return last_width = default_width;
}
int i1 = count - 1 - window_size;
int i2 = count - 1;
double progress_sum = progress_history[i2] - progress_history[i1];
double time_sum = time_history[i2] - time_history[i1];
if (progress_sum == 0 || time_sum == 0) {
// window size is too small
window_size *= 2;
return last_width = default_width;
}
int width_sum = 0;
for (int i = i1 + 1; i <= i2; i++) {
width_sum += width_history[i];
}
double progress_per_turn = progress_sum / window_size;
double time_per_width = time_sum / width_sum;
double left_time = time_limit - time;
double left_progress = 1 - progress;
if (left_time <= 0 || left_progress <= 0)
return 1;
double left_turn = left_progress / progress_per_turn;
double left_time_per_turn = left_time / left_turn;
double left_width_per_turn = left_time_per_turn / time_per_width;
return last_width = round(left_width_per_turn);
}
void report(int actual_last_width) {
last_width = actual_last_width;
}
};
} // namespace beam_search
namespace simulated_annealing {
// (state) -> score
template <class T, class State, class Score>
concept get_score =
totally_ordered<Score> && invocable<T, State&> && same_as<invoke_result_t<T, State&>, Score>;
// (iter) -> progress
template <class T>
concept update_progress = invocable<T, int> && same_as<invoke_result_t<T, int>, double>;
// (state, tolerance) -> accepted
template <class T, class State>
concept try_transition =
invocable<T, State&, double> && same_as<invoke_result_t<T, State&, double>, bool>;
template <class State, totally_ordered Score, class Direction = greater<Score>>
class simulated_annealing {
private:
Direction dir = {};
public:
int clock_interval = 10;
double t_from = 100;
double t_to = 0.01;
double progress = 0;
int num_iterations = 0;
int num_acceptances = 0;
int num_rejections = 0;
bool use_linear_temp = false;
Score best_score = 0;
simulated_annealing() {
}
simulated_annealing(Direction dir) : dir(dir) {
}
template <get_score<State, Score> GetScore, update_progress UpdateProgress,
try_transition<State> TryTransition>
State run(const State& initial_state, rngen& rng, GetScore get_score,
UpdateProgress update_progress, TryTransition try_transition,
function<void(State&, Score, int, double)> best_updated = nullptr) {
State state = initial_state;
Score score = get_score(state);
State best_state = state;
best_score = score;
num_iterations = 0;
num_acceptances = 0;
num_rejections = 0;
int interval = clock_interval;
progress = 0;
double t = t_from;
while (true) {
if (--interval <= 0) {
progress = update_progress(num_iterations);
if (progress >= 1)
break;
t = use_linear_temp ? lerp(t_from, t_to, progress)
: exp_interp(t_from, t_to, progress);
interval = clock_interval;
}
double tolerance = t * -log(rng.next_float());
if (try_transition(state, tolerance)) {
num_acceptances++;
score = get_score(state);
if (dir(score, best_score)) {
best_state = state;
best_score = score;
if (best_updated) {
best_updated(state, score, num_iterations, t);
}
}
} else {
num_rejections++;
}
num_iterations++;
}
return best_state;
}
};
} // namespace simulated_annealing
namespace dijkstra {
// (vertex) -> index
template <class T, class Vertex>
concept get_index = invocable<T, Vertex> && same_as<invoke_result_t<T, Vertex>, int>;
// (vertex) -> is_goal
template <class T, class Vertex>
concept is_goal = invocable<T, Vertex> && same_as<invoke_result_t<T, Vertex>, bool>;
// (vertex, distance) -> void
template <class T, class Vertex, class Weight>
concept visit_adjacent_vertices =
invocable<T, Vertex, Weight> && same_as<invoke_result_t<T, Vertex, Weight>, void>;
template <class Vertex, class Weight, Weight Infinity, int MaxVertexIndex>
requires(integral<Weight> || floating_point<Weight>)
class dijkstra {
private:
using vw = pair<Vertex, Weight>;
static constexpr int VERTEX_ARRAY_SIZE = MaxVertexIndex + 1;
vector<vw> toVisit;
bool visiting = false;
public:
array<bool, VERTEX_ARRAY_SIZE> visited;
array<Weight, VERTEX_ARRAY_SIZE> distance;
array<optional<Vertex>, VERTEX_ARRAY_SIZE> previous;
dijkstra() {
}
template <get_index<Vertex> GetIndex, is_goal<Vertex> IsGoal,
visit_adjacent_vertices<Vertex, Weight> VisitAdjacentVertices>
void run(const vector<Vertex>& starts, GetIndex get_index, IsGoal is_goal,
VisitAdjacentVertices visit_adjacent_vertices) {
auto comp = [](vw& a, vw& b) {
return a.second > b.second;
};
visited.fill(false);
previous.fill(nullopt);
distance.fill(Infinity);
priority_queue<vw, vector<vw>, decltype(comp)> q(comp);
for (auto& st : starts) {
distance[get_index(st)] = Weight(0);
q.emplace(st, Weight(0));
}
int loop = 0;
while (!q.empty()) {
if (++loop % 10 == 0)
trace(loop, " ", timer::timer());
auto [from, dist] = q.top();
q.pop();
int fromi = get_index(from);
if (visited[fromi])
continue;
visited[fromi] = true;
if (is_goal(from)) {
return;
}
visiting = true;
toVisit.clear();
visit_adjacent_vertices(from, dist);
visiting = false;
for (vw& pair : toVisit) {
Vertex to = pair.first;
int toi = get_index(to);
Weight new_dist = pair.second;
if (new_dist < distance[toi]) {
distance[toi] = new_dist;
previous[toi] = from;
q.emplace(to, new_dist);
}
}
}
}
void visit(Vertex vertex, Weight total_distance) {
assert(("not visiting now", visiting));
toVisit.emplace_back(vertex, total_distance);
}
template <get_index<Vertex> GetIndex>
vector<Vertex> restore_path(Vertex goal, GetIndex get_index) {
assert(("goal not reached", visited[get_index(goal)]));
vector<Vertex> res;
Vertex v = goal;
while (true) {
res.push_back(v);
if (!previous[get_index(v)])
break;
v = previous[get_index(v)].value();
}
reverse(res.begin(), res.end());
return res;
}
};
}; // namespace dijkstra
namespace file {
string pad4(int n) {
return (n < 0 || n >= 1000 ? "" : n < 10 ? "000" : n < 100 ? "00" : "0") + tos(n);
}
string input_file_name(int seed) {
return "in/" + pad4(seed) + ".txt";
}
string output_file_name(int seed) {
return "out/" + pad4(seed) + ".txt";
}
string movie_file_name(int seed) {
return "mov/" + pad4(seed) + ".smv";
}
bool write_text(string fileName, string text, bool append = false) {
ofstream fout;
fout.open(fileName, append ? ios::out | ios::app : ios::out);
if (!fout)
return false;
fout << text;
fout.close();
return true;
}
pair<string, bool> read_text(string fileName) {
ifstream fin;
fin.open(fileName, ios::in);
if (!fin)
return make_pair("", false);
string res;
string line;
while (getline(fin, line)) {
res += line;
res += "\n";
}
return make_pair(res, true);
}
void write_text_assert(string fileName, string text, bool append = false) {
auto res = write_text(fileName, text, append);
assert(res);
}
string read_text_assert(string fileName) {
auto res = read_text(fileName);
assert(res.second);
return res.first;
}
} // namespace file
} // namespace shr
using namespace shr::basic;
using namespace shr::ds;
using namespace shr::beam_search;
using namespace shr::simulated_annealing;
using namespace shr::dijkstra;
using namespace shr::random;
using namespace shr::timer;
using namespace shr::tracer;
using namespace shr::file;
//
// --- macros ---
//
#define rep(i, from, until) for (int i = (from); i < (until); i++)
#define repr(i, from, until) for (int i = (until) -1; i >= (from); i--)
#define rep0(i, until) rep(i, 0, until)
#define rep0r(i, until) repr(i, 0, until)
//
// --- movie lib ---
//
class movie {
private:
bool is_open = false;
string file_name;
ofstream out;
#ifdef ONLINE_JUDGE
void write_instruction(const string& it, const vector<double>& argf, const vector<string>& args) {
}
#else
void write_instruction(const string& it, const vector<double>& argf, const vector<string>& args) {
assert(("file name is not set", file_name != ""));
if (!is_open) {
is_open = true;
out = ofstream(file_name, ios_base::out | ios_base::binary);
out.write("smv", 3);
}
write_string(it);
for (double f : argf) {
write_float(f);
}
for (auto& s : args) {
write_string(s);
}
if (it == "n") {
out.flush(); // flush at the end of each frame
}
}
void write_float(double a) {
float f = (float) a;
out.write((char*) &f, 4);
}
void write_string(const string& str) {
out.write(str.c_str(), str.length() + 1);
}
#endif
public:
static constexpr int LEFT = 0;
static constexpr int CENTER = 1;
static constexpr int RIGHT = 2;
movie() {
}
void set_file(string file) {
assert(!is_open);
file_name = file;
}
void close_file() {
if (!is_open)
return;
is_open = false;
out.close();
}
void fill(double rgb, double a = 1.0) {
fill(rgb, rgb, rgb, a);
}
void fill(double r, double g, double b, double a = 1.0) {
write_instruction("f", {r, g, b, a}, {});
}
void stroke(double rgb, double a = 1.0) {
stroke(rgb, rgb, rgb, a);
}
void stroke(double r, double g, double b, double a = 1.0) {
write_instruction("s", {r, g, b, a}, {});
}
void no_fill() {
write_instruction("nf", {}, {});
}
void no_stroke() {
write_instruction("ns", {}, {});
}
void comment(string text) {
write_instruction("cm", {}, {text});
}
void tooltip(string text) {
write_instruction("tt", {}, {text});
}
void no_tooltip() {
write_instruction("nt", {}, {});
}
void stroke_weight(double weight) {
write_instruction("sw", {weight}, {});
}
void text_size(double size) {
write_instruction("ts", {size}, {});
}
void text_align(int align) {
write_instruction("ta", {(double) align}, {});
}
void rect(double x, double y, double w, double h) {
write_instruction("r", {x, y, w, h}, {});
}
void circle(double x, double y, double r) {
write_instruction("c", {x, y, r}, {});
}
void ellipse(double x, double y, double rx, double ry) {
write_instruction("e", {x, y, rx, ry}, {});
}
void line(double x1, double y1, double x2, double y2) {
write_instruction("l", {x1, y1, x2, y2}, {});
}
void text(string str, double x, double y) {
write_instruction("t", {x, y}, {str});
}
void transform(double e00, double e01, double e10, double e11) {
write_instruction("tf", {e00, e01, e10, e11}, {});
}
void translate(double tx, double ty) {
write_instruction("tr", {tx, ty}, {});
}
void rotate(double ang) {
write_instruction("ro", {ang}, {});
}
void scale(double s) {
scale(s, s);
}
void scale(double sx, double sy) {
write_instruction("sc", {sx, sy}, {});
}
void push() {
write_instruction("pu", {}, {});
}
void pop() {
write_instruction("po", {}, {});
}
void end_frame() {
write_instruction("n", {}, {});
}
void target(string name) {
write_instruction("tg", {}, {name});
}
};
movie mov;
// --------------------------------------------------
// main part
// --------------------------------------------------
bool isLocal = false;
bool render = false;
// define N and stuff here
constexpr int N = 45;
constexpr int N2 = N * 2;
constexpr int M = 50;
#define repn(i) rep0(i, N)
#define repm(i) rep0(i, M)
class Problem {
private:
public:
array<array<ll, 2>, N> vs;
void load(istream& in) {
// read input here
int n;
in >> n;
assert(n == N);
repn(i) {
in >> vs[i][0] >> vs[i][1];
}
}
};
struct SolverResult {
ll score = 0;
};
class Solver {
public:
int seed;
rngen rng;
SolverResult result;
Problem p;
Solver() : rng() {
}
void load(istream& in, int seed = -1) {
p.load(in);
mov.set_file(movie_file_name(seed));
init();
}
void load(int seed) {
this->seed = seed;
istringstream in(read_text_assert(input_file_name(seed)));
isLocal = true;
load(in, seed);
}
void solve() {
if (isLocal) {
ostringstream out;
solveMain(out);
mov.close_file();
write_text(output_file_name(seed), out.str());
} else {
solveMain(cout);
}
}
private:
void init() {
}
void solveMain(ostream& out) { // write answer to out
constexpr ll TARGET = (ll) (5e17);
array<ll, N2> cs;
repn(i) {
cs[i << 1] = p.vs[i][0];
cs[i << 1 | 1] = p.vs[i][1];
}
auto op = [&](int i, int j) {
return make_pair(cs[i << 1] + cs[j << 1] >> 1, cs[i << 1 | 1] + cs[j << 1 | 1] >> 1);
};
auto getScore = [&](ll a, ll b) {
return 20000000 - 100000 * log10(max(abs(a - TARGET), abs(b - TARGET)) + 1);
};
// vector<pii> ops;
// repm(iter) {
// double score = getScore(cs[0], cs[1]);
// double bestScore = score;
// int bestI = -1;
// rep(i, 1, N) {
// auto [a, b] = op(0, i);
// double score = getScore(a, b);
// if (update_max(score, bestScore)) {
// bestI = i;
// }
// }
// if (bestI == -1)
// break;
// auto [a, b] = op(0, bestI);
// cs[0] = a;
// cs[1] = b;
// cs[bestI << 1 | 0] = a;
// cs[bestI << 1 | 1] = b;
// trace(bestI, " ", log10(max(abs(a - TARGET), abs(b - TARGET))), " ", bestScore, " ", iter);
// }
// out << len(ops) << endl;
// for (auto [a, b] : ops) {
// out << a + 1 << " " << b + 1 << endl;
// }
struct State {
ll cs[N2];
ll hist[M * 4];
int ihist[M * 2];
int turn = 0;
};
auto diff = [&](ll cs[N2], int i) {
return max(abs(cs[i << 1] - TARGET), abs(cs[i << 1 | 1] - TARGET));
};
auto apply = [&](State& st, short move) {
int i = move >> 8 & 0xff;
int j = move & 0xff;
ll ai = st.cs[i << 1];
ll bi = st.cs[i << 1 | 1];
ll aj = st.cs[j << 1];
ll bj = st.cs[j << 1 | 1];
ll a = ai + aj >> 1;
ll b = bi + bj >> 1;
st.hist[st.turn << 2 | 0] = ai;
st.hist[st.turn << 2 | 1] = bi;
st.hist[st.turn << 2 | 2] = aj;
st.hist[st.turn << 2 | 3] = bj;
st.ihist[st.turn << 1 | 0] = i;
st.ihist[st.turn << 1 | 1] = j;
st.cs[i << 1] = a;
st.cs[i << 1 | 1] = b;
st.cs[j << 1] = a;
st.cs[j << 1 | 1] = b;
st.turn++;
};
auto undo = [&](State& st) {
st.turn--;
int i = st.ihist[st.turn << 1 | 0];
int j = st.ihist[st.turn << 1 | 1];
ll ai = st.hist[st.turn << 2 | 0];
ll bi = st.hist[st.turn << 2 | 1];
ll aj = st.hist[st.turn << 2 | 2];
ll bj = st.hist[st.turn << 2 | 3];
ll a = st.cs[i << 1];
ll b = st.cs[i << 1 | 1];
st.cs[i << 1] = ai;
st.cs[i << 1 | 1] = bi;
st.cs[j << 1] = aj;
st.cs[j << 1 | 1] = bj;
};
beam_search<State, ll, short, -1, ll, less<ll>, 24> bs;
bs.max_turn = M;
State st;
repn(i) {
st.cs[i << 1] = cs[i << 1];
st.cs[i << 1 | 1] = cs[i << 1 | 1];
}
auto res = bs.run_tree(
st,
[&](State& st) {
return max(abs(st.cs[0] - TARGET), abs(st.cs[1] - TARGET));
},
apply, undo,
[&](State& st) {
auto getScore = [&]() {
ll res = diff(st.cs, 0);
res += diff(st.cs, 1) >> 1;
res += diff(st.cs, 2) >> 2;
res += diff(st.cs, 3) >> 3;
res += diff(st.cs, 4) >> 4;
res += diff(st.cs, 5) >> 5;
return res;
};
ll cscore = getScore();
bs.add_candidate(0, cscore, 0);
rep0(i, N - 1) {
rep(j, i + 1, N) {
apply(st, i << 8 | j);
ll score = getScore();
undo(st);
bs.add_candidate(i << 8 | j, score, 0);
}
}
},
[&](int turn) {
auto& cands = bs.candidates_to_filter();
int bw = 300;
auto better = [&](auto& a, auto& b) {
return a.data < b.data;
};
trace(turn, " ", len(cands));
static hash_imap<int> counts;
counts.clear();
if (len(cands) > bw) {
ranges::sort(cands, better);
erase_if(cands, [&](auto& a) {
if (counts.access(a.parent)) {
int num = counts.get();
if (num > 10)
return true;
counts.set(num + 1);
} else {
counts.set(1);
}
return false;
});
if (len(cands) > bw) {
nth_element(cands.begin(), cands.begin() + bw, cands.end(), better);
cands.resize(bw);
}
}
});
erase_if(res, [&](auto move) {
return move == 0;
});
trace(round(2e6 - 1e5 * log10(bs.best_score)) * 50);
out << len(res) << endl;
for (short move : res) {
out << (move >> 8 & 0xff) << " " << (move & 0xff) << endl;
// trace(move >> 8 & 0xff, " ", move & 0xff);
}
}
};
int main() {
#if 0 || ONLINE_JUDGE
isLocal = false;
render = false;
timer(true);
Solver sol;
sol.load(cin);
sol.solve();
#elif 0
compareScores("cut", "nocut");
// compareScores("new6", "new10");
#elif 0
// for local and remote testers
debug = false;
render = false;
int seed;
cin >> seed;
cin >> time_scale;
timer(true);
Solver sol;
sol.load(seed);
cout << sol.result.score << endl;
#elif 1
// single-threaded test, handy but slow
time_scale = 1.0;
int num = 50;
int from = 0;
int stride = 1;
int single = 0;
debug = true;
render = false;
struct TestCase {
int seed;
int time;
ll score;
};
vector<TestCase> cases;
vector<int> seedList = {};
if (seedList.empty()) {
if (single == -1) {
rep0(t, num) {
seedList.push_back(from + t * stride);
}
} else {
seedList.push_back(single);
}
}
bool doTrace = debug;
debug = true;
for (int seed : seedList) {
timer(true);
trace("------------ SOLVING SEED ", seed, " ------------");
debug = doTrace;
Solver s;
s.load(seed);
s.solve();
debug = true;
int time = timer();
trace("score: ", s.result.score, " (time ", time, " ms)\n");
if (s.result.score != -1)
cases.emplace_back(seed, time, s.result.score);
}
auto print = [&](const TestCase& c) {
int seed = c.seed;
string space = seed < 10 ? " " : seed < 100 ? " " : seed < 1000 ? " " : "";
trace(" seed ", space, seed, ": ", c.score, " (time ", c.time, " ms)");
};
if (len(cases) > 1) {
trace("------------ summary ------------");
trace("sort by seed:");
sort(cases.begin(), cases.end(), [&](auto a, auto b) {
return a.seed < b.seed;
});
for (auto& c : cases)
print(c);
trace("sort by score:");
sort(cases.begin(), cases.end(), [&](auto a, auto b) {
return a.score > b.score;
});
for (auto& c : cases)
print(c);
ll scoreSum = 0;
double logScoreSum = 0;
for (auto& c : cases) {
scoreSum += c.score;
logScoreSum += log(c.score);
}
double invDenom = 1.0 / len(cases);
trace("total score: ", scoreSum, ", mean: ", (ll) (scoreSum * invDenom * 100 + 0.5) / 100.0,
", mean(log2): ", (ll) (logScoreSum * invDenom * 1000 + 0.5) / 1000.0);
}
#endif
}