提出 #75031139
ソースコード 拡げる
// #undef YOSUPO_LOCAL
#if 0 and !defined(__clang__)
#include <vector>
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#pragma GCC optimize("Ofast")
#endif
#include <stdio.h>
#include <unistd.h>
#include <algorithm>
#include <array>
#include <bit>
#include <cassert>
#include <cctype>
#include <cstdint>
#include <cstdio>
#include <cstring>
#include <sstream>
#include <string>
#include <type_traits>
#include <vector>
namespace yosupo {
namespace internal {
template <class T>
using is_signed_int128 =
typename std::conditional<std::is_same<T, __int128_t>::value ||
std::is_same<T, __int128>::value,
std::true_type,
std::false_type>::type;
template <class T>
using is_unsigned_int128 =
typename std::conditional<std::is_same<T, __uint128_t>::value ||
std::is_same<T, unsigned __int128>::value,
std::true_type,
std::false_type>::type;
template <class T>
using make_unsigned_int128 =
typename std::conditional<std::is_same<T, __int128_t>::value,
__uint128_t,
unsigned __int128>;
template <class T>
using is_integral =
typename std::conditional<std::is_integral<T>::value ||
internal::is_signed_int128<T>::value ||
internal::is_unsigned_int128<T>::value,
std::true_type,
std::false_type>::type;
template <class T>
using is_signed_int = typename std::conditional<(is_integral<T>::value &&
std::is_signed<T>::value) ||
is_signed_int128<T>::value,
std::true_type,
std::false_type>::type;
template <class T>
using is_unsigned_int =
typename std::conditional<(is_integral<T>::value &&
std::is_unsigned<T>::value) ||
is_unsigned_int128<T>::value,
std::true_type,
std::false_type>::type;
template <class T>
using to_unsigned = typename std::conditional<
is_signed_int128<T>::value,
make_unsigned_int128<T>,
typename std::conditional<std::is_signed<T>::value,
std::make_unsigned<T>,
std::common_type<T>>::type>::type;
template <class T>
using is_integral_t = std::enable_if_t<is_integral<T>::value>;
template <class T>
using is_signed_int_t = std::enable_if_t<is_signed_int<T>::value>;
template <class T>
using is_unsigned_int_t = std::enable_if_t<is_unsigned_int<T>::value>;
template <class T> using to_unsigned_t = typename to_unsigned<T>::type;
} // namespace internal
} // namespace yosupo
namespace yosupo {
struct Scanner {
public:
Scanner(const Scanner&) = delete;
Scanner& operator=(const Scanner&) = delete;
Scanner(FILE* fp) : fd(fileno(fp)) { line[0] = 127; }
void read() {}
template <class H, class... T> void read(H& h, T&... t) {
bool f = read_single(h);
assert(f);
read(t...);
}
int read_unsafe() { return 0; }
template <class H, class... T> int read_unsafe(H& h, T&... t) {
bool f = read_single(h);
if (!f) return 0;
return 1 + read_unsafe(t...);
}
int close() { return ::close(fd); }
private:
static constexpr int SIZE = 1 << 15;
int fd = -1;
std::array<char, SIZE + 1> line;
int st = 0, ed = 0;
bool eof = false;
bool read_single(std::string& ref) {
if (!skip_space()) return false;
ref = "";
while (true) {
char c = top();
if (c <= ' ') break;
ref += c;
st++;
}
return true;
}
bool read_single(double& ref) {
std::string s;
if (!read_single(s)) return false;
ref = std::stod(s);
return true;
}
template <class T> bool read_single(std::vector<T>& ref) {
for (auto& e : ref) {
if (!read_single(e)) return false;
}
return true;
}
template <class T,
std::enable_if_t<std::is_same<T, char>::value>* = nullptr>
bool read_single(T& ref) {
if (!skip_space<50>()) return false;
ref = top();
st++;
return true;
}
template <class T,
internal::is_signed_int_t<T>* = nullptr,
std::enable_if_t<!std::is_same<T, char>::value>* = nullptr>
bool read_single(T& sref) {
using U = internal::to_unsigned_t<T>;
if (!skip_space<50>()) return false;
bool neg = false;
if (line[st] == '-') {
neg = true;
st++;
}
U ref = 0;
do {
ref = 10 * ref + (line[st++] & 0x0f);
} while (line[st] >= '0');
sref = neg ? -ref : ref;
return true;
}
template <class U,
internal::is_unsigned_int_t<U>* = nullptr,
std::enable_if_t<!std::is_same<U, char>::value>* = nullptr>
bool read_single(U& ref) {
if (!skip_space<50>()) return false;
ref = 0;
do {
ref = 10 * ref + (line[st++] & 0x0f);
} while (line[st] >= '0');
return true;
}
bool reread() {
if (ed - st >= 50) return true;
if (st > SIZE / 2) {
std::memmove(line.data(), line.data() + st, ed - st);
ed -= st;
st = 0;
}
if (eof) return false;
auto u = ::read(fd, line.data() + ed, SIZE - ed);
if (u == 0) {
eof = true;
line[ed] = '\0';
u = 1;
}
ed += int(u);
line[ed] = char(127);
return true;
}
char top() {
if (st == ed) {
bool f = reread();
assert(f);
}
return line[st];
}
template <int TOKEN_LEN = 0> bool skip_space() {
while (true) {
while (line[st] <= ' ') st++;
if (ed - st > TOKEN_LEN) return true;
if (st > ed) st = ed;
for (auto i = st; i < ed; i++) {
if (line[i] <= ' ') return true;
}
if (!reread()) return false;
}
}
};
struct Printer {
public:
template <char sep = ' ', bool F = false> void write() {}
template <char sep = ' ', bool F = false, class H, class... T>
void write(const H& h, const T&... t) {
if (F) write_single(sep);
write_single(h);
write<true>(t...);
}
template <char sep = ' ', class... T> void writeln(const T&... t) {
write<sep>(t...);
write_single('\n');
}
Printer(FILE* _fp) : fd(fileno(_fp)) {}
~Printer() { flush(); }
int close() {
flush();
return ::close(fd);
}
void flush() {
if (pos) {
auto res = ::write(fd, line.data(), pos);
assert(res != -1);
pos = 0;
}
}
private:
static std::array<std::array<char, 2>, 100> small;
static std::array<unsigned long long, 20> tens;
static constexpr size_t SIZE = 1 << 15;
int fd;
std::array<char, SIZE> line;
size_t pos = 0;
std::stringstream ss;
template <class T,
std::enable_if_t<std::is_same<char, T>::value>* = nullptr>
void write_single(const T& val) {
if (pos == SIZE) flush();
line[pos++] = val;
}
template <class T,
internal::is_signed_int_t<T>* = nullptr,
std::enable_if_t<!std::is_same<char, T>::value>* = nullptr>
void write_single(const T& val) {
using U = internal::to_unsigned_t<T>;
if (val == 0) {
write_single('0');
return;
}
if (pos > SIZE - 50) flush();
U uval = val;
if (val < 0) {
write_single('-');
uval = -uval;
}
write_unsigned(uval);
}
template <class U,
internal::is_unsigned_int_t<U>* = nullptr,
std::enable_if_t<!std::is_same<char, U>::value>* = nullptr>
void write_single(U uval) {
if (uval == 0) {
write_single('0');
return;
}
if (pos > SIZE - 50) flush();
write_unsigned(uval);
}
static int calc_len(uint64_t x) {
int i = ((63 - std::countl_zero(x)) * 3 + 3) / 10;
if (x < tens[i])
return i;
else
return i + 1;
}
template <class U,
internal::is_unsigned_int_t<U>* = nullptr,
std::enable_if_t<2 >= sizeof(U)>* = nullptr>
void write_unsigned(U uval) {
size_t len = calc_len(uval);
pos += len;
char* ptr = line.data() + pos;
while (uval >= 100) {
ptr -= 2;
memcpy(ptr, small[uval % 100].data(), 2);
uval /= 100;
}
if (uval >= 10) {
memcpy(ptr - 2, small[uval].data(), 2);
} else {
*(ptr - 1) = char('0' + uval);
}
}
template <class U,
internal::is_unsigned_int_t<U>* = nullptr,
std::enable_if_t<4 == sizeof(U)>* = nullptr>
void write_unsigned(U uval) {
std::array<char, 8> buf;
memcpy(buf.data() + 6, small[uval % 100].data(), 2);
memcpy(buf.data() + 4, small[uval / 100 % 100].data(), 2);
memcpy(buf.data() + 2, small[uval / 10000 % 100].data(), 2);
memcpy(buf.data() + 0, small[uval / 1000000 % 100].data(), 2);
if (uval >= 100000000) {
if (uval >= 1000000000) {
memcpy(line.data() + pos, small[uval / 100000000 % 100].data(),
2);
pos += 2;
} else {
line[pos] = char('0' + uval / 100000000);
pos++;
}
memcpy(line.data() + pos, buf.data(), 8);
pos += 8;
} else {
size_t len = calc_len(uval);
memcpy(line.data() + pos, buf.data() + (8 - len), len);
pos += len;
}
}
template <class U,
internal::is_unsigned_int_t<U>* = nullptr,
std::enable_if_t<8 == sizeof(U)>* = nullptr>
void write_unsigned(U uval) {
size_t len = calc_len(uval);
pos += len;
char* ptr = line.data() + pos;
while (uval >= 100) {
ptr -= 2;
memcpy(ptr, small[uval % 100].data(), 2);
uval /= 100;
}
if (uval >= 10) {
memcpy(ptr - 2, small[uval].data(), 2);
} else {
*(ptr - 1) = char('0' + uval);
}
}
template <
class U,
std::enable_if_t<internal::is_unsigned_int128<U>::value>* = nullptr>
void write_unsigned(U uval) {
static std::array<char, 50> buf;
size_t len = 0;
while (uval > 0) {
buf[len++] = char((uval % 10) + '0');
uval /= 10;
}
std::reverse(buf.begin(), buf.begin() + len);
memcpy(line.data() + pos, buf.data(), len);
pos += len;
}
void write_single(const std::string& s) {
for (char c : s) write_single(c);
}
void write_single(const char* s) {
size_t len = strlen(s);
for (size_t i = 0; i < len; i++) write_single(s[i]);
}
template <class T> void write_single(const std::vector<T>& val) {
auto n = val.size();
for (size_t i = 0; i < n; i++) {
if (i) write_single(' ');
write_single(val[i]);
}
}
};
inline std::array<std::array<char, 2>, 100> Printer::small = [] {
std::array<std::array<char, 2>, 100> table;
for (int i = 0; i <= 99; i++) {
table[i][1] = char('0' + (i % 10));
table[i][0] = char('0' + (i / 10 % 10));
}
return table;
}();
inline std::array<unsigned long long, 20> Printer::tens = [] {
std::array<unsigned long long, 20> table;
for (int i = 0; i < 20; i++) {
table[i] = 1;
for (int j = 0; j < i; j++) {
table[i] *= 10;
}
}
return table;
}();
} // namespace yosupo
#include <chrono>
namespace yosupo {
struct StopWatch {
std::chrono::steady_clock::time_point begin;
StopWatch() : begin(std::chrono::steady_clock::now()) {}
int msecs() {
auto now = std::chrono::steady_clock::now();
return int(
duration_cast<std::chrono::milliseconds>(now - begin).count());
}
};
} // namespace yosupo
#include <bitset>
#include <cmath>
#include <iostream>
#include <map>
#include <queue>
#include <ranges>
#include <set>
#include <utility>
#include <concepts>
#include <cstddef>
#include <tuple>
namespace yosupo {
using i8 = int8_t;
using u8 = uint8_t;
using i16 = int16_t;
using u16 = uint16_t;
using i32 = int32_t;
using u32 = uint32_t;
using i64 = int64_t;
using u64 = uint64_t;
using i128 = __int128;
using u128 = unsigned __int128;
using f32 = float;
using f64 = double;
} // namespace yosupo
namespace yosupo {
inline std::string dump(const std::string& t) { return t; }
inline std::string dump(const char* t) { return t; }
template <std::integral T> std::string dump(T t) { return std::to_string(t); }
inline std::string dump(const u128& t) {
if (t == 0) {
return "0";
}
std::string s;
u128 x = t;
while (x) {
s += char(x % 10 + '0');
x /= 10;
}
std::ranges::reverse(s);
return s;
}
inline std::string dump(const i128& t) {
if (t < 0) {
return "-" + dump((u128)(-t));
} else {
return dump((u128)(t));
}
}
template <std::floating_point T> std::string dump(T t) {
return std::to_string(t);
}
template <class T>
requires requires(T t) { t.dump(); }
std::string dump(T t);
template <class T>
requires(!requires(T t) { t.dump(); }) && (requires(T t) { t.val(); })
std::string dump(T t);
template <class T, std::size_t N> std::string dump(const std::array<T, N>&);
template <class T> std::string dump(const std::vector<T>&);
template <class T1, class T2> std::string dump(const std::pair<T1, T2>&);
template <class K, class V> std::string dump(const std::map<K, V>&);
template <class T> std::string dump(const std::set<T>&);
template <class... Ts> std::string dump(const std::tuple<Ts...>& t);
template <class T>
requires requires(T t) { t.dump(); }
std::string dump(T t) {
return dump(t.dump());
}
template <class T>
requires(!requires(T t) { t.dump(); }) && (requires(T t) { t.val(); })
std::string dump(T t) {
return dump(t.val());
}
template <class T, std::size_t N> std::string dump(const std::array<T, N>& a) {
std::string s = "[";
for (size_t i = 0; i < N; i++) {
if (i) {
s += ", ";
}
s += dump(a[i]);
}
s += "]";
return s;
}
template <class T> std::string dump(const std::vector<T>& v) {
std::string s = "[";
for (std::size_t i = 0; i < v.size(); ++i) {
s += dump(v[i]);
if (i + 1 != v.size()) {
s += ", ";
}
}
s += "]";
return s;
}
template <class T1, class T2> std::string dump(const std::pair<T1, T2>& p) {
std::string s = "(";
s += dump(p.first);
s += ", ";
s += dump(p.second);
s += ")";
return s;
}
template <class K, class V> std::string dump(const std::map<K, V>& m) {
std::string s = "{";
for (auto it = m.begin(); it != m.end(); ++it) {
if (it != m.begin()) {
s += ", ";
}
s += dump(it->first);
s += ": ";
s += dump(it->second);
}
s += "}";
return s;
}
template <class T> std::string dump(const std::set<T>& s) {
std::string str = "{";
for (auto it = s.begin(); it != s.end(); ++it) {
if (it != s.begin()) {
str += ", ";
}
str += dump(*it);
}
str += "}";
return str;
}
template <class... Ts> std::string dump(const std::tuple<Ts...>& t) {
std::string s = "(";
[&]<std::size_t... I>(std::index_sequence<I...>) {
((s += dump(std::get<I>(t)) + ((I < sizeof...(Ts) - 1) ? ", " : "")),
...);
}(std::make_index_sequence<sizeof...(Ts)>());
s += ")";
return s;
}
} // namespace yosupo
#include <functional>
#include <span>
namespace yosupo {
template <class T> bool chmin(T& a, const T& b) {
if (a > b) {
a = b;
return true;
}
return false;
}
template <class T> bool chmax(T& a, const T& b) {
if (a < b) {
a = b;
return true;
}
return false;
}
template <class T> T floor_div(T x, T y) {
auto d = x / y;
auto r = x % y;
if (r == 0) return d;
if ((r > 0) == (y > 0)) return d;
return d - 1;
}
template <class T> T ceil_div(T x, T y) {
auto d = x / y;
auto r = x % y;
if (r == 0) return d;
if ((r > 0) == (y > 0)) return d + 1;
return d;
}
template <std::ranges::input_range R>
std::vector<std::ranges::range_value_t<R>> to_vec(R&& r) {
auto common = r | std::views::common;
return std::vector(common.begin(), common.end());
}
template <class T, class Comp = std::equal_to<>>
void dedup(std::vector<T>& v, Comp comp = Comp{}) {
auto it = std::ranges::unique(v, comp);
v.erase(it.begin(), it.end());
}
template <size_t N, class T> std::span<T, N> subspan(std::span<T> a, int idx) {
return a.subspan(idx).template first<N>();
}
inline auto rep(int l, int r) {
if (l > r) return std::views::iota(l, l);
return std::views::iota(l, r);
}
} // namespace yosupo
using namespace yosupo;
using std::abs, std::pow, std::sqrt;
using std::array, std::vector, std::string, std::queue, std::deque;
using std::countl_zero, std::countl_one, std::countr_zero, std::countr_one;
using std::istream, std::ostream, std::cerr, std::endl;
using std::min, std::max, std::swap;
using std::pair, std::tuple, std::bitset;
using std::popcount;
using std::priority_queue, std::set, std::multiset, std::map;
using std::views::iota, std::views::reverse;
namespace ranges = std::ranges;
using ranges::sort, ranges::copy_n;
using uint = unsigned int;
using ll = long long;
using ull = unsigned long long;
constexpr ll TEN(int n) { return (n == 0) ? 1 : 10 * TEN(n - 1); }
template <class T> using V = vector<T>;
template <class T> using VV = V<V<T>>;
#ifdef YOSUPO_LOCAL
struct PrettyOS {
ostream& os;
bool first;
template <class T> auto operator<<(T&& x) {
if (!first) os << ", ";
first = false;
os << yosupo::dump(x);
return *this;
}
};
template <class... T> void dbg0(T&&... t) {
(PrettyOS{cerr, true} << ... << t);
}
#define dbg(...) \
do { \
cerr << __LINE__ << " : " << #__VA_ARGS__ << " = "; \
dbg0(__VA_ARGS__); \
cerr << endl; \
} while (false);
#else
#define dbg(...)
#endif
#include <limits>
#include <random>
namespace yosupo {
struct Xoshiro256StarStar {
public:
using result_type = u64;
Xoshiro256StarStar() : Xoshiro256StarStar(0) {}
explicit Xoshiro256StarStar(u64 seed) {
// use splitmix64
// Reference: http://xoshiro.di.unimi.it/splitmix64.c
for (int i = 0; i < 4; i++) {
u64 z = (seed += 0x9e3779b97f4a7c15);
z = (z ^ (z >> 30)) * 0xbf58476d1ce4e5b9;
z = (z ^ (z >> 27)) * 0x94d049bb133111eb;
s[i] = z ^ (z >> 31);
}
}
static constexpr result_type min() { return 0; }
static constexpr result_type max() { return -1; }
result_type operator()() {
const u64 result_starstar = rotl(s[1] * 5, 7) * 9;
const u64 t = s[1] << 17;
s[2] ^= s[0];
s[3] ^= s[1];
s[1] ^= s[2];
s[0] ^= s[3];
s[2] ^= t;
s[3] = rotl(s[3], 45);
return result_starstar;
}
private:
// Use xoshiro256**
// Refereces: http://xoshiro.di.unimi.it/xoshiro256starstar.c
static u64 rotl(const u64 x, int k) { return (x << k) | (x >> (64 - k)); }
std::array<u64, 4> s;
};
// https://github.com/wangyi-fudan/wyhash
struct WYRand {
public:
using result_type = u64;
explicit WYRand(u64 seed) : s(seed) {}
static constexpr result_type min() { return 0; }
static constexpr result_type max() { return -1; }
result_type operator()() {
s += 0x2d358dccaa6c78a5;
auto x = (u128)s * (s ^ 0x8bb84b93962eacc9);
return (u64)(x ^ (x >> 64));
}
private:
uint64_t s;
};
using Random = WYRand;
inline Random get_random() { return Random(std::random_device()()); }
namespace internal {
inline Random global_gen = get_random();
}
inline Random& global_gen() { return internal::global_gen; }
template <class G>
concept random_64 = std::uniform_random_bit_generator<G> &&
std::same_as<u64, std::invoke_result_t<G&>> &&
G::min() == u64(0) && G::max() == u64(-1);
namespace internal {
// random choice from [0, upper]
template <random_64 G> u64 uniform_u64(u64 upper, G& gen) {
if (upper == 0) return 0;
u64 mask = (std::bit_floor(upper) << 1) - 1;
while (true) {
u64 r = gen() & mask;
if (r <= upper) return r;
}
}
// random choice from [0, upper], faster than uniform_u64
template <random_64 G> u64 random_u64(u64 upper, G& gen) {
return (u64)(((u128)(upper) + 1) * gen() >> 64);
}
} // namespace internal
template <class T, random_64 G> T uniform(T lower, T upper, G& gen) {
return T(lower + internal::uniform_u64(u64(upper) - u64(lower), gen));
}
template <class T> T uniform(T lower, T upper) {
return uniform(lower, upper, global_gen());
}
template <std::unsigned_integral T, random_64 G> T uniform(G& gen) {
return T(gen());
}
template <std::signed_integral T, random_64 G> T uniform(G& gen) {
return T(gen() + (u64)std::numeric_limits<T>::min());
}
template <class T, random_64 G>
requires requires {
{ T::mod() } -> std::integral;
}
T uniform(G& gen) {
return T(uniform(0, T::mod() - 1, gen));
}
template <class T> T uniform() { return uniform<T>(global_gen()); }
template <class T, random_64 G> T random(T lower, T upper, G& gen) {
return T(lower + internal::random_u64(u64(upper) - u64(lower), gen));
}
template <class T> T random(T lower, T upper) {
return random(lower, upper, global_gen());
}
template <random_64 G> bool uniform_bool(G& gen) { return gen() & 1; }
inline bool uniform_bool() { return uniform_bool(global_gen()); }
// select 2 elements from [lower, uppper]
template <class T, random_64 G>
std::pair<T, T> uniform_pair(T lower, T upper, G& gen) {
assert(upper - lower >= 1);
T a, b;
do {
a = uniform(lower, upper, gen);
b = uniform(lower, upper, gen);
} while (a == b);
if (a > b) std::swap(a, b);
return {a, b};
}
template <class T> std::pair<T, T> uniform_pair(T lower, T upper) {
return uniform_pair(lower, upper, global_gen());
}
// random 0.0 <= X < 1.0
template <class G> inline double random_01(G& gen) {
constexpr double inv = 1.0 / ((double)(u64(1) << 63) * 2);
return double(gen()) * inv;
}
inline double random_01() { return random_01(global_gen()); }
} // namespace yosupo
namespace yosupo {
struct Coord {
public:
constexpr Coord() : d{0, 0} {}
constexpr Coord(int _r, int _c) : d{_r, _c} {}
constexpr Coord(const std::pair<int, int>& p) : d{p.first, p.second} {}
bool operator==(const Coord& other) const { return d == other.d; }
Coord& operator+=(const Coord& other) {
d[0] += other.d[0];
d[1] += other.d[1];
return *this;
}
Coord operator+(const Coord& other) const {
Coord result = *this;
result += other;
return result;
}
Coord& operator-=(const Coord& other) {
d[0] -= other.d[0];
d[1] -= other.d[1];
return *this;
}
Coord operator-(const Coord& other) const {
Coord result = *this;
result -= other;
return result;
}
int& r() { return d[0]; }
int& c() { return d[1]; }
const int& r() const { return d[0]; }
const int& c() const { return d[1]; }
int& operator[](int index) {
if (index == 0) return d[0];
if (index == 1) return d[1];
assert(false);
}
const int& operator[](int index) const {
if (index == 0) return d[0];
if (index == 1) return d[1];
assert(false);
}
operator std::pair<int, int>() const { return std::make_pair(d[0], d[1]); }
std::string dump() const {
return "(" + std::to_string(d[0]) + ", " + std::to_string(d[1]) + ")";
}
Coord move4(int dir) const {
static constexpr std::array<Coord, 4> d4 = {Coord(0, 1), Coord(1, 0),
Coord(0, -1), Coord(-1, 0)};
return *this + d4[dir];
}
auto move4() const {
return std::views::iota(0, 4) | std::views::transform([this](int dir) {
return this->move4(dir);
});
}
Coord move8(int dir) const {
static constexpr std::array<Coord, 8> d8 = {
Coord(0, 1), Coord(1, 1), Coord(1, 0), Coord(1, -1),
Coord(0, -1), Coord(-1, -1), Coord(-1, 0), Coord(-1, 1)};
assert(0 <= dir && dir < 8);
return *this + d8[dir];
}
auto move8() const {
return std::views::iota(0, 8) | std::views::transform([this](int dir) {
return this->move8(dir);
});
}
bool contains(const Coord& t) const {
return 0 <= t.r() && t.r() < r() && 0 <= t.c() && t.c() < c();
}
struct CellsRangeView {
struct Iterator {
using value_type = Coord;
using difference_type = std::ptrdiff_t;
int h, w, r, c;
value_type operator*() const { return Coord{r, c}; }
Iterator& operator++() {
if (++c == w) {
c = 0;
++r;
}
return *this;
}
Iterator operator++(int) {
Iterator tmp = *this;
++(*this);
return tmp;
}
bool operator==(const Iterator& other) const {
return r == other.r && c == other.c;
}
};
Iterator begin() const { return Iterator{h, w, 0, 0}; }
Iterator end() const { return Iterator{h, w, h, 0}; }
int h, w;
};
CellsRangeView cells() const { return CellsRangeView{r(), c()}; }
private:
std::array<int, 2> d;
};
} // namespace yosupo
namespace marathon {
inline constexpr int kBoardSize = 32;
inline constexpr yosupo::Coord kBoardShape{kBoardSize, kBoardSize};
struct Problem {
int n = kBoardSize;
int k = 0;
int c = 0;
std::vector<std::vector<int>> g;
};
struct Action {
int type = 0; // 0: paint, 1: copy, 2: clear
int k = 0; // target layer
int h = 0; // source layer (for copy)
int r = 0; // rotation (for copy)
int i = 0;
int j = 0; // for paint: position, for copy: shift
int x = 0; // color (for paint)
};
using Answer = std::vector<Action>;
template <class Scanner> Problem read_problem(Scanner& sc) {
Problem problem;
sc.read(problem.n, problem.k, problem.c);
problem.g.assign(problem.n, std::vector<int>(problem.n));
for (int i = 0; i < problem.n; ++i) {
for (int j = 0; j < problem.n; ++j) {
sc.read(problem.g[i][j]);
}
}
return problem;
}
inline int count_goal_nonzero(const Problem& problem) {
int count = 0;
for (const auto& row : problem.g) {
for (int color : row) {
count += (color != 0);
}
}
return count;
}
inline int calc_score(int goal_nonzero, const Answer& answer) {
if (goal_nonzero == 0) {
return 0;
}
if (answer.empty()) {
return 1 << 29;
}
double ratio = 2.0 * (double)answer.size() / (double)goal_nonzero;
double score = 10.0 * (1.0 + std::log(ratio) / std::log(6.0));
return (int)std::llround(score);
}
inline int calc_score(const Problem& problem, const Answer& answer) {
return calc_score(count_goal_nonzero(problem), answer);
}
inline long long calc_actual_score(int goal_nonzero, const Answer& answer) {
if (goal_nonzero == 0 || answer.empty()) {
return 0;
}
double ratio = (double)goal_nonzero / (double)answer.size();
double score = 1'000'000.0 * (1.0 + std::log2(ratio));
return (long long)std::llround(score);
}
inline long long calc_actual_score(const Problem& problem,
const Answer& answer) {
return calc_actual_score(count_goal_nonzero(problem), answer);
}
inline void push_paint(Answer& actions, int k, int i, int j, int x) {
actions.push_back({0, k, 0, 0, i, j, x});
}
inline void push_copy(Answer& actions, int k, int h, int r, int di, int dj) {
actions.push_back({1, k, h, r, di, dj, 0});
}
inline void push_clear(Answer& actions, int k) {
actions.push_back({2, k, 0, 0, 0, 0, 0});
}
inline yosupo::Coord rotate_in_full(yosupo::Coord pos, int n, int r) {
if (r == 0) return pos;
if (r == 1) return {pos.c(), n - 1 - pos.r()};
if (r == 2) return {n - 1 - pos.r(), n - 1 - pos.c()};
return {n - 1 - pos.c(), pos.r()};
}
inline bool replay_and_check(const Problem& problem, const Answer& actions) {
if ((int)actions.size() > problem.n * problem.n) {
return false;
}
std::vector<std::vector<std::vector<int>>> layer(
problem.k,
std::vector<std::vector<int>>(problem.n,
std::vector<int>(problem.n, 0)));
const yosupo::Coord shape{problem.n, problem.n};
for (const auto& action : actions) {
if (action.type == 0) {
yosupo::Coord pos{action.i, action.j};
if (!(0 <= action.k && action.k < problem.k &&
shape.contains(pos) &&
0 <= action.x && action.x <= problem.c)) {
return false;
}
layer[action.k][pos.r()][pos.c()] = action.x;
continue;
}
if (action.type == 1) {
if (!(0 <= action.k && action.k < problem.k && 0 <= action.h &&
action.h < problem.k && 0 <= action.r && action.r < 4)) {
return false;
}
yosupo::Coord shift{action.i, action.j};
std::vector<std::pair<yosupo::Coord, int>> writes;
writes.reserve(problem.n * problem.n);
for (yosupo::Coord src : shape.cells()) {
int color = layer[action.h][src.r()][src.c()];
if (color == 0) continue;
yosupo::Coord dst =
shift + rotate_in_full(src, problem.n, action.r);
if (!shape.contains(dst)) {
return false;
}
writes.push_back({dst, color});
}
for (const auto& [dst, color] : writes) {
layer[action.k][dst.r()][dst.c()] = color;
}
continue;
}
if (action.type == 2) {
if (!(0 <= action.k && action.k < problem.k)) {
return false;
}
for (auto& row : layer[action.k]) {
std::fill(row.begin(), row.end(), 0);
}
continue;
}
return false;
}
return layer[0] == problem.g;
}
inline bool is_valid_answer(const Problem& problem, const Answer& answer) {
return (int)answer.size() <= problem.n * problem.n &&
replay_and_check(problem, answer);
}
inline bool better_answer(const Problem& problem,
const Answer& candidate,
const Answer& current_best) {
int candidate_score = calc_score(problem, candidate);
int best_score = calc_score(problem, current_best);
if (candidate_score != best_score) {
return candidate_score < best_score;
}
return candidate.size() < current_best.size();
}
template <class Printer>
void print_answer(const Answer& answer, Printer& pr) {
for (const auto& action : answer) {
if (action.type == 0) {
pr.write(action.type);
pr.write(' ');
pr.write(action.k);
pr.write(' ');
pr.write(action.i);
pr.write(' ');
pr.write(action.j);
pr.write(' ');
pr.write(action.x);
pr.write('\n');
continue;
}
if (action.type == 1) {
pr.write(action.type);
pr.write(' ');
pr.write(action.k);
pr.write(' ');
pr.write(action.h);
pr.write(' ');
pr.write(action.r);
pr.write(' ');
pr.write(action.i);
pr.write(' ');
pr.write(action.j);
pr.write('\n');
continue;
}
pr.write(action.type);
pr.write(' ');
pr.write(action.k);
pr.write('\n');
}
}
} // namespace marathon
#include <unordered_set>
namespace sigma3_port {
struct Action {
int type = 0;
int k = 0;
int h = 0;
int r = 0;
int i = 0;
int j = 0;
int x = 0;
};
namespace detail {
struct Cell {
int x = 0;
int y = 0;
int color = 0;
};
struct Occurrence {
int r = 0;
int ai = 0;
int aj = 0;
int gain = 0;
};
struct ReversePlan {
int saving = 0;
int size = 0;
std::vector<Cell> cells;
std::vector<Occurrence> uses;
};
constexpr int STAR = -1;
inline std::pair<int, int> rotate_in_square(int x, int y, int s, int r) {
if (r == 0) return {x, y};
if (r == 1) return {y, s - 1 - x};
if (r == 2) return {s - 1 - x, s - 1 - y};
return {s - 1 - y, x};
}
inline std::string canonical_key(const std::vector<std::vector<int>>& cur,
int bi,
int bj,
int s) {
std::vector<std::string> keys;
keys.reserve(4);
for (int r = 0; r < 4; ++r) {
std::string key;
key.reserve(static_cast<std::size_t>(s * s + 8));
key += static_cast<char>('0' + std::min(s, 9));
key += ':';
for (int x = 0; x < s; ++x) {
for (int y = 0; y < s; ++y) {
auto [rx, ry] = rotate_in_square(x, y, s, r);
int color = cur[bi + rx][bj + ry];
key += (color == STAR) ? '*' : static_cast<char>('0' + color);
}
}
keys.push_back(std::move(key));
}
return *std::min_element(keys.begin(), keys.end());
}
inline int current_reverse_gain(const std::vector<Cell>& cells,
int s,
int r,
int ai,
int aj,
const std::vector<std::vector<int>>& cur) {
int gain = 0;
for (const auto& cell : cells) {
auto [rx, ry] = rotate_in_square(cell.x, cell.y, s, r);
if (cur[ai + rx][aj + ry] == cell.color) {
++gain;
}
}
return gain;
}
inline std::vector<Occurrence> select_occurrences_reverse_greedily(
const std::vector<Cell>& cells,
int s,
const std::vector<std::vector<int>>& cur) {
const int n = static_cast<int>(cur.size());
std::vector<Occurrence> candidates;
for (int r = 0; r < 4; ++r) {
for (int ai = 0; ai + s <= n; ++ai) {
for (int aj = 0; aj + s <= n; ++aj) {
bool ok = true;
int gain = 0;
for (const auto& cell : cells) {
auto [rx, ry] = rotate_in_square(cell.x, cell.y, s, r);
int v = cur[ai + rx][aj + ry];
if (v != STAR && v != cell.color) {
ok = false;
break;
}
if (v == cell.color) {
++gain;
}
}
if (ok && gain >= 2) {
candidates.push_back({r, ai, aj, gain});
}
}
}
}
std::vector<std::vector<int>> temp = cur;
std::vector<Occurrence> chosen;
std::vector<char> used(candidates.size(), 0);
while (true) {
int best_idx = -1;
int best_gain = 0;
for (int idx = 0; idx < static_cast<int>(candidates.size()); ++idx) {
if (used[idx]) continue;
int gain = current_reverse_gain(cells, s, candidates[idx].r,
candidates[idx].ai,
candidates[idx].aj, temp);
if (gain > best_gain) {
best_gain = gain;
best_idx = idx;
}
}
if (best_idx == -1 || best_gain < 2) {
break;
}
used[best_idx] = 1;
Occurrence occ = candidates[best_idx];
occ.gain = best_gain;
chosen.push_back(occ);
for (const auto& cell : cells) {
auto [rx, ry] = rotate_in_square(cell.x, cell.y, s, occ.r);
int& v = temp[occ.ai + rx][occ.aj + ry];
if (v == cell.color) {
v = STAR;
}
}
}
return chosen;
}
inline ReversePlan evaluate_stamp_reverse(
const std::vector<Cell>& cells,
int s,
const std::vector<std::vector<int>>& cur,
bool need_clear) {
ReversePlan plan;
if (static_cast<int>(cells.size()) < 4) {
return plan;
}
std::vector<Occurrence> uses =
select_occurrences_reverse_greedily(cells, s, cur);
if (uses.empty()) {
return plan;
}
int total_gain = 0;
for (const auto& occ : uses) {
total_gain += occ.gain;
}
int setup_cost =
static_cast<int>(cells.size()) + static_cast<int>(uses.size()) +
(need_clear ? 1 : 0);
int saving = total_gain - setup_cost;
if (saving <= 0) {
return plan;
}
plan.saving = saving;
plan.size = s;
plan.cells = cells;
plan.uses = std::move(uses);
return plan;
}
template <class StopPredicate>
inline std::vector<Occurrence> select_occurrences_reverse_greedily(
const std::vector<Cell>& cells,
int s,
const std::vector<std::vector<int>>& cur,
const StopPredicate& should_stop) {
const int n = static_cast<int>(cur.size());
std::vector<Occurrence> candidates;
for (int r = 0; r < 4; ++r) {
if (should_stop()) {
return {};
}
for (int ai = 0; ai + s <= n; ++ai) {
if (should_stop()) {
return {};
}
for (int aj = 0; aj + s <= n; ++aj) {
bool ok = true;
int gain = 0;
for (const auto& cell : cells) {
auto [rx, ry] = rotate_in_square(cell.x, cell.y, s, r);
int v = cur[ai + rx][aj + ry];
if (v != STAR && v != cell.color) {
ok = false;
break;
}
if (v == cell.color) {
++gain;
}
}
if (ok && gain >= 2) {
candidates.push_back({r, ai, aj, gain});
}
}
}
}
std::vector<std::vector<int>> temp = cur;
std::vector<Occurrence> chosen;
std::vector<char> used(candidates.size(), 0);
while (true) {
if (should_stop()) {
return chosen;
}
int best_idx = -1;
int best_gain = 0;
for (int idx = 0; idx < static_cast<int>(candidates.size()); ++idx) {
if (used[idx]) continue;
int gain = current_reverse_gain(cells, s, candidates[idx].r,
candidates[idx].ai,
candidates[idx].aj, temp);
if (gain > best_gain) {
best_gain = gain;
best_idx = idx;
}
}
if (best_idx == -1 || best_gain < 2) {
break;
}
used[best_idx] = 1;
Occurrence occ = candidates[best_idx];
occ.gain = best_gain;
chosen.push_back(occ);
for (const auto& cell : cells) {
auto [rx, ry] = rotate_in_square(cell.x, cell.y, s, occ.r);
int& v = temp[occ.ai + rx][occ.aj + ry];
if (v == cell.color) {
v = STAR;
}
}
}
return chosen;
}
template <class StopPredicate>
inline ReversePlan evaluate_stamp_reverse(
const std::vector<Cell>& cells,
int s,
const std::vector<std::vector<int>>& cur,
bool need_clear,
const StopPredicate& should_stop) {
ReversePlan plan;
if (static_cast<int>(cells.size()) < 4 || should_stop()) {
return plan;
}
std::vector<Occurrence> uses =
select_occurrences_reverse_greedily(cells, s, cur, should_stop);
if (uses.empty()) {
return plan;
}
int total_gain = 0;
for (const auto& occ : uses) {
total_gain += occ.gain;
}
int setup_cost =
static_cast<int>(cells.size()) + static_cast<int>(uses.size()) +
(need_clear ? 1 : 0);
int saving = total_gain - setup_cost;
if (saving <= 0) {
return plan;
}
plan.saving = saving;
plan.size = s;
plan.cells = cells;
plan.uses = std::move(uses);
return plan;
}
template <class StopPredicate>
inline ReversePlan find_best_reverse_plan(
const std::vector<std::vector<int>>& cur,
bool need_clear,
const StopPredicate& should_stop) {
const int n = static_cast<int>(cur.size());
int remaining = 0;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
remaining += (cur[i][j] != 0);
if (cur[i][j] == STAR) {
--remaining;
}
}
}
if (remaining < 4) {
return {};
}
ReversePlan best;
const std::vector<int> sizes = {2, 3, 4, 5, 6};
for (int s : sizes) {
if (should_stop()) {
return best;
}
std::unordered_set<std::string> seen;
for (int bi = 0; bi + s <= n; ++bi) {
if (should_stop()) {
return best;
}
for (int bj = 0; bj + s <= n; ++bj) {
if (should_stop()) {
return best;
}
std::string key = canonical_key(cur, bi, bj, s);
if (!seen.insert(key).second) {
continue;
}
std::vector<Cell> cells;
for (int x = 0; x < s; ++x) {
for (int y = 0; y < s; ++y) {
int color = cur[bi + x][bj + y];
if (color > 0) {
cells.push_back({x, y, color});
}
}
}
ReversePlan plan =
evaluate_stamp_reverse(cells, s, cur, need_clear,
should_stop);
if (plan.saving > best.saving) {
best = std::move(plan);
}
if (should_stop()) {
return best;
}
}
}
}
return best;
}
inline void apply_reverse_plan(std::vector<std::vector<int>>& cur,
const ReversePlan& plan) {
for (const auto& occ : plan.uses) {
for (const auto& cell : plan.cells) {
auto [rx, ry] = rotate_in_square(cell.x, cell.y, plan.size, occ.r);
int& v = cur[occ.ai + rx][occ.aj + ry];
if (v == cell.color) {
v = STAR;
}
}
}
}
inline std::vector<Action> build_forward_actions(
const std::vector<std::vector<int>>& base,
const std::vector<ReversePlan>& reverse_plans,
int main_layer,
int aux_layer) {
const int n = static_cast<int>(base.size());
std::vector<Action> actions;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
if (base[i][j] > 0) {
actions.push_back({0, main_layer, 0, 0, i, j, base[i][j]});
}
}
}
bool aux_initialized = false;
for (int idx = static_cast<int>(reverse_plans.size()) - 1; idx >= 0; --idx) {
const auto& plan = reverse_plans[idx];
if (aux_initialized) {
actions.push_back({2, aux_layer, 0, 0, 0, 0, 0});
}
aux_initialized = true;
for (const auto& cell : plan.cells) {
actions.push_back(
{0, aux_layer, 0, 0, cell.x, cell.y, cell.color});
}
int shift = n - plan.size;
for (int t = static_cast<int>(plan.uses.size()) - 1; t >= 0; --t) {
const auto& occ = plan.uses[t];
int di = occ.ai;
int dj = occ.aj;
if (occ.r == 1) {
dj -= shift;
} else if (occ.r == 2) {
di -= shift;
dj -= shift;
} else if (occ.r == 3) {
di -= shift;
}
actions.push_back({1, main_layer, aux_layer, occ.r, di, dj, 0});
}
}
return actions;
}
} // namespace detail
template <class StopPredicate>
inline std::vector<Action> solve_with_stop(
const std::vector<std::vector<int>>& goal,
int main_layer,
int aux_layer,
const StopPredicate& should_stop) {
if (goal.empty()) {
return {};
}
std::vector<std::vector<int>> cur = goal;
std::vector<detail::ReversePlan> reverse_plans;
const int n = static_cast<int>(goal.size());
while (!should_stop()) {
detail::ReversePlan plan =
detail::find_best_reverse_plan(cur, !reverse_plans.empty(),
should_stop);
if (plan.saving <= 0) {
break;
}
reverse_plans.push_back(plan);
detail::apply_reverse_plan(cur, reverse_plans.back());
if (static_cast<int>(reverse_plans.size()) > n * n) {
break;
}
}
return detail::build_forward_actions(cur, reverse_plans, main_layer,
aux_layer);
}
inline std::vector<Action> solve(const std::vector<std::vector<int>>& goal,
int main_layer = 0,
int aux_layer = 1) {
auto never_stop = []() { return false; };
return solve_with_stop(goal, main_layer, aux_layer, never_stop);
}
} // namespace sigma3_port
namespace my1_solver {
using marathon::Action;
using marathon::Answer;
using marathon::Problem;
inline constexpr int N = marathon::kBoardSize;
inline constexpr Coord BOARD_SHAPE = marathon::kBoardShape;
inline constexpr int kInvalidCost = 1 << 29;
inline constexpr int kDefaultBudgetMs = 1100;
inline constexpr int kSigma3StopGuardMs = 80;
inline Answer build_fallback_actions(const Problem& problem) {
Answer actions;
for (int i = 0; i < problem.n; ++i) {
for (int j = 0; j < problem.n; ++j) {
if (problem.g[i][j] != 0) {
marathon::push_paint(actions, 0, i, j, problem.g[i][j]);
}
}
}
return actions;
}
inline int answer_cost(const Problem& problem, const Answer& actions) {
if (!marathon::is_valid_answer(problem, actions)) {
return kInvalidCost;
}
return (int)actions.size();
}
namespace detail {
constexpr int STAR = -1;
constexpr int HILL_MARGIN_MS = 25;
constexpr int SEARCH_MARGIN_MS = 20;
constexpr int MAX_STAMP_OPAQUE = 80;
struct Cell {
Coord pos;
int color = 0;
};
struct RotStamp {
int h = 0;
int w = 0;
V<Cell> cells;
};
struct Occurrence {
int r = 0;
int ai = 0;
int aj = 0;
int gain = 0;
};
struct ReversePlan {
int saving = 0;
int opaque = 0;
int total_gain = 0;
int h = 0;
int w = 0;
VV<int> stamp;
array<RotStamp, 4> rots;
V<Occurrence> uses;
};
struct Context {
explicit Context(const Problem& problem_) : problem(problem_) {}
const Problem& problem;
Random rng = get_random();
int time_budget_ms = 0;
int remaining_ms(StopWatch& timer) const {
return time_budget_ms - timer.msecs();
}
bool time_over(StopWatch& timer) const { return remaining_ms(timer) <= 0; }
int rand_int(int lo, int hi) { return yosupo::random(lo, hi, rng); }
bool chance(double p) { return yosupo::random_01(rng) < p; }
int count_stamp_opaque(const VV<int>& stamp) const {
int cnt = 0;
for (const auto& row : stamp) {
for (int color : row) {
cnt += (color != 0);
}
}
return cnt;
}
int count_fixed_nonzero(const VV<int>& state) const {
int cnt = 0;
for (const auto& row : state) {
for (int color : row) {
cnt += (color > 0);
}
}
return cnt;
}
V<Coord> list_fixed_nonzero(const VV<int>& state) const {
V<Coord> ps;
ps.reserve(N * N);
for (int i = 0; i < N; ++i) {
for (int j = 0; j < N; ++j) {
if (state[i][j] > 0) {
ps.push_back({i, j});
}
}
}
return ps;
}
VV<int> crop_pattern(const VV<int>& src) const {
const int h = (int)src.size();
const int w = h ? (int)src[0].size() : 0;
int min_i = h;
int min_j = w;
int max_i = -1;
int max_j = -1;
for (int i = 0; i < h; ++i) {
for (int j = 0; j < w; ++j) {
if (src[i][j] != 0) {
min_i = min(min_i, i);
min_j = min(min_j, j);
max_i = max(max_i, i);
max_j = max(max_j, j);
}
}
}
if (max_i == -1) {
return {};
}
VV<int> dst(max_i - min_i + 1, V<int>(max_j - min_j + 1, 0));
for (int i = min_i; i <= max_i; ++i) {
for (int j = min_j; j <= max_j; ++j) {
dst[i - min_i][j - min_j] = src[i][j];
}
}
return dst;
}
array<RotStamp, 4> make_rotations(const VV<int>& stamp) const {
const int h = (int)stamp.size();
const int w = h ? (int)stamp[0].size() : 0;
V<Cell> base;
base.reserve(h * w);
for (int i = 0; i < h; ++i) {
for (int j = 0; j < w; ++j) {
if (stamp[i][j] != 0) {
base.push_back({Coord{i, j}, stamp[i][j]});
}
}
}
array<RotStamp, 4> rots;
rots[0] = {h, w, base};
rots[1].h = w;
rots[1].w = h;
rots[1].cells.reserve(base.size());
for (const auto& cell : base) {
rots[1].cells.push_back(
{Coord{cell.pos.c(), h - 1 - cell.pos.r()}, cell.color});
}
rots[2].h = h;
rots[2].w = w;
rots[2].cells.reserve(base.size());
for (const auto& cell : base) {
rots[2].cells.push_back(
{Coord{h - 1 - cell.pos.r(), w - 1 - cell.pos.c()}, cell.color});
}
rots[3].h = w;
rots[3].w = h;
rots[3].cells.reserve(base.size());
for (const auto& cell : base) {
rots[3].cells.push_back(
{Coord{w - 1 - cell.pos.c(), cell.pos.r()}, cell.color});
}
return rots;
}
Coord rotate_in_rect(Coord pos, int h, int w, int r) const {
if (r == 0) return pos;
if (r == 1) return {pos.c(), h - 1 - pos.r()};
if (r == 2) return {h - 1 - pos.r(), w - 1 - pos.c()};
return {w - 1 - pos.c(), pos.r()};
}
int small_biased_len(int cap) {
int x = 0;
while (x < cap && !yosupo::uniform_bool(rng)) {
++x;
}
return x;
}
bool make_tiny_random_stamp(const VV<int>& state, VV<int>& out_stamp) {
auto fixed = list_fixed_nonzero(state);
if (fixed.empty()) {
return false;
}
Coord center = fixed[rand_int(0, (int)fixed.size() - 1)];
int ci = center.r();
int cj = center.c();
int h = rand_int(2, 4);
int w = rand_int(2, 4);
int r0_lo = max(0, ci - h + 1);
int r0_hi = min(ci, N - h);
int c0_lo = max(0, cj - w + 1);
int c0_hi = min(cj, N - w);
if (r0_lo > r0_hi || c0_lo > c0_hi) {
return false;
}
int r0 = rand_int(r0_lo, r0_hi);
int c0 = rand_int(c0_lo, c0_hi);
int li = ci - r0;
int lj = cj - c0;
VV<int> stamp(h, V<int>(w, 0));
int opaque = 0;
bool has_fixed = false;
for (int i = 0; i < h; ++i) {
for (int j = 0; j < w; ++j) {
bool keep = chance(0.5);
if (i == li && j == lj) {
keep = true;
}
if (!keep) {
continue;
}
int color = state[r0 + i][c0 + j];
if (color <= 0) {
continue;
}
stamp[i][j] = color;
++opaque;
has_fixed = true;
}
}
if (opaque < 2 || !has_fixed) {
return false;
}
out_stamp = std::move(stamp);
return true;
}
bool make_random_stamp(const VV<int>& state, VV<int>& out_stamp) {
if (chance(0.35)) {
return make_tiny_random_stamp(state, out_stamp);
}
auto fixed = list_fixed_nonzero(state);
if (fixed.empty()) {
return false;
}
Coord center = fixed[rand_int(0, (int)fixed.size() - 1)];
int ci = center.r();
int cj = center.c();
int up = small_biased_len(ci);
int left = small_biased_len(cj);
int down = small_biased_len(N - 1 - ci);
int right = small_biased_len(N - 1 - cj);
if (chance(0.18)) {
up = rand_int(0, ci);
left = rand_int(0, cj);
down = rand_int(0, N - 1 - ci);
right = rand_int(0, N - 1 - cj);
}
int r0 = ci - up;
int r1 = ci + down;
int c0 = cj - left;
int c1 = cj + right;
int max_h = chance(0.85) ? 10 : 20;
int max_w = chance(0.85) ? 10 : 20;
if (r1 - r0 + 1 > max_h) {
if (chance(0.5)) {
r1 = r0 + max_h - 1;
} else {
r0 = r1 - max_h + 1;
}
}
if (c1 - c0 + 1 > max_w) {
if (chance(0.5)) {
c1 = c0 + max_w - 1;
} else {
c0 = c1 - max_w + 1;
}
}
V<pair<int, int>> candidates;
candidates.reserve((r1 - r0 + 1) * (c1 - c0 + 1));
for (int i = r0; i <= r1; ++i) {
for (int j = c0; j <= c1; ++j) {
if (state[i][j] > 0) {
candidates.push_back({i, j});
}
}
}
if (candidates.empty()) {
return false;
}
static constexpr double table[] = {0.00, 0.08, 0.15, 0.25, 0.35, 0.50};
double p_drop =
table[rand_int(0, (int)(sizeof(table) / sizeof(table[0])) - 1)];
V<pair<int, int>> kept;
kept.reserve(candidates.size());
for (const auto& [i, j] : candidates) {
bool keep = !chance(p_drop);
if (i == ci && j == cj) {
keep = true;
}
if (keep) {
kept.push_back({i, j});
}
}
if ((int)kept.size() < 2) {
return false;
}
int min_i = N;
int min_j = N;
int max_i = -1;
int max_j = -1;
for (const auto& [i, j] : kept) {
min_i = min(min_i, i);
min_j = min(min_j, j);
max_i = max(max_i, i);
max_j = max(max_j, j);
}
VV<int> stamp(max_i - min_i + 1, V<int>(max_j - min_j + 1, 0));
for (const auto& [i, j] : kept) {
stamp[i - min_i][j - min_j] = state[i][j];
}
stamp = crop_pattern(stamp);
int opaque = count_stamp_opaque(stamp);
if (opaque < 2 || opaque > MAX_STAMP_OPAQUE) {
return false;
}
out_stamp = std::move(stamp);
return true;
}
int gain_at(const RotStamp& rot, int ai, int aj, const VV<int>& state) const {
int gain = 0;
for (const auto& cell : rot.cells) {
int target = state[ai + cell.pos.r()][aj + cell.pos.c()];
if (target != STAR && target != cell.color) {
return -1;
}
if (target > 0) {
++gain;
}
}
return gain;
}
ReversePlan evaluate_candidate(const VV<int>& state,
const VV<int>& stamp,
bool need_clear) const {
ReversePlan plan;
plan.stamp = stamp;
plan.opaque = count_stamp_opaque(stamp);
if (plan.opaque < 2) {
return plan;
}
plan.h = (int)stamp.size();
plan.w = plan.h ? (int)stamp[0].size() : 0;
if (plan.h == 0 || plan.w == 0 || plan.h > N || plan.w > N) {
return plan;
}
plan.rots = make_rotations(stamp);
V<Occurrence> occs;
for (int r = 0; r < 4; ++r) {
const auto& rot = plan.rots[r];
if (rot.cells.empty() || rot.h > N || rot.w > N) {
continue;
}
for (int ai = 0; ai + rot.h <= N; ++ai) {
for (int aj = 0; aj + rot.w <= N; ++aj) {
int gain = gain_at(rot, ai, aj, state);
if (gain >= 2) {
occs.push_back({r, ai, aj, gain});
}
}
}
}
if (occs.empty()) {
return plan;
}
sort(occs, [](const Occurrence& a, const Occurrence& b) {
if (a.gain != b.gain) return a.gain > b.gain;
if (a.ai != b.ai) return a.ai < b.ai;
if (a.aj != b.aj) return a.aj < b.aj;
return a.r < b.r;
});
VV<int> temp = state;
int total_gain = 0;
for (const auto& occ : occs) {
const auto& rot = plan.rots[occ.r];
int gain = 0;
bool ok = true;
for (const auto& cell : rot.cells) {
int target = temp[occ.ai + cell.pos.r()][occ.aj + cell.pos.c()];
if (target != STAR && target != cell.color) {
ok = false;
break;
}
gain += (target > 0);
}
if (!ok || gain < 2) {
continue;
}
plan.uses.push_back({occ.r, occ.ai, occ.aj, gain});
total_gain += gain;
for (const auto& cell : rot.cells) {
temp[occ.ai + cell.pos.r()][occ.aj + cell.pos.c()] = STAR;
}
}
if (plan.uses.empty()) {
return plan;
}
plan.total_gain = total_gain;
int setup_cost =
plan.opaque + (int)plan.uses.size() + (need_clear ? 1 : 0);
plan.saving = total_gain - setup_cost;
return plan;
}
bool better_plan(const ReversePlan& a, const ReversePlan& b) const {
if (a.uses.empty()) return false;
if (b.uses.empty()) return true;
if (a.saving != b.saving) return a.saving > b.saving;
if (a.total_gain != b.total_gain) return a.total_gain > b.total_gain;
if (a.uses.size() != b.uses.size()) return a.uses.size() > b.uses.size();
return a.opaque < b.opaque;
}
VV<int> mutate_stamp_once(const VV<int>& stamp, const ReversePlan& plan) {
if (stamp.empty() || stamp[0].empty() || plan.uses.empty()) {
return {};
}
int h = (int)stamp.size();
int w = (int)stamp[0].size();
const auto& ref = plan.uses[rand_int(0, (int)plan.uses.size() - 1)];
int pad_top = chance(0.3) ? 1 : 0;
int pad_bottom = chance(0.3) ? 1 : 0;
int pad_left = chance(0.3) ? 1 : 0;
int pad_right = chance(0.3) ? 1 : 0;
int nh = h + pad_top + pad_bottom;
int nw = w + pad_left + pad_right;
VV<int> cand(nh, V<int>(nw, 0));
for (int i = 0; i < h; ++i) {
for (int j = 0; j < w; ++j) {
cand[i + pad_top][j + pad_left] = stamp[i][j];
}
}
V<Coord> nonzero;
for (int i = 0; i < nh; ++i) {
for (int j = 0; j < nw; ++j) {
if (cand[i][j] != 0) {
nonzero.push_back({i, j});
}
}
}
if (nonzero.empty()) {
return {};
}
int mode = rand_int(0, 2);
if (mode == 0 && (int)nonzero.size() >= 2) {
Coord pos = nonzero[rand_int(0, (int)nonzero.size() - 1)];
cand[pos.r()][pos.c()] = 0;
} else {
Coord pos{rand_int(0, nh - 1), rand_int(0, nw - 1)};
Coord goal_pos =
Coord{ref.ai, ref.aj} + rotate_in_rect(pos, nh, nw, ref.r);
if (BOARD_SHAPE.contains(goal_pos)) {
int color = problem.g[goal_pos.r()][goal_pos.c()];
if (color == 0) {
color = rand_int(1, problem.c);
}
cand[pos.r()][pos.c()] = color;
} else if (mode == 2) {
Coord src = nonzero[rand_int(0, (int)nonzero.size() - 1)];
Coord dst = src + Coord{rand_int(-1, 1), rand_int(-1, 1)};
Coord stamp_shape{nh, nw};
dst.r() = max(0, min(nh - 1, dst.r()));
dst.c() = max(0, min(nw - 1, dst.c()));
if (!stamp_shape.contains(dst)) {
return {};
}
cand[dst.r()][dst.c()] = cand[src.r()][src.c()];
} else {
return {};
}
}
cand = crop_pattern(cand);
if (cand.empty()) {
return {};
}
int opaque = count_stamp_opaque(cand);
if (opaque < 2 || opaque > MAX_STAMP_OPAQUE) {
return {};
}
return cand;
}
ReversePlan hill_climb_plan(const VV<int>& state,
const VV<int>& initial_stamp,
bool need_clear,
StopWatch& timer) {
ReversePlan best = evaluate_candidate(state, initial_stamp, need_clear);
if (best.uses.empty()) {
return best;
}
int fail = 0;
while (!time_over(timer) && remaining_ms(timer) >= HILL_MARGIN_MS &&
!best.uses.empty() && fail < 20) {
ReversePlan local_best = best;
bool improved = false;
for (int t = 0; t < 8 && !time_over(timer); ++t) {
auto mutated = mutate_stamp_once(best.stamp, best);
if (mutated.empty()) {
continue;
}
auto cand = evaluate_candidate(state, mutated, need_clear);
if (better_plan(cand, local_best)) {
local_best = std::move(cand);
improved = true;
}
}
if (!improved) {
++fail;
continue;
}
best = std::move(local_best);
fail = 0;
}
return best;
}
ReversePlan find_best_reverse_plan(const VV<int>& state,
bool need_clear,
StopWatch& timer) {
ReversePlan best;
int remaining = count_fixed_nonzero(state);
if (remaining < 4) {
return best;
}
int trials = 4500;
if (remaining < 150) trials = 2500;
if (remaining < 60) trials = 1200;
trials *= 10;
for (int it = 0; it < trials && !time_over(timer); ++it) {
if (remaining_ms(timer) < SEARCH_MARGIN_MS) {
break;
}
VV<int> stamp;
if (!make_random_stamp(state, stamp)) {
continue;
}
auto cand = hill_climb_plan(state, stamp, need_clear, timer);
if (better_plan(cand, best)) {
best = std::move(cand);
}
}
return best;
}
void apply_reverse_plan(VV<int>& state, const ReversePlan& plan) const {
for (const auto& occ : plan.uses) {
const auto& rot = plan.rots[occ.r];
for (const auto& cell : rot.cells) {
state[occ.ai + cell.pos.r()][occ.aj + cell.pos.c()] = STAR;
}
}
}
Coord copy_delta(int ai, int aj, int h, int w, int r) const {
if (r == 0) return {ai, aj};
if (r == 1) return {ai, aj - (N - h)};
if (r == 2) return {ai - (N - h), aj - (N - w)};
return {ai - (N - w), aj};
}
Answer build_forward_actions(const VV<int>& base,
const V<ReversePlan>& reverse_plans) const {
Answer actions;
for (int i = 0; i < N; ++i) {
for (int j = 0; j < N; ++j) {
if (base[i][j] > 0) {
marathon::push_paint(actions, 0, i, j, base[i][j]);
}
}
}
bool aux_initialized = false;
for (int idx = (int)reverse_plans.size() - 1; idx >= 0; --idx) {
const auto& plan = reverse_plans[idx];
if (aux_initialized) {
marathon::push_clear(actions, 1);
}
aux_initialized = true;
for (int i = 0; i < plan.h; ++i) {
for (int j = 0; j < plan.w; ++j) {
if (plan.stamp[i][j] != 0) {
marathon::push_paint(actions, 1, i, j, plan.stamp[i][j]);
}
}
}
for (int t = (int)plan.uses.size() - 1; t >= 0; --t) {
const auto& occ = plan.uses[t];
Coord delta = copy_delta(occ.ai, occ.aj, plan.h, plan.w, occ.r);
marathon::push_copy(actions, 0, 1, occ.r, delta.r(), delta.c());
}
}
return actions;
}
Answer solve(StopWatch& timer) {
VV<int> cur = problem.g;
V<ReversePlan> reverse_plans;
while (!time_over(timer)) {
auto plan = find_best_reverse_plan(cur, !reverse_plans.empty(), timer);
if (plan.saving <= 0) {
break;
}
reverse_plans.push_back(plan);
apply_reverse_plan(cur, reverse_plans.back());
if ((int)reverse_plans.size() > N * N) {
break;
}
}
return build_forward_actions(cur, reverse_plans);
}
};
inline Action convert_sigma3_action(const sigma3_port::Action& action) {
return {action.type, action.k, action.h, action.r,
action.i, action.j, action.x};
}
inline Answer convert_sigma3_actions(const std::vector<sigma3_port::Action>& actions) {
Answer converted;
converted.reserve(actions.size());
for (const auto& action : actions) {
converted.push_back(convert_sigma3_action(action));
}
return converted;
}
} // namespace detail
inline Answer solve(const Problem& problem,
int available_ms) {
if (available_ms <= 0) {
return {};
}
detail::Context ctx(problem);
ctx.time_budget_ms = min(available_ms, kDefaultBudgetMs);
StopWatch local_timer;
return ctx.solve(local_timer);
}
inline Answer solve_sigma3(const Problem& problem,
int available_ms) {
int stop_budget_ms = available_ms - kSigma3StopGuardMs;
if (stop_budget_ms <= 0) {
return {};
}
StopWatch local_timer;
auto raw_actions = sigma3_port::solve_with_stop(
problem.g, 0, 1, [&]() { return local_timer.msecs() >= stop_budget_ms; });
return detail::convert_sigma3_actions(raw_actions);
}
} // namespace my1_solver
#include <unordered_map>
namespace sol_md_solver {
using marathon::Action;
using marathon::Answer;
using marathon::Problem;
inline constexpr int N = marathon::kBoardSize;
inline constexpr Coord BOARD_SHAPE = marathon::kBoardShape;
inline constexpr int STAR = -1;
inline constexpr int kDefaultBudgetMs = 1750;
inline constexpr int kSearchMarginMs = 15;
inline constexpr int kHillMarginMs = 12;
inline constexpr int kMaxStampOpaque = 64 * 10;
inline constexpr int kMaxSeedSize = 10;
inline constexpr int kLocalSeedLimit = 12 * 10;
inline constexpr int kLocalIters = 40;
inline constexpr int kBestRefineRounds = 10;
struct Cell {
Coord pos;
int color = 0;
};
struct RotStamp {
int h = 0;
int w = 0;
V<Cell> cells;
};
struct Occurrence {
int r = 0;
int ai = 0;
int aj = 0;
int gain = 0;
};
struct ReversePlan {
int saving = 0;
int opaque = 0;
int total_gain = 0;
int build_cost = 0;
bool is_self_copy = false;
int self_r = 0;
int self_di = 0;
int self_dj = 0;
int h = 0;
int w = 0;
VV<int> stamp;
array<RotStamp, 4> rots;
V<Occurrence> uses;
V<Coord> self_removed;
};
struct SeedCandidate {
int bi = 0;
int bj = 0;
int s = 0;
int opaque = 0;
VV<int> stamp;
ReversePlan base_plan;
};
struct StampBuildPlan {
int cost = 0;
V<Action> ops;
};
inline Answer build_fallback_actions(const Problem& problem) {
Answer actions;
for (int i = 0; i < problem.n; ++i) {
for (int j = 0; j < problem.n; ++j) {
if (problem.g[i][j] != 0) {
marathon::push_paint(actions, 0, i, j, problem.g[i][j]);
}
}
}
return actions;
}
struct Context {
explicit Context(const Problem& problem_) : problem(problem_) {}
const Problem& problem;
Random rng = get_random();
int time_budget_ms = 0;
mutable std::unordered_map<string, StampBuildPlan> build_plan_cache;
int remaining_ms(StopWatch& timer) const {
return time_budget_ms - timer.msecs();
}
bool time_over(StopWatch& timer) const { return remaining_ms(timer) <= 0; }
int rand_int(int lo, int hi) { return yosupo::random(lo, hi, rng); }
bool chance(double p) { return yosupo::random_01(rng) < p; }
int count_fixed_nonzero(const VV<int>& state) const {
int cnt = 0;
for (const auto& row : state) {
for (int color : row) {
cnt += (color > 0);
}
}
return cnt;
}
int count_stamp_opaque(const VV<int>& stamp) const {
int cnt = 0;
for (const auto& row : stamp) {
for (int color : row) {
cnt += (color != 0);
}
}
return cnt;
}
V<Coord> list_fixed_nonzero(const VV<int>& state) const {
V<Coord> ps;
ps.reserve(N * N);
for (int i = 0; i < N; ++i) {
for (int j = 0; j < N; ++j) {
if (state[i][j] > 0) {
ps.push_back({i, j});
}
}
}
return ps;
}
VV<int> crop_pattern(const VV<int>& src) const {
const int h = (int)src.size();
const int w = h ? (int)src[0].size() : 0;
int min_i = h;
int min_j = w;
int max_i = -1;
int max_j = -1;
for (int i = 0; i < h; ++i) {
for (int j = 0; j < w; ++j) {
if (src[i][j] != 0) {
min_i = min(min_i, i);
min_j = min(min_j, j);
max_i = max(max_i, i);
max_j = max(max_j, j);
}
}
}
if (max_i == -1) {
return {};
}
VV<int> dst(max_i - min_i + 1, V<int>(max_j - min_j + 1, 0));
for (int i = min_i; i <= max_i; ++i) {
for (int j = min_j; j <= max_j; ++j) {
dst[i - min_i][j - min_j] = src[i][j];
}
}
return dst;
}
string canonical_key_square(const VV<int>& state, int bi, int bj, int s) const {
V<string> keys;
keys.reserve(4);
for (int r = 0; r < 4; ++r) {
string key;
key.reserve(s * s * 3 + 8);
key += std::to_string(s);
key += ':';
for (int i = 0; i < s; ++i) {
for (int j = 0; j < s; ++j) {
Coord pos{i, j};
Coord rot = rotate_in_rect(pos, s, s, r);
int color = state[bi + rot.r()][bj + rot.c()];
if (color == STAR) {
key += "*,";
} else {
key += std::to_string(color);
key += ',';
}
}
}
keys.push_back(std::move(key));
}
return *ranges::min_element(keys);
}
VV<int> make_square_seed_stamp(const VV<int>& state, int bi, int bj, int s) const {
VV<int> stamp(s, V<int>(s, 0));
for (int i = 0; i < s; ++i) {
for (int j = 0; j < s; ++j) {
if (state[bi + i][bj + j] > 0) {
stamp[i][j] = state[bi + i][bj + j];
}
}
}
return crop_pattern(stamp);
}
void push_seed(V<SeedCandidate>& seeds, SeedCandidate seed) const {
seeds.push_back(std::move(seed));
sort(seeds, [&](const SeedCandidate& a, const SeedCandidate& b) {
if (a.base_plan.saving != b.base_plan.saving) {
return a.base_plan.saving > b.base_plan.saving;
}
if (a.base_plan.total_gain != b.base_plan.total_gain) {
return a.base_plan.total_gain > b.base_plan.total_gain;
}
if (a.opaque != b.opaque) {
return a.opaque > b.opaque;
}
return a.s < b.s;
});
if ((int)seeds.size() > kLocalSeedLimit) {
seeds.resize(kLocalSeedLimit);
}
}
string stamp_key(const VV<int>& stamp) const {
string key;
key.reserve(stamp.size() * (stamp.empty() ? 1 : stamp[0].size() * 3 + 1) + 16);
key += std::to_string((int)stamp.size());
key += ':';
key += std::to_string(stamp.empty() ? 0 : (int)stamp[0].size());
key += ':';
for (const auto& row : stamp) {
for (int color : row) {
key += std::to_string(color);
key += ',';
}
key += ';';
}
return key;
}
const StampBuildPlan& get_stamp_build_plan(const VV<int>& stamp) const {
string key = stamp_key(stamp);
auto it = build_plan_cache.find(key);
if (it != build_plan_cache.end()) {
return it->second;
}
StampBuildPlan plan;
int h = (int)stamp.size();
int w = h ? (int)stamp[0].size() : 0;
for (int i = 0; i < h; ++i) {
for (int j = 0; j < w; ++j) {
if (stamp[i][j] != 0) {
plan.ops.push_back({0, 0, 0, 0, i, j, stamp[i][j]});
}
}
}
plan.cost = (int)plan.ops.size();
auto [inserted_it, _] =
build_plan_cache.emplace(std::move(key), std::move(plan));
return inserted_it->second;
}
array<RotStamp, 4> make_rotations(const VV<int>& stamp) const {
const int h = (int)stamp.size();
const int w = h ? (int)stamp[0].size() : 0;
V<Cell> base;
base.reserve(h * w);
for (int i = 0; i < h; ++i) {
for (int j = 0; j < w; ++j) {
if (stamp[i][j] != 0) {
base.push_back({Coord{i, j}, stamp[i][j]});
}
}
}
array<RotStamp, 4> rots;
rots[0] = {h, w, base};
rots[1].h = w;
rots[1].w = h;
rots[1].cells.reserve(base.size());
for (const auto& cell : base) {
rots[1].cells.push_back(
{Coord{cell.pos.c(), h - 1 - cell.pos.r()}, cell.color});
}
rots[2].h = h;
rots[2].w = w;
rots[2].cells.reserve(base.size());
for (const auto& cell : base) {
rots[2].cells.push_back(
{Coord{h - 1 - cell.pos.r(), w - 1 - cell.pos.c()}, cell.color});
}
rots[3].h = w;
rots[3].w = h;
rots[3].cells.reserve(base.size());
for (const auto& cell : base) {
rots[3].cells.push_back(
{Coord{w - 1 - cell.pos.c(), cell.pos.r()}, cell.color});
}
return rots;
}
Coord rotate_in_rect(Coord pos, int h, int w, int r) const {
if (r == 0) return pos;
if (r == 1) return {pos.c(), h - 1 - pos.r()};
if (r == 2) return {h - 1 - pos.r(), w - 1 - pos.c()};
return {w - 1 - pos.c(), pos.r()};
}
bool make_random_stamp(const VV<int>& state, VV<int>& out_stamp) {
auto fixed = list_fixed_nonzero(state);
if (fixed.empty()) {
return false;
}
Coord center = fixed[rand_int(0, (int)fixed.size() - 1)];
int ci = center.r();
int cj = center.c();
int max_h = 10;
int max_w = 10;
if (chance(0.12)) {
max_h = 16;
max_w = 16;
}
if (chance(0.04)) {
max_h = N;
max_w = N;
}
int h = rand_int(2, max_h);
int w = rand_int(2, max_w);
int r0_lo = max(0, ci - h + 1);
int r0_hi = min(ci, N - h);
int c0_lo = max(0, cj - w + 1);
int c0_hi = min(cj, N - w);
if (r0_lo > r0_hi || c0_lo > c0_hi) {
return false;
}
int r0 = rand_int(r0_lo, r0_hi);
int c0 = rand_int(c0_lo, c0_hi);
int li = ci - r0;
int lj = cj - c0;
VV<int> stamp(h, V<int>(w, 0));
int opaque = 0;
bool dense = chance(0.25);
for (int i = 0; i < h; ++i) {
for (int j = 0; j < w; ++j) {
int color = state[r0 + i][c0 + j];
if (color <= 0) {
continue;
}
bool keep = dense || chance(0.6);
if (i == li && j == lj) {
keep = true;
}
if (!keep) {
continue;
}
stamp[i][j] = color;
++opaque;
}
}
stamp = crop_pattern(stamp);
opaque = count_stamp_opaque(stamp);
if (opaque < 4 || opaque > kMaxStampOpaque) {
return false;
}
out_stamp = std::move(stamp);
return true;
}
int gain_at(const RotStamp& rot, int ai, int aj, const VV<int>& state) const {
int gain = 0;
for (const auto& cell : rot.cells) {
int target = state[ai + cell.pos.r()][aj + cell.pos.c()];
if (target != STAR && target != cell.color) {
return -1;
}
gain += (target > 0);
}
return gain;
}
int current_gain_at(const RotStamp& rot,
int ai,
int aj,
const VV<int>& state) const {
int gain = 0;
for (const auto& cell : rot.cells) {
int target = state[ai + cell.pos.r()][aj + cell.pos.c()];
if (target == cell.color) {
++gain;
}
}
return gain;
}
ReversePlan evaluate_candidate(const VV<int>& state,
const VV<int>& stamp) const {
ReversePlan plan;
plan.stamp = stamp;
plan.opaque = count_stamp_opaque(stamp);
if (plan.opaque < 4) {
return plan;
}
plan.build_cost = get_stamp_build_plan(stamp).cost;
plan.h = (int)stamp.size();
plan.w = plan.h ? (int)stamp[0].size() : 0;
if (plan.h == 0 || plan.w == 0 || plan.h > N || plan.w > N) {
return plan;
}
plan.rots = make_rotations(stamp);
V<Occurrence> occs;
for (int r = 0; r < 4; ++r) {
const auto& rot = plan.rots[r];
if (rot.cells.empty()) {
continue;
}
for (int ai = 0; ai + rot.h <= N; ++ai) {
for (int aj = 0; aj + rot.w <= N; ++aj) {
int gain = gain_at(rot, ai, aj, state);
if (gain >= 2) {
occs.push_back({r, ai, aj, gain});
}
}
}
}
if (occs.empty()) {
return plan;
}
VV<int> temp = state;
V<char> used(occs.size(), 0);
while (true) {
int best_idx = -1;
int best_gain = 0;
for (int idx = 0; idx < (int)occs.size(); ++idx) {
if (used[idx]) {
continue;
}
int gain =
current_gain_at(plan.rots[occs[idx].r], occs[idx].ai, occs[idx].aj,
temp);
if (gain > best_gain) {
best_gain = gain;
best_idx = idx;
}
}
if (best_idx == -1 || best_gain < 2) {
break;
}
used[best_idx] = 1;
auto occ = occs[best_idx];
occ.gain = best_gain;
plan.uses.push_back(occ);
plan.total_gain += best_gain;
const auto& rot = plan.rots[occ.r];
for (const auto& cell : rot.cells) {
int& target = temp[occ.ai + cell.pos.r()][occ.aj + cell.pos.c()];
if (target == cell.color) {
target = STAR;
}
}
}
if (plan.uses.empty()) {
return plan;
}
int setup_cost = plan.build_cost + (int)plan.uses.size();
plan.saving = plan.total_gain - setup_cost;
if (plan.saving <= 0) {
return ReversePlan{};
}
return plan;
}
bool better_plan(const ReversePlan& a, const ReversePlan& b) const {
if (!has_reverse_action(a)) return false;
if (!has_reverse_action(b)) return true;
return a.saving > b.saving;
}
bool has_reverse_action(const ReversePlan& plan) const {
if (plan.is_self_copy) {
return !plan.self_removed.empty();
}
return !plan.uses.empty();
}
bool solve_self_copy_path(const V<int>& nodes,
const V<char>& keepable,
V<char>& selected) const {
static constexpr int INF = 1 << 29;
const int m = (int)nodes.size();
V<array<int, 2>> dp(m, {INF, INF});
V<array<int, 2>> parent(m, {-1, -1});
if (!keepable[nodes[0]]) {
return false;
}
dp[0][1] = 1;
for (int i = 1; i < m; ++i) {
for (int prev = 0; prev < 2; ++prev) {
if (dp[i - 1][prev] >= INF) {
continue;
}
for (int cur = 0; cur < 2; ++cur) {
if (cur && !keepable[nodes[i]]) {
continue;
}
if (!(prev || cur)) {
continue;
}
int cand = dp[i - 1][prev] + cur;
if (cand < dp[i][cur]) {
dp[i][cur] = cand;
parent[i][cur] = prev;
}
}
}
}
int last = (dp[m - 1][0] <= dp[m - 1][1] ? 0 : 1);
if (dp[m - 1][last] >= INF) {
return false;
}
for (int i = m - 1; i >= 0; --i) {
selected[nodes[i]] = static_cast<char>(last);
if (i > 0) {
last = parent[i][last];
}
}
return true;
}
bool solve_self_copy_cycle(const V<int>& nodes,
const V<char>& keepable,
V<char>& selected) const {
static constexpr int INF = 1 << 29;
const int m = (int)nodes.size();
int best_cost = INF;
V<char> best_local(m, 0);
for (int first = 0; first < 2; ++first) {
if (first && !keepable[nodes[0]]) {
continue;
}
V<array<int, 2>> dp(m, {INF, INF});
V<array<int, 2>> parent(m, {-1, -1});
dp[0][first] = first;
for (int i = 1; i < m; ++i) {
for (int prev = 0; prev < 2; ++prev) {
if (dp[i - 1][prev] >= INF) {
continue;
}
for (int cur = 0; cur < 2; ++cur) {
if (cur && !keepable[nodes[i]]) {
continue;
}
if (!(prev || cur)) {
continue;
}
int cand = dp[i - 1][prev] + cur;
if (cand < dp[i][cur]) {
dp[i][cur] = cand;
parent[i][cur] = prev;
}
}
}
}
for (int last = 0; last < 2; ++last) {
if (dp[m - 1][last] >= INF) {
continue;
}
if (!(last || first)) {
continue;
}
if (dp[m - 1][last] >= best_cost) {
continue;
}
V<char> local(m, 0);
int cur = last;
for (int i = m - 1; i >= 0; --i) {
local[i] = static_cast<char>(cur);
if (i > 0) {
cur = parent[i][cur];
}
}
best_cost = dp[m - 1][last];
best_local = std::move(local);
}
}
if (best_cost >= INF) {
return false;
}
for (int i = 0; i < m; ++i) {
selected[nodes[i]] = best_local[i];
}
return true;
}
ReversePlan evaluate_self_copy_candidate(const VV<int>& state,
const V<Coord>& fixed,
const V<int>& index_of,
int r,
int di,
int dj) const {
ReversePlan plan;
plan.is_self_copy = true;
plan.self_r = r;
plan.self_di = di;
plan.self_dj = dj;
if (r == 0 && di == 0 && dj == 0) {
return plan;
}
const int m = (int)fixed.size();
V<int> succ(m, -1), pred(m, -1);
V<char> keepable(m, 0), visited(m, 0), selected(m, 0);
for (int idx = 0; idx < m; ++idx) {
Coord src = fixed[idx];
int color = state[src.r()][src.c()];
Coord dst = Coord{di, dj} + marathon::rotate_in_full(src, N, r);
if (!BOARD_SHAPE.contains(dst)) {
keepable[idx] = 1;
continue;
}
if (state[dst.r()][dst.c()] != color) {
continue;
}
int to = index_of[dst.r() * N + dst.c()];
if (to < 0) {
continue;
}
keepable[idx] = 1;
succ[idx] = to;
if (pred[to] != -1) {
return ReversePlan{};
}
pred[to] = idx;
}
for (int start = 0; start < m; ++start) {
if (visited[start] || pred[start] != -1) {
continue;
}
V<int> nodes;
for (int cur = start; cur != -1 && !visited[cur]; cur = succ[cur]) {
visited[cur] = 1;
nodes.push_back(cur);
}
if (!solve_self_copy_path(nodes, keepable, selected)) {
return ReversePlan{};
}
}
for (int start = 0; start < m; ++start) {
if (visited[start]) {
continue;
}
V<int> nodes;
int cur = start;
do {
visited[cur] = 1;
nodes.push_back(cur);
cur = succ[cur];
} while (cur != start);
if (!solve_self_copy_cycle(nodes, keepable, selected)) {
return ReversePlan{};
}
}
for (int idx = 0; idx < m; ++idx) {
if (!selected[idx]) {
plan.self_removed.push_back(fixed[idx]);
}
}
plan.total_gain = (int)plan.self_removed.size();
plan.saving = plan.total_gain - 1;
if (plan.total_gain < 2) {
return ReversePlan{};
}
return plan;
}
ReversePlan find_best_self_copy_plan(const VV<int>& state,
StopWatch& timer) const {
ReversePlan best;
V<Coord> fixed = list_fixed_nonzero(state);
if ((int)fixed.size() < 2) {
return best;
}
V<int> index_of(N * N, -1);
for (int idx = 0; idx < (int)fixed.size(); ++idx) {
index_of[fixed[idx].r() * N + fixed[idx].c()] = idx;
}
for (int r = 0; r < 4; ++r) {
for (int di = -N + 1; di < N; ++di) {
for (int dj = -N + 1; dj < N; ++dj) {
if (remaining_ms(timer) < kSearchMarginMs) {
return best;
}
auto cand =
evaluate_self_copy_candidate(state, fixed, index_of, r, di, dj);
if (better_plan(cand, best)) {
best = std::move(cand);
}
}
}
}
return best;
}
VV<int> mutate_stamp_once(const VV<int>& stamp, const ReversePlan& plan) {
if (stamp.empty() || stamp[0].empty() || plan.uses.empty()) {
return {};
}
int h = (int)stamp.size();
int w = (int)stamp[0].size();
const auto& ref = plan.uses[rand_int(0, (int)plan.uses.size() - 1)];
int pad_top = chance(0.3) ? 1 : 0;
int pad_bottom = chance(0.3) ? 1 : 0;
int pad_left = chance(0.3) ? 1 : 0;
int pad_right = chance(0.3) ? 1 : 0;
int nh = h + pad_top + pad_bottom;
int nw = w + pad_left + pad_right;
VV<int> cand(nh, V<int>(nw, 0));
for (int i = 0; i < h; ++i) {
for (int j = 0; j < w; ++j) {
cand[i + pad_top][j + pad_left] = stamp[i][j];
}
}
V<Coord> nonzero;
for (int i = 0; i < nh; ++i) {
for (int j = 0; j < nw; ++j) {
if (cand[i][j] != 0) {
nonzero.push_back({i, j});
}
}
}
if (nonzero.empty()) {
return {};
}
int mode = rand_int(0, 3);
if (mode == 0 && (int)nonzero.size() >= 2) {
Coord pos = nonzero[rand_int(0, (int)nonzero.size() - 1)];
cand[pos.r()][pos.c()] = 0;
} else if (mode == 1) {
Coord pos{rand_int(0, nh - 1), rand_int(0, nw - 1)};
Coord goal_pos =
Coord{ref.ai, ref.aj} + rotate_in_rect(pos, nh, nw, ref.r);
if (!BOARD_SHAPE.contains(goal_pos)) {
return {};
}
int color = problem.g[goal_pos.r()][goal_pos.c()];
if (color <= 0) {
color = rand_int(1, problem.c);
}
cand[pos.r()][pos.c()] = color;
} else if (mode == 2) {
Coord src = nonzero[rand_int(0, (int)nonzero.size() - 1)];
Coord dst = src + Coord{rand_int(-1, 1), rand_int(-1, 1)};
dst.r() = max(0, min(nh - 1, dst.r()));
dst.c() = max(0, min(nw - 1, dst.c()));
cand[dst.r()][dst.c()] = cand[src.r()][src.c()];
} else {
Coord pos = nonzero[rand_int(0, (int)nonzero.size() - 1)];
if (problem.c >= 2) {
int color = cand[pos.r()][pos.c()];
int new_color = rand_int(1, problem.c - 1);
if (new_color >= color) {
++new_color;
}
cand[pos.r()][pos.c()] = min(problem.c, new_color);
}
}
cand = crop_pattern(cand);
if (cand.empty()) {
return {};
}
int opaque = count_stamp_opaque(cand);
if (opaque < 4 || opaque > kMaxStampOpaque) {
return {};
}
return cand;
}
ReversePlan hill_climb_plan(const VV<int>& state,
const VV<int>& initial_stamp,
StopWatch& timer) {
ReversePlan current = evaluate_candidate(state, initial_stamp);
ReversePlan best = current;
int stalled = 0;
for (int iter = 0; iter < kLocalIters * 10; ++iter) {
if (remaining_ms(timer) < kHillMarginMs) {
break;
}
auto mutated = mutate_stamp_once(current.stamp, current);
if (mutated.empty()) {
++stalled;
continue;
}
auto cand = evaluate_candidate(state, mutated);
if (better_plan(cand, current)) {
current = cand;
stalled = 0;
if (better_plan(current, best)) {
best = current;
}
} else if (!better_plan(current, cand)) {
current = cand;
++stalled;
if (stalled >= 10) {
break;
}
} else {
++stalled;
if (stalled >= 10) {
break;
}
}
}
return best;
}
ReversePlan refine_best_plan(const VV<int>& state,
ReversePlan best,
StopWatch& timer) {
if (best.is_self_copy || best.uses.empty()) {
return best;
}
int stalled = 0;
while (!time_over(timer) &&
remaining_ms(timer) >= kHillMarginMs &&
stalled < kBestRefineRounds) {
auto improved = hill_climb_plan(state, best.stamp, timer);
if (better_plan(improved, best)) {
best = std::move(improved);
stalled = 0;
continue;
}
auto perturbed = mutate_stamp_once(best.stamp, best);
if (!perturbed.empty()) {
improved = hill_climb_plan(state, perturbed, timer);
if (better_plan(improved, best)) {
best = std::move(improved);
stalled = 0;
continue;
}
}
++stalled;
}
return best;
}
ReversePlan find_best_reverse_plan(const VV<int>& state,
StopWatch& timer) {
ReversePlan best; // = find_best_self_copy_plan(state, timer);
int remaining = count_fixed_nonzero(state);
if (remaining < 4) {
return best;
}
V<SeedCandidate> seeds;
for (int s = 2; s <= min(kMaxSeedSize, N); ++s) {
if (remaining_ms(timer) < kSearchMarginMs) {
break;
}
set<string> seen;
for (int bi = 0; bi + s <= N; ++bi) {
for (int bj = 0; bj + s <= N; ++bj) {
if (remaining_ms(timer) < kSearchMarginMs) {
return best;
}
string key = canonical_key_square(state, bi, bj, s);
if (!seen.insert(key).second) {
continue;
}
VV<int> stamp = make_square_seed_stamp(state, bi, bj, s);
int opaque = count_stamp_opaque(stamp);
if (opaque < 4 || opaque > kMaxStampOpaque) {
continue;
}
auto cand = evaluate_candidate(state, stamp);
if (better_plan(cand, best)) {
best = cand;
}
push_seed(seeds, {bi, bj, s, opaque, std::move(stamp), cand});
}
}
}
// for (const auto& seed : seeds) {
// if (remaining_ms(timer) < kSearchMarginMs) {
// return best;
// }
// auto improved = hill_climb_plan(state, seed.stamp, timer);
// if (better_plan(improved, best)) {
// best = improved;
// }
// }
// int trials = 900;
// if (remaining < 160) trials = 600;
// if (remaining < 80) trials = 360;
// if (remaining < 40) trials = 180;
// for (int it = 0; it < trials && !time_over(timer); ++it) {
// if (remaining_ms(timer) < kSearchMarginMs) {
// break;
// }
// VV<int> stamp;
// if (!make_random_stamp(state, stamp)) {
// continue;
// }
// auto cand = hill_climb_plan(state, stamp, timer);
// if (better_plan(cand, best)) {
// best = cand;
// }
// }
return refine_best_plan(state, std::move(best), timer);
}
void apply_reverse_plan(VV<int>& state, const ReversePlan& plan) const {
if (plan.is_self_copy) {
for (Coord pos : plan.self_removed) {
state[pos.r()][pos.c()] = STAR;
}
return;
}
for (const auto& occ : plan.uses) {
const auto& rot = plan.rots[occ.r];
for (const auto& cell : rot.cells) {
state[occ.ai + cell.pos.r()][occ.aj + cell.pos.c()] = STAR;
}
}
}
Coord copy_delta(int ai, int aj, int h, int w, int r) const {
if (r == 0) return {ai, aj};
if (r == 1) return {ai, aj - (N - h)};
if (r == 2) return {ai - (N - h), aj - (N - w)};
return {ai - (N - w), aj};
}
Answer build_forward_actions(const VV<int>& base,
const V<ReversePlan>& reverse_plans) const {
Answer actions;
for (int i = 0; i < N; ++i) {
for (int j = 0; j < N; ++j) {
if (base[i][j] > 0) {
marathon::push_paint(actions, 0, i, j, base[i][j]);
}
}
}
const int aux_count = max(1, problem.k - 1);
V<V<int>> layer_state(aux_count, V<int>(N * N, 0));
V<int> layer_nonzero(aux_count, 0);
for (int idx = (int)reverse_plans.size() - 1; idx >= 0; --idx) {
const auto& plan = reverse_plans[idx];
if (plan.is_self_copy) {
marathon::push_copy(actions, 0, 0, plan.self_r, plan.self_di,
plan.self_dj);
continue;
}
const auto& blank_build = get_stamp_build_plan(plan.stamp);
V<int> target(N * N, 0);
for (int i = 0; i < plan.h; ++i) {
for (int j = 0; j < plan.w; ++j) {
if (plan.stamp[i][j] != 0) {
target[i * N + j] = plan.stamp[i][j];
}
}
}
int best_layer = 0;
int best_cost = 1 << 29;
bool best_clear = false;
V<pair<int, int>> best_changes;
for (int layer_idx = 0; layer_idx < aux_count; ++layer_idx) {
V<pair<int, int>> changes;
changes.reserve(kMaxStampOpaque * 2 + 8);
int diff_cost = 0;
for (int pos = 0; pos < N * N; ++pos) {
if (layer_state[layer_idx][pos] == target[pos]) {
continue;
}
++diff_cost;
if (diff_cost > best_cost) {
break;
}
changes.push_back({pos, target[pos]});
}
int clear_cost =
(layer_nonzero[layer_idx] > 0 ? 1 : 0) + blank_build.cost;
bool use_clear = clear_cost < diff_cost;
int cost = use_clear ? clear_cost : diff_cost;
if (cost < best_cost) {
best_cost = cost;
best_layer = layer_idx;
best_clear = use_clear;
if (use_clear) {
best_changes.clear();
} else {
best_changes = std::move(changes);
}
}
}
const int actual_layer = best_layer + 1;
if (best_clear) {
if (layer_nonzero[best_layer] > 0) {
marathon::push_clear(actions, actual_layer);
}
for (const auto& op : blank_build.ops) {
if (op.type == 0) {
marathon::push_paint(actions, actual_layer, op.i, op.j,
op.x);
} else if (op.type == 1) {
marathon::push_copy(actions, actual_layer, actual_layer,
op.r, op.i, op.j);
} else {
marathon::push_clear(actions, actual_layer);
}
}
} else {
for (const auto& [pos, color] : best_changes) {
marathon::push_paint(actions, actual_layer, pos / N, pos % N,
color);
}
}
layer_state[best_layer] = std::move(target);
layer_nonzero[best_layer] = plan.opaque;
for (int t = (int)plan.uses.size() - 1; t >= 0; --t) {
const auto& occ = plan.uses[t];
Coord delta = copy_delta(occ.ai, occ.aj, plan.h, plan.w, occ.r);
marathon::push_copy(actions, 0, actual_layer, occ.r, delta.r(),
delta.c());
}
}
return actions;
}
int answer_cost_for(const VV<int>& base,
const V<ReversePlan>& reverse_plans) const {
return (int)build_forward_actions(base, reverse_plans).size();
}
Answer solve(StopWatch& timer) {
VV<int> cur = problem.g;
V<ReversePlan> reverse_plans;
int current_cost = answer_cost_for(cur, reverse_plans);
while (!time_over(timer)) {
auto plan = find_best_reverse_plan(cur, timer);
if (!has_reverse_action(plan)) {
break;
}
VV<int> next_cur = cur;
apply_reverse_plan(next_cur, plan);
V<ReversePlan> next_reverse_plans = reverse_plans;
next_reverse_plans.push_back(plan);
int next_cost = answer_cost_for(next_cur, next_reverse_plans);
if (next_cost >= current_cost) {
break;
}
cur = std::move(next_cur);
reverse_plans = std::move(next_reverse_plans);
current_cost = next_cost;
if ((int)reverse_plans.size() > N * N) {
break;
}
}
return build_forward_actions(cur, reverse_plans);
}
};
inline Answer solve(const Problem& problem,
int available_ms) {
Answer fallback = build_fallback_actions(problem);
if (problem.k < 2 || problem.n != N) {
return fallback;
}
if (available_ms <= 0) {
return fallback;
}
Context ctx(problem);
ctx.time_budget_ms = min(available_ms, kDefaultBudgetMs);
StopWatch local_timer;
Answer candidate = ctx.solve(local_timer);
if (!marathon::is_valid_answer(problem, candidate)) {
return fallback;
}
if (marathon::better_answer(problem, candidate, fallback)) {
return candidate;
}
return fallback;
}
} // namespace sol_md_solver
#include <optional>
namespace sol0042 {
inline int smallest_power_two_period(const std::vector<int>& line) {
const int n = (int)line.size();
for (int period = 1; period <= n; ++period) {
if (n % period != 0) continue;
if (!std::has_single_bit((unsigned)(n / period))) continue;
bool ok = true;
for (int i = period; i < n; ++i) {
if (line[i] != line[i % period]) {
ok = false;
break;
}
}
if (ok) return period;
}
return n;
}
inline marathon::Answer build_repeated_row_answer(
const marathon::Problem& problem,
const std::vector<int>& row) {
const int seed_width = smallest_power_two_period(row);
marathon::Answer answer;
for (int j = 0; j < seed_width; ++j) {
if (row[j] != 0) {
marathon::push_paint(answer, 0, 0, j, row[j]);
}
}
for (int width = seed_width; width < problem.n; width *= 2) {
marathon::push_copy(answer, 0, 0, 0, 0, width);
}
for (int height = 1; height < problem.n; height *= 2) {
marathon::push_copy(answer, 0, 0, 0, height, 0);
}
return answer;
}
inline marathon::Answer build_repeated_col_answer(
const marathon::Problem& problem,
const std::vector<int>& col) {
const int seed_height = smallest_power_two_period(col);
marathon::Answer answer;
for (int i = 0; i < seed_height; ++i) {
if (col[i] != 0) {
marathon::push_paint(answer, 0, i, 0, col[i]);
}
}
for (int height = seed_height; height < problem.n; height *= 2) {
marathon::push_copy(answer, 0, 0, 0, height, 0);
}
for (int width = 1; width < problem.n; width *= 2) {
marathon::push_copy(answer, 0, 0, 0, 0, width);
}
return answer;
}
inline std::optional<marathon::Answer> solve(const marathon::Problem& problem,
int available_ms) {
if (available_ms <= 0) {
return std::nullopt;
}
if (problem.n != marathon::kBoardSize || problem.k < 1) {
return std::nullopt;
}
std::optional<marathon::Answer> best;
bool repeated_rows = true;
for (int i = 1; i < problem.n && repeated_rows; ++i) {
repeated_rows &= (problem.g[i] == problem.g[0]);
}
if (repeated_rows) {
marathon::Answer candidate =
build_repeated_row_answer(problem, problem.g[0]);
if (marathon::is_valid_answer(problem, candidate)) {
best = std::move(candidate);
}
}
bool repeated_cols = true;
std::vector<int> first_col(problem.n);
for (int i = 0; i < problem.n; ++i) {
first_col[i] = problem.g[i][0];
}
for (int j = 1; j < problem.n && repeated_cols; ++j) {
for (int i = 0; i < problem.n; ++i) {
if (problem.g[i][j] != first_col[i]) {
repeated_cols = false;
break;
}
}
}
if (repeated_cols) {
marathon::Answer candidate =
build_repeated_col_answer(problem, first_col);
if (marathon::is_valid_answer(problem, candidate) &&
(!best || marathon::better_answer(problem, candidate, *best))) {
best = std::move(candidate);
}
}
return best;
}
} // namespace sol0042
Scanner sc = Scanner(stdin);
Printer pr = Printer(stdout);
using marathon::Action;
using marathon::Answer;
using marathon::Problem;
namespace inb0001_solver {
using Grid = std::vector<std::vector<int>>;
// Detect boards built from a b x b seed, arranged as
// [rot0 rot1; rot3 rot2], then tiled over the whole board.
struct Pattern {
int board_size = 0;
int base_size = 0;
Grid base;
};
inline int count_nonzero(const Grid& grid) {
int count = 0;
for (const auto& row : grid) {
for (int color : row) {
count += (color != 0);
}
}
return count;
}
inline std::pair<int, int> rotated_source_pos(int i, int j, int size, int r) {
if (r == 0) return {i, j};
if (r == 1) return {size - 1 - j, i};
if (r == 2) return {size - 1 - i, size - 1 - j};
return {j, size - 1 - i};
}
inline int rotated_value(const Grid& base, int r, int i, int j) {
auto [ri, rj] = rotated_source_pos(i, j, (int)base.size(), r);
return base[ri][rj];
}
inline int quadrant_rotation(int i, int j, int base_size) {
const bool bottom = i >= base_size;
const bool right = j >= base_size;
if (!bottom && !right) return 0;
if (!bottom && right) return 1;
if (bottom && right) return 2;
return 3;
}
inline bool matches_pattern(const Grid& goal, const Pattern& pattern) {
const int n = pattern.board_size;
const int b = pattern.base_size;
const int period = 2 * b;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
const int pi = i % period;
const int pj = j % period;
const int r = quadrant_rotation(pi, pj, b);
const int li = pi % b;
const int lj = pj % b;
if (goal[i][j] != rotated_value(pattern.base, r, li, lj)) {
return false;
}
}
}
return true;
}
inline std::pair<int, int> copy_shift(int board_size,
int ai,
int aj,
int h,
int w,
int r) {
if (r == 0) return {ai, aj};
if (r == 1) return {ai, aj - (board_size - h)};
if (r == 2) return {ai - (board_size - h), aj - (board_size - w)};
return {ai - (board_size - w), aj};
}
inline int axis_copy_count(int board_size, int period) {
int copies = 0;
for (int filled = period; filled < board_size; filled += min(filled, board_size - filled)) {
++copies;
}
return copies;
}
inline bool append_axis_copies(marathon::Answer& actions,
int board_size,
int period,
bool vertical) {
for (int filled = period; filled < board_size;
filled += min(filled, board_size - filled)) {
const int shift = min(filled, board_size - filled);
if (shift <= 0) {
return false;
}
if (vertical) {
marathon::push_copy(actions, 0, 0, 0, shift, 0);
} else {
marathon::push_copy(actions, 0, 0, 0, 0, shift);
}
}
return true;
}
inline marathon::Answer build_actions(const Pattern& pattern) {
marathon::Answer actions;
const int n = pattern.board_size;
const int b = pattern.base_size;
const int period = 2 * b;
actions.reserve(count_nonzero(pattern.base) + 4 +
2 * axis_copy_count(n, period));
for (int i = 0; i < b; ++i) {
for (int j = 0; j < b; ++j) {
if (pattern.base[i][j] != 0) {
marathon::push_paint(actions, 1, i, j, pattern.base[i][j]);
}
}
}
for (int r = 0; r < 4; ++r) {
const int ai = (r == 2 || r == 3) ? b : 0;
const int aj = (r == 1 || r == 2) ? b : 0;
auto [di, dj] = copy_shift(n, ai, aj, b, b, r);
marathon::push_copy(actions, 0, 1, r, di, dj);
}
if (!append_axis_copies(actions, n, period, false)) {
return {};
}
if (!append_axis_copies(actions, n, period, true)) {
return {};
}
return actions;
}
inline marathon::Answer solve(const marathon::Problem& problem, int available_ms) {
if (available_ms <= 0) {
return {};
}
if (problem.k < 2 || problem.n <= 1 || (int)problem.g.size() != problem.n) {
return {};
}
for (const auto& row : problem.g) {
if ((int)row.size() != problem.n) {
return {};
}
}
if (count_nonzero(problem.g) == 0) {
return {};
}
marathon::Answer best;
int best_cost = problem.n * problem.n + 1;
for (int b = 1; 2 * b <= problem.n; ++b) {
if (problem.n % (2 * b) != 0) {
continue;
}
Pattern pattern;
pattern.board_size = problem.n;
pattern.base_size = b;
pattern.base.assign(b, std::vector<int>(b, 0));
for (int i = 0; i < b; ++i) {
for (int j = 0; j < b; ++j) {
pattern.base[i][j] = problem.g[i][j];
}
}
if (!matches_pattern(problem.g, pattern)) {
continue;
}
auto actions = build_actions(pattern);
if (actions.empty() || !marathon::replay_and_check(problem, actions)) {
continue;
}
if ((int)actions.size() < best_cost) {
best_cost = (int)actions.size();
best = std::move(actions);
}
}
return best;
}
} // namespace inb0001_solver
namespace inb0007_solver {
inline constexpr int kBoardSize = 32;
inline constexpr int STAR = -1;
inline constexpr int NEG_INF = -1'000'000'000;
inline constexpr int MAX_STAMP_SIZE = 10;
inline constexpr int LOCAL_SEED_LIMIT = 12;
inline constexpr int LOCAL_ITERS = 48;
inline constexpr int kStopGuardMs = 40;
inline constexpr int kSearchMarginMs = 20;
inline constexpr int kHillMarginMs = 15;
struct Cell {
int x = 0;
int y = 0;
int color = 0;
};
struct Occurrence {
int r = 0;
int ai = 0;
int aj = 0;
int gain = 0;
};
struct ReversePlan {
int saving = NEG_INF;
int total_gain = NEG_INF;
int size = 0;
V<Cell> cells;
V<Occurrence> uses;
};
struct SeedCandidate {
int bi = 0;
int bj = 0;
int s = 0;
int opaque = 0;
V<Cell> cells;
ReversePlan base_plan;
};
struct XorShift64 {
ull x = 1;
explicit XorShift64(ull seed) : x(seed ? seed : 1) {}
ull next() {
x ^= x << 7;
x ^= x >> 9;
return x;
}
int randint(int l, int r) {
assert(l <= r);
return l + int(next() % ull(r - l + 1));
}
};
inline int remaining_ms(StopWatch& timer, int time_budget_ms) {
return time_budget_ms - timer.msecs();
}
inline bool time_over(StopWatch& timer, int time_budget_ms) {
return remaining_ms(timer, time_budget_ms) <= 0;
}
inline pair<int, int> rotate_in_square(int x, int y, int s, int r) {
if (r == 0) return {x, y};
if (r == 1) return {y, s - 1 - x};
if (r == 2) return {s - 1 - x, s - 1 - y};
return {s - 1 - y, x};
}
inline pair<int, int> rotate_in_full(int x, int y, int n, int r) {
if (r == 0) return {x, y};
if (r == 1) return {y, n - 1 - x};
if (r == 2) return {n - 1 - x, n - 1 - y};
return {n - 1 - y, x};
}
inline string canonical_key(const VV<int>& cur, int bi, int bj, int s) {
V<string> keys;
keys.reserve(4);
for (int r = 0; r < 4; ++r) {
string key;
key.reserve(s * s + 8);
key += char('0' + min(s, 9));
key += ':';
for (int x = 0; x < s; ++x) {
for (int y = 0; y < s; ++y) {
auto [rx, ry] = rotate_in_square(x, y, s, r);
int color = cur[bi + rx][bj + ry];
if (color == STAR) {
key += '*';
} else {
key += char('0' + color);
}
}
}
keys.push_back(key);
}
return *ranges::min_element(keys);
}
inline bool better_plan(const ReversePlan& lhs, const ReversePlan& rhs) {
if (lhs.saving != rhs.saving) return lhs.saving > rhs.saving;
if (lhs.total_gain != rhs.total_gain) {
return lhs.total_gain > rhs.total_gain;
}
if (lhs.cells.size() != rhs.cells.size()) {
return lhs.cells.size() < rhs.cells.size();
}
return lhs.size < rhs.size;
}
inline bool better_seed(const SeedCandidate& lhs, const SeedCandidate& rhs) {
if (lhs.base_plan.saving != rhs.base_plan.saving) {
return lhs.base_plan.saving > rhs.base_plan.saving;
}
if (lhs.base_plan.total_gain != rhs.base_plan.total_gain) {
return lhs.base_plan.total_gain > rhs.base_plan.total_gain;
}
if (lhs.opaque != rhs.opaque) return lhs.opaque > rhs.opaque;
return lhs.s < rhs.s;
}
inline V<Cell> collect_cells_in_square(const VV<int>& cur,
int bi,
int bj,
int s) {
V<Cell> cells;
for (int x = 0; x < s; ++x) {
for (int y = 0; y < s; ++y) {
int color = cur[bi + x][bj + y];
if (color > 0) {
cells.push_back({x, y, color});
}
}
}
return cells;
}
inline pair<V<Cell>, int> normalize_cells(const V<Cell>& raw_cells) {
if (raw_cells.empty()) {
return {{}, 0};
}
int min_x = MAX_STAMP_SIZE;
int min_y = MAX_STAMP_SIZE;
int max_x = -1;
int max_y = -1;
for (const auto& cell : raw_cells) {
min_x = min(min_x, cell.x);
min_y = min(min_y, cell.y);
max_x = max(max_x, cell.x);
max_y = max(max_y, cell.y);
}
int h = max_x - min_x + 1;
int w = max_y - min_y + 1;
int s = max(h, w);
V<Cell> cells;
cells.reserve(raw_cells.size());
for (const auto& cell : raw_cells) {
cells.push_back({cell.x - min_x, cell.y - min_y, cell.color});
}
sort(cells, [](const Cell& a, const Cell& b) {
if (a.x != b.x) return a.x < b.x;
if (a.y != b.y) return a.y < b.y;
return a.color < b.color;
});
cells.erase(ranges::unique(cells, [](const Cell& a, const Cell& b) {
return a.x == b.x && a.y == b.y && a.color == b.color;
}).begin(),
cells.end());
return {cells, s};
}
inline VV<int> cells_to_stamp(const V<Cell>& cells, int s) {
VV<int> stamp(s, V<int>(s, 0));
for (const auto& cell : cells) {
stamp[cell.x][cell.y] = cell.color;
}
return stamp;
}
inline V<Cell> stamp_to_cells(const VV<int>& stamp) {
int s = (int)stamp.size();
V<Cell> cells;
for (int x = 0; x < s; ++x) {
for (int y = 0; y < s; ++y) {
if (stamp[x][y] > 0) {
cells.push_back({x, y, stamp[x][y]});
}
}
}
return cells;
}
inline int current_reverse_gain(const V<Cell>& cells,
int s,
int r,
int ai,
int aj,
const VV<int>& cur) {
int gain = 0;
for (const auto& cell : cells) {
auto [rx, ry] = rotate_in_square(cell.x, cell.y, s, r);
if (cur[ai + rx][aj + ry] == cell.color) {
++gain;
}
}
return gain;
}
inline V<Occurrence> select_occurrences_reverse_greedily(const V<Cell>& cells,
int s,
const VV<int>& cur,
StopWatch& timer,
int time_budget_ms) {
const int n = (int)cur.size();
V<Occurrence> candidates;
int probe = 0;
for (int r = 0; r < 4; ++r) {
for (int ai = 0; ai + s <= n; ++ai) {
for (int aj = 0; aj + s <= n; ++aj) {
if (((probe++) & 63) == 0 && time_over(timer, time_budget_ms)) {
return {};
}
bool ok = true;
int gain = 0;
for (const auto& cell : cells) {
auto [rx, ry] = rotate_in_square(cell.x, cell.y, s, r);
int v = cur[ai + rx][aj + ry];
if (v != STAR && v != cell.color) {
ok = false;
break;
}
if (v == cell.color) {
++gain;
}
}
if (ok && gain >= 2) {
candidates.push_back({r, ai, aj, gain});
}
}
}
}
VV<int> temp = cur;
V<Occurrence> chosen;
V<char> used(candidates.size(), 0);
while (true) {
if (time_over(timer, time_budget_ms)) {
return chosen;
}
int best_idx = -1;
int best_gain = 0;
for (int idx = 0; idx < (int)candidates.size(); ++idx) {
if ((idx & 255) == 0 && time_over(timer, time_budget_ms)) {
return chosen;
}
if (used[idx]) continue;
int gain = current_reverse_gain(cells, s, candidates[idx].r,
candidates[idx].ai,
candidates[idx].aj, temp);
if (gain > best_gain) {
best_gain = gain;
best_idx = idx;
}
}
if (best_idx == -1 || best_gain < 2) {
break;
}
used[best_idx] = 1;
auto occ = candidates[best_idx];
occ.gain = best_gain;
chosen.push_back(occ);
for (const auto& cell : cells) {
auto [rx, ry] = rotate_in_square(cell.x, cell.y, s, occ.r);
int& v = temp[occ.ai + rx][occ.aj + ry];
if (v == cell.color) {
v = STAR;
}
}
}
return chosen;
}
inline ReversePlan evaluate_stamp_reverse(const V<Cell>& cells,
int s,
const VV<int>& cur,
bool need_clear,
StopWatch& timer,
int time_budget_ms) {
ReversePlan plan;
if ((int)cells.size() < 4) {
plan.size = s;
plan.cells = cells;
return plan;
}
auto uses =
select_occurrences_reverse_greedily(cells, s, cur, timer, time_budget_ms);
int total_gain = 0;
for (const auto& occ : uses) {
total_gain += occ.gain;
}
int setup_cost =
(int)cells.size() + (int)uses.size() + (need_clear ? 1 : 0);
plan.saving = total_gain - setup_cost;
plan.total_gain = total_gain;
plan.size = s;
plan.cells = cells;
plan.uses = std::move(uses);
return plan;
}
inline ReversePlan evaluate_normalized_stamp(const VV<int>& stamp,
const VV<int>& cur,
bool need_clear,
StopWatch& timer,
int time_budget_ms) {
auto cells = stamp_to_cells(stamp);
auto [normalized_cells, s] = normalize_cells(cells);
return evaluate_stamp_reverse(normalized_cells, s, cur, need_clear, timer,
time_budget_ms);
}
inline VV<int> normalize_stamp(const VV<int>& stamp) {
auto cells = stamp_to_cells(stamp);
auto [normalized_cells, s] = normalize_cells(cells);
return cells_to_stamp(normalized_cells, s);
}
inline VV<int> mutate_stamp(const VV<int>& stamp,
XorShift64& rng,
int color_count) {
VV<int> next = stamp;
int s = (int)next.size();
V<pair<int, int>> filled;
V<pair<int, int>> empty;
for (int x = 0; x < s; ++x) {
for (int y = 0; y < s; ++y) {
if (next[x][y] > 0) {
filled.push_back({x, y});
} else {
empty.push_back({x, y});
}
}
}
int op = rng.randint(0, 7);
if (op <= 2 && !filled.empty()) {
auto [x, y] = filled[rng.randint(0, (int)filled.size() - 1)];
next[x][y] = 0;
return normalize_stamp(next);
}
if (op == 3 && !filled.empty()) {
auto [x, y] = filled[rng.randint(0, (int)filled.size() - 1)];
int color = next[x][y];
if (color_count >= 2) {
int new_color = rng.randint(1, color_count - 1);
if (new_color >= color) ++new_color;
next[x][y] = new_color;
}
return normalize_stamp(next);
}
if (op == 4 && !filled.empty() && !empty.empty()) {
auto [fx, fy] = filled[rng.randint(0, (int)filled.size() - 1)];
int color = next[fx][fy];
next[fx][fy] = 0;
auto [tx, ty] = empty[rng.randint(0, (int)empty.size() - 1)];
next[tx][ty] = color;
return normalize_stamp(next);
}
if (op == 5 && !empty.empty()) {
auto [x, y] = empty[rng.randint(0, (int)empty.size() - 1)];
next[x][y] = rng.randint(1, color_count);
return normalize_stamp(next);
}
if (op >= 6 && s < MAX_STAMP_SIZE) {
VV<int> bigger(s + 1, V<int>(s + 1, 0));
int ox = rng.randint(0, 1);
int oy = rng.randint(0, 1);
for (int x = 0; x < s; ++x) {
for (int y = 0; y < s; ++y) {
bigger[x + ox][y + oy] = next[x][y];
}
}
V<pair<int, int>> bigger_empty;
for (int x = 0; x <= s; ++x) {
for (int y = 0; y <= s; ++y) {
if (bigger[x][y] == 0) {
bigger_empty.push_back({x, y});
}
}
}
if (!bigger_empty.empty()) {
auto [x, y] =
bigger_empty[rng.randint(0, (int)bigger_empty.size() - 1)];
bigger[x][y] = rng.randint(1, color_count);
}
return normalize_stamp(bigger);
}
return normalize_stamp(next);
}
inline ReversePlan hill_climb_stamp(VV<int> stamp,
const VV<int>& cur,
bool need_clear,
int color_count,
XorShift64& rng,
StopWatch& timer,
int time_budget_ms) {
stamp = normalize_stamp(stamp);
ReversePlan current =
evaluate_normalized_stamp(stamp, cur, need_clear, timer, time_budget_ms);
ReversePlan best = current;
int stalled = 0;
for (int iter = 0; iter < LOCAL_ITERS; ++iter) {
if (remaining_ms(timer, time_budget_ms) < kHillMarginMs) {
break;
}
auto next_stamp = mutate_stamp(stamp, rng, color_count);
ReversePlan next = evaluate_normalized_stamp(next_stamp, cur, need_clear,
timer, time_budget_ms);
if (better_plan(next, current)) {
current = next;
stamp = std::move(next_stamp);
stalled = 0;
if (better_plan(current, best)) {
best = current;
}
continue;
}
++stalled;
if (stalled >= 12) {
break;
}
}
return best;
}
inline void push_seed(V<SeedCandidate>& seeds, SeedCandidate seed) {
seeds.push_back(std::move(seed));
sort(seeds, better_seed);
if ((int)seeds.size() > LOCAL_SEED_LIMIT) {
seeds.resize(LOCAL_SEED_LIMIT);
}
}
inline ReversePlan find_best_reverse_plan(const VV<int>& cur,
bool need_clear,
int color_count,
StopWatch& timer,
int time_budget_ms) {
const int n = (int)cur.size();
int remaining = 0;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
remaining += (cur[i][j] > 0);
}
}
if (remaining < 4) {
return {};
}
ReversePlan best;
V<SeedCandidate> seeds;
const V<int> sizes = {2, 3, 4, 5, 6, 7, 8, 9, 10};
int probe = 0;
for (int s : sizes) {
if (remaining_ms(timer, time_budget_ms) < kSearchMarginMs) {
return best;
}
std::unordered_set<string> seen;
for (int bi = 0; bi + s <= n; ++bi) {
for (int bj = 0; bj + s <= n; ++bj) {
if (((probe++) & 63) == 0 &&
remaining_ms(timer, time_budget_ms) < kSearchMarginMs) {
return best;
}
string key = canonical_key(cur, bi, bj, s);
if (!seen.insert(key).second) {
continue;
}
auto cells = collect_cells_in_square(cur, bi, bj, s);
auto [normalized_cells, normalized_s] = normalize_cells(cells);
auto plan = evaluate_stamp_reverse(normalized_cells,
normalized_s, cur,
need_clear, timer,
time_budget_ms);
if (better_plan(plan, best)) {
best = plan;
}
push_seed(seeds,
{bi, bj, s, (int)cells.size(), std::move(cells), plan});
}
}
}
ull seed = 1469598103934665603ULL;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
seed ^= ull(cur[i][j] + 7);
seed *= 1099511628211ULL;
}
}
XorShift64 rng(seed ^ ull(need_clear ? 1 : 0));
for (const auto& seed_candidate : seeds) {
if (remaining_ms(timer, time_budget_ms) < kSearchMarginMs) {
return best;
}
V<pair<int, int>> starts = {
{seed_candidate.bi, seed_candidate.bj},
{seed_candidate.bi - 1, seed_candidate.bj},
{seed_candidate.bi + 1, seed_candidate.bj},
{seed_candidate.bi, seed_candidate.bj - 1},
{seed_candidate.bi, seed_candidate.bj + 1},
};
for (const auto& [bi, bj] : starts) {
if (bi < 0 || bj < 0 || bi + seed_candidate.s > n ||
bj + seed_candidate.s > n) {
continue;
}
auto cells = collect_cells_in_square(cur, bi, bj, seed_candidate.s);
auto [normalized_cells, normalized_s] = normalize_cells(cells);
auto stamp = cells_to_stamp(normalized_cells, normalized_s);
auto improved = hill_climb_stamp(stamp, cur, need_clear, color_count,
rng, timer, time_budget_ms);
if (better_plan(improved, best)) {
best = std::move(improved);
}
}
}
return best;
}
inline void apply_reverse_plan(VV<int>& cur, const ReversePlan& plan) {
for (const auto& occ : plan.uses) {
for (const auto& cell : plan.cells) {
auto [rx, ry] = rotate_in_square(cell.x, cell.y, plan.size, occ.r);
int& v = cur[occ.ai + rx][occ.aj + ry];
if (v == cell.color) {
v = STAR;
}
}
}
}
inline Answer build_forward_actions(const VV<int>& base,
const V<ReversePlan>& reverse_plans) {
const int n = (int)base.size();
Answer actions;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
if (base[i][j] > 0) {
marathon::push_paint(actions, 0, i, j, base[i][j]);
}
}
}
bool aux_initialized = false;
for (int idx = (int)reverse_plans.size() - 1; idx >= 0; --idx) {
const auto& plan = reverse_plans[idx];
if (aux_initialized) {
marathon::push_clear(actions, 1);
}
aux_initialized = true;
for (const auto& cell : plan.cells) {
marathon::push_paint(actions, 1, cell.x, cell.y, cell.color);
}
int shift = n - plan.size;
for (int t = (int)plan.uses.size() - 1; t >= 0; --t) {
const auto& occ = plan.uses[t];
int di = occ.ai;
int dj = occ.aj;
if (occ.r == 1) {
dj -= shift;
} else if (occ.r == 2) {
di -= shift;
dj -= shift;
} else if (occ.r == 3) {
di -= shift;
}
marathon::push_copy(actions, 0, 1, occ.r, di, dj);
}
}
return actions;
}
inline Answer build_fallback_actions(const Problem& problem) {
Answer actions;
for (int i = 0; i < problem.n; ++i) {
for (int j = 0; j < problem.n; ++j) {
if (problem.g[i][j] != 0) {
marathon::push_paint(actions, 0, i, j, problem.g[i][j]);
}
}
}
return actions;
}
inline bool looks_like_0007_family(const Problem& problem) {
if (problem.n != kBoardSize || problem.k < 2 || problem.c != 4) {
return false;
}
std::unordered_map<string, int> freq;
int best = 0;
std::set<string> block_keys;
for (int bi = 0; bi + 4 <= problem.n; ++bi) {
for (int bj = 0; bj + 4 <= problem.n; ++bj) {
string key = canonical_key(problem.g, bi, bj, 4);
int now = ++freq[key];
best = max(best, now);
}
}
for (int bi = 0; bi < problem.n; bi += 4) {
for (int bj = 0; bj < problem.n; bj += 4) {
block_keys.insert(canonical_key(problem.g, bi, bj, 4));
}
}
return best >= 20 && (int)block_keys.size() >= 20;
}
inline Answer solve(const Problem& problem, int available_ms) {
if (!looks_like_0007_family(problem)) {
return {};
}
int time_budget_ms = available_ms - kStopGuardMs;
if (time_budget_ms <= 0) {
return {};
}
StopWatch timer;
VV<int> cur = problem.g;
V<ReversePlan> reverse_plans;
while (!time_over(timer, time_budget_ms)) {
auto plan = find_best_reverse_plan(cur, !reverse_plans.empty(), problem.c,
timer, time_budget_ms);
if (plan.saving <= 0) {
break;
}
reverse_plans.push_back(plan);
apply_reverse_plan(cur, plan);
if ((int)reverse_plans.size() > problem.n * problem.n) {
break;
}
}
if (reverse_plans.empty()) {
return {};
}
auto actions = build_forward_actions(cur, reverse_plans);
auto fallback = build_fallback_actions(problem);
if (!marathon::replay_and_check(problem, actions) ||
(int)actions.size() >= (int)fallback.size()) {
return {};
}
return actions;
}
} // namespace inb0007_solver
namespace inb0016_solver {
inline constexpr int kBoardSize = 32;
inline constexpr int kAuxLayer = 1;
struct PatternCell {
int i = 0;
int j = 0;
int color = 0;
};
struct Pattern {
int h = 0;
int w = 0;
V<PatternCell> cells;
};
struct Occurrence {
int pattern_id = 0;
int r = 0;
int ai = 0;
int aj = 0;
V<Coord> cells;
};
struct SolvePlan {
int cost = 1 << 29;
int covered = 0;
int leftover = 0;
int used_mask = 0;
array<V<Occurrence>, 2> picks;
};
inline Coord rotate_in_rect(Coord pos, int h, int w, int r) {
if (r == 0) return pos;
if (r == 1) return {pos.c(), h - 1 - pos.r()};
if (r == 2) return {h - 1 - pos.r(), w - 1 - pos.c()};
return {w - 1 - pos.c(), pos.r()};
}
inline pair<int, int> copy_shift(int ai, int aj, int h, int w, int r) {
if (r == 0) return {ai, aj};
if (r == 1) return {ai, aj - (kBoardSize - h)};
if (r == 2) return {ai - (kBoardSize - h), aj - (kBoardSize - w)};
return {ai - (kBoardSize - w), aj};
}
inline V<Pattern> patterns() {
V<Pattern> ps(2);
ps[0].h = 2;
ps[0].w = 4;
ps[0].cells = {
{0, 0, 1}, {0, 1, 2}, {0, 2, 4}, {0, 3, 3},
{1, 0, 3}, {1, 1, 4}, {1, 2, 2},
};
ps[1].h = 2;
ps[1].w = 6;
ps[1].cells = {
{0, 0, 4}, {0, 1, 3}, {0, 2, 1}, {0, 3, 2}, {0, 4, 4}, {0, 5, 3},
{1, 0, 2}, {1, 1, 1}, {1, 2, 3}, {1, 3, 4}, {1, 4, 2}, {1, 5, 1},
};
return ps;
}
inline V<Occurrence> find_occurrences(const VV<int>& goal, const V<Pattern>& ps) {
V<Occurrence> occs;
for (int pid = 0; pid < (int)ps.size(); ++pid) {
const auto& pat = ps[pid];
for (int r = 0; r < 4; ++r) {
const int nh = (r & 1) ? pat.w : pat.h;
const int nw = (r & 1) ? pat.h : pat.w;
V<PatternCell> rotated;
rotated.reserve(pat.cells.size());
for (const auto& cell : pat.cells) {
Coord pos = rotate_in_rect({cell.i, cell.j}, pat.h, pat.w, r);
rotated.push_back({pos.r(), pos.c(), cell.color});
}
for (int ai = 0; ai + nh <= kBoardSize; ++ai) {
for (int aj = 0; aj + nw <= kBoardSize; ++aj) {
V<Coord> cells;
cells.reserve(rotated.size());
bool ok = true;
for (const auto& cell : rotated) {
if (goal[ai + cell.i][aj + cell.j] != cell.color) {
ok = false;
break;
}
cells.push_back({ai + cell.i, aj + cell.j});
}
if (ok) {
occs.push_back({pid, r, ai, aj, std::move(cells)});
}
}
}
}
}
return occs;
}
inline int count_goal_nonzero(const VV<int>& goal) {
int count = 0;
for (const auto& row : goal) {
for (int color : row) {
count += (color != 0);
}
}
return count;
}
inline SolvePlan build_plan(const VV<int>& goal,
const V<Pattern>& ps,
const V<Occurrence>& occs,
int mask) {
SolvePlan plan;
plan.leftover = count_goal_nonzero(goal);
VV<char> covered(kBoardSize, V<char>(kBoardSize, 0));
V<char> used(occs.size(), 0);
while (true) {
int best_idx = -1;
int best_gain = 0;
int best_size = -1;
for (int idx = 0; idx < (int)occs.size(); ++idx) {
if (used[idx]) continue;
const auto& occ = occs[idx];
if (((mask >> occ.pattern_id) & 1) == 0) continue;
int gain = 0;
for (Coord pos : occ.cells) {
gain += !covered[pos.r()][pos.c()];
}
int size = (int)occ.cells.size();
if (gain > best_gain || (gain == best_gain && size > best_size)) {
best_gain = gain;
best_size = size;
best_idx = idx;
}
}
if (best_idx == -1 || best_gain <= 1) {
break;
}
used[best_idx] = 1;
const auto& occ = occs[best_idx];
plan.picks[occ.pattern_id].push_back(occ);
for (Coord pos : occ.cells) {
if (!covered[pos.r()][pos.c()]) {
covered[pos.r()][pos.c()] = 1;
++plan.covered;
}
}
}
plan.used_mask = 0;
for (int pid = 0; pid < (int)ps.size(); ++pid) {
if (!plan.picks[pid].empty()) {
plan.used_mask |= 1 << pid;
}
}
if (plan.used_mask == 0) {
plan.cost = count_goal_nonzero(goal);
return plan;
}
const int setup_cost =
(int)ps[0].cells.size() * !plan.picks[0].empty() +
(int)ps[1].cells.size() * !plan.picks[1].empty() +
max(0, std::popcount((unsigned)plan.used_mask) - 1);
const int copy_cost =
(int)plan.picks[0].size() + (int)plan.picks[1].size();
plan.leftover = count_goal_nonzero(goal) - plan.covered;
plan.cost = setup_cost + copy_cost + plan.leftover;
return plan;
}
inline Answer build_answer(const Problem& problem,
const V<Pattern>& ps,
const SolvePlan& plan) {
Answer actions;
VV<char> covered(kBoardSize, V<char>(kBoardSize, 0));
bool initialized = false;
for (int pid = 0; pid < (int)ps.size(); ++pid) {
if (plan.picks[pid].empty()) {
continue;
}
if (initialized) {
marathon::push_clear(actions, kAuxLayer);
}
initialized = true;
const auto& pat = ps[pid];
for (const auto& cell : pat.cells) {
marathon::push_paint(actions, kAuxLayer, cell.i, cell.j, cell.color);
}
for (const auto& occ : plan.picks[pid]) {
auto [di, dj] = copy_shift(occ.ai, occ.aj, pat.h, pat.w, occ.r);
marathon::push_copy(actions, 0, kAuxLayer, occ.r, di, dj);
for (Coord pos : occ.cells) {
covered[pos.r()][pos.c()] = 1;
}
}
}
for (int i = 0; i < kBoardSize; ++i) {
for (int j = 0; j < kBoardSize; ++j) {
if (problem.g[i][j] != 0 && !covered[i][j]) {
marathon::push_paint(actions, 0, i, j, problem.g[i][j]);
}
}
}
return actions;
}
inline Answer solve(const Problem& problem) {
if (problem.n != kBoardSize || problem.k < 2 || problem.c != 4) {
return {};
}
const auto ps = patterns();
const auto occs = find_occurrences(problem.g, ps);
const int goal_nonzero = count_goal_nonzero(problem.g);
SolvePlan best;
best.cost = goal_nonzero;
best.leftover = goal_nonzero;
for (int mask = 1; mask < (1 << (int)ps.size()); ++mask) {
auto plan = build_plan(problem.g, ps, occs, mask);
if (plan.cost < best.cost) {
best = std::move(plan);
}
}
if (best.used_mask == 0) {
return {};
}
if (best.covered * 100 < goal_nonzero * 90) {
return {};
}
auto actions = build_answer(problem, ps, best);
if ((int)actions.size() >= goal_nonzero) {
return {};
}
if (!marathon::replay_and_check(problem, actions)) {
return {};
}
return actions;
}
} // namespace inb0016_solver
namespace inb0018_solver {
inline constexpr int kBoardSize = 32;
inline constexpr int kBlockSize = 8;
inline constexpr int kRemoved = -1;
struct Block {
int color = 0;
int i = 0;
int j = 0;
};
struct Decomposition {
bool ok = false;
V<Block> reverse_blocks;
};
inline Action make_paint(int layer, int i, int j, int color) {
Action action;
action.type = 0;
action.k = layer;
action.i = i;
action.j = j;
action.x = color;
return action;
}
inline Action make_copy(int dst, int src, int r, int di, int dj) {
Action action;
action.type = 1;
action.k = dst;
action.h = src;
action.r = r;
action.i = di;
action.j = dj;
return action;
}
inline Action make_clear(int layer) {
Action action;
action.type = 2;
action.k = layer;
return action;
}
inline void fill_whole_board(Answer& actions, int color) {
if (color == 0) {
return;
}
actions.push_back(make_paint(0, 0, 0, color));
for (int d : {1, 2, 4, 8, 16}) {
actions.push_back(make_copy(0, 0, 0, 0, d));
}
for (int d : {1, 2, 4, 8, 16}) {
actions.push_back(make_copy(0, 0, 0, d, 0));
}
}
inline void stamp_block(Answer& actions, const Block& block, bool need_clear) {
if (need_clear) {
actions.push_back(make_clear(1));
}
actions.push_back(make_paint(1, block.i, block.j, block.color));
for (int d : {1, 2, 4}) {
actions.push_back(make_copy(1, 1, 0, 0, d));
}
for (int d : {1, 2, 4}) {
actions.push_back(make_copy(1, 1, 0, d, 0));
}
actions.push_back(make_copy(0, 1, 0, 0, 0));
}
inline int count_non_background(const VV<int>& goal, int background) {
int count = 0;
for (const auto& row : goal) {
for (int color : row) {
count += (color != background);
}
}
return count;
}
inline int estimate_action_count(int background, int num_blocks) {
int count = (background == 0 ? 0 : 11);
if (num_blocks == 0) {
return count;
}
count += 8 * num_blocks;
count += num_blocks - 1;
return count;
}
inline Decomposition decompose(const VV<int>& goal, int background) {
Decomposition res;
VV<int> cur = goal;
int remaining = count_non_background(cur, background);
while (remaining > 0) {
int best_visible = 0;
Block best;
for (int i = 0; i + kBlockSize <= kBoardSize; ++i) {
for (int j = 0; j + kBlockSize <= kBoardSize; ++j) {
int color = -1;
int visible = 0;
bool ok = true;
for (int di = 0; di < kBlockSize && ok; ++di) {
for (int dj = 0; dj < kBlockSize; ++dj) {
int v = cur[i + di][j + dj];
if (v == background) {
ok = false;
break;
}
if (v == kRemoved) {
continue;
}
if (color == -1) {
color = v;
} else if (color != v) {
ok = false;
break;
}
++visible;
}
}
if (!ok || visible == 0) {
continue;
}
if (visible > best_visible ||
(visible == best_visible &&
(i < best.i || (i == best.i && j < best.j)))) {
best_visible = visible;
best = {color, i, j};
}
}
}
if (best_visible == 0) {
return res;
}
res.reverse_blocks.push_back(best);
for (int di = 0; di < kBlockSize; ++di) {
for (int dj = 0; dj < kBlockSize; ++dj) {
int& v = cur[best.i + di][best.j + dj];
if (v != kRemoved) {
remaining -= (v != background);
v = kRemoved;
}
}
}
}
res.ok = true;
return res;
}
inline Answer build_actions(int background, const V<Block>& reverse_blocks) {
Answer actions;
actions.reserve(estimate_action_count(background, (int)reverse_blocks.size()));
fill_whole_board(actions, background);
bool need_clear = false;
for (int idx = (int)reverse_blocks.size() - 1; idx >= 0; --idx) {
stamp_block(actions, reverse_blocks[idx], need_clear);
need_clear = true;
}
return actions;
}
inline Answer solve(const VV<int>& goal, int k, int c, int available_ms) {
if (available_ms <= 0) {
return {};
}
if (k < 2 || (int)goal.size() != kBoardSize) {
return {};
}
for (const auto& row : goal) {
if ((int)row.size() != kBoardSize) {
return {};
}
}
Answer best;
int best_cost = 1 << 29;
for (int background = 0; background <= c; ++background) {
auto dec = decompose(goal, background);
if (!dec.ok) {
continue;
}
int estimated = estimate_action_count(background,
(int)dec.reverse_blocks.size());
if (estimated > kBoardSize * kBoardSize) {
continue;
}
auto actions = build_actions(background, dec.reverse_blocks);
if ((int)actions.size() < best_cost) {
best_cost = (int)actions.size();
best = std::move(actions);
}
}
return best;
}
} // namespace inb0018_solver
namespace inb0020_solver {
inline constexpr int kBoardSize = 32;
inline constexpr int kSeedSize = 2;
inline constexpr int kHalfSize = 16;
inline constexpr int kInvalidCost = 1 << 29;
inline pair<int, int> source_parity(int x, int y, int r) {
if (r == 0) return {x, y};
if (r == 1) return {1 - y, x};
if (r == 2) return {1 - x, 1 - y};
return {y, 1 - x};
}
inline int quadrant_rotation(int i, int j) {
if (i < kHalfSize && j < kHalfSize) return 0;
if (i < kHalfSize && j >= kHalfSize) return 1;
if (i >= kHalfSize && j >= kHalfSize) return 2;
return 3;
}
inline int pattern_color(const array<int, 4>& seed, int i, int j) {
const int r = quadrant_rotation(i, j);
auto [si, sj] = source_parity(i & 1, j & 1, r);
return seed[si * kSeedSize + sj];
}
inline int seed_paint_count(const array<int, 4>& seed) {
int count = 0;
for (int color : seed) {
count += (color != 0);
}
return count;
}
inline int mismatch_count(const Problem& problem, const array<int, 4>& seed) {
int count = 0;
for (int i = 0; i < problem.n; ++i) {
for (int j = 0; j < problem.n; ++j) {
count += (problem.g[i][j] != pattern_color(seed, i, j));
}
}
return count;
}
inline Answer build_actions(const Problem& problem, const array<int, 4>& seed) {
Answer actions;
const int base_paints = seed_paint_count(seed);
const int mismatches = mismatch_count(problem, seed);
if (base_paints == 0 && mismatches == 0) {
return actions;
}
actions.reserve(base_paints + mismatches + (base_paints ? 8 : 0));
for (int i = 0; i < kSeedSize; ++i) {
for (int j = 0; j < kSeedSize; ++j) {
int color = seed[i * kSeedSize + j];
if (color != 0) {
marathon::push_paint(actions, 0, i, j, color);
}
}
}
if (base_paints > 0) {
for (int d : {2, 4, 8}) {
marathon::push_copy(actions, 0, 0, 0, 0, d);
}
for (int d : {2, 4, 8}) {
marathon::push_copy(actions, 0, 0, 0, d, 0);
}
marathon::push_copy(actions, 0, 0, 1, 0, 0);
marathon::push_copy(actions, 0, 0, 2, 0, 0);
}
for (int i = 0; i < problem.n; ++i) {
for (int j = 0; j < problem.n; ++j) {
if (problem.g[i][j] != pattern_color(seed, i, j)) {
marathon::push_paint(actions, 0, i, j, problem.g[i][j]);
}
}
}
return actions;
}
inline int estimated_cost(const Problem& problem, const array<int, 4>& seed) {
const int base_paints = seed_paint_count(seed);
int cost = mismatch_count(problem, seed) + base_paints;
if (base_paints > 0) {
cost += 8;
}
return cost;
}
inline Answer solve(const Problem& problem, int available_ms) {
if (available_ms <= 0) {
return {};
}
if (problem.n != kBoardSize || problem.k < 1) {
return {};
}
Answer best;
int best_cost = kInvalidCost;
array<int, 4> seed{};
for (int a = 0; a <= problem.c; ++a) {
seed[0] = a;
for (int b = 0; b <= problem.c; ++b) {
seed[1] = b;
for (int c = 0; c <= problem.c; ++c) {
seed[2] = c;
for (int d = 0; d <= problem.c; ++d) {
seed[3] = d;
int cost = estimated_cost(problem, seed);
if (cost >= best_cost || cost > problem.n * problem.n) {
continue;
}
auto actions = build_actions(problem, seed);
if (!marathon::is_valid_answer(problem, actions)) {
continue;
}
best_cost = cost;
best = std::move(actions);
}
}
}
}
return best;
}
} // namespace inb0020_solver
namespace inb0045_solver {
constexpr int STAR = -1;
constexpr int NEG_INF = -1'000'000'000;
constexpr int MAX_STAMP_SIZE = 10;
constexpr int LOCAL_SEED_LIMIT = 12;
constexpr int LOCAL_ITERS = 48;
constexpr int kStopGuardMs = 40;
constexpr int kSearchMarginMs = 20;
constexpr int kHillMarginMs = 15;
struct Cell {
int x = 0;
int y = 0;
int color = 0;
};
struct Occurrence {
int r = 0;
int ai = 0;
int aj = 0;
int gain = 0;
};
struct ReversePlan {
int saving = NEG_INF;
int total_gain = NEG_INF;
int size = 0;
V<Cell> cells;
V<Occurrence> uses;
};
struct SeedCandidate {
int bi = 0;
int bj = 0;
int s = 0;
int opaque = 0;
V<Cell> cells;
ReversePlan base_plan;
};
struct XorShift64 {
ull x;
explicit XorShift64(ull seed) : x(seed ? seed : 1) {}
ull next() {
x ^= x << 7;
x ^= x >> 9;
return x;
}
int randint(int l, int r) {
assert(l <= r);
return l + int(next() % ull(r - l + 1));
}
};
inline int remaining_ms(StopWatch& timer, int time_budget_ms) {
return time_budget_ms - timer.msecs();
}
inline bool time_over(StopWatch& timer, int time_budget_ms) {
return remaining_ms(timer, time_budget_ms) <= 0;
}
inline pair<int, int> rotate_in_square(int x, int y, int s, int r) {
if (r == 0) return {x, y};
if (r == 1) return {y, s - 1 - x};
if (r == 2) return {s - 1 - x, s - 1 - y};
return {s - 1 - y, x};
}
inline string canonical_key(const VV<int>& cur, int bi, int bj, int s) {
V<string> keys;
keys.reserve(4);
for (int r = 0; r < 4; ++r) {
string key;
key.reserve(s * s + 8);
key += char('0' + min(s, 9));
key += ':';
for (int x = 0; x < s; ++x) {
for (int y = 0; y < s; ++y) {
auto [rx, ry] = rotate_in_square(x, y, s, r);
int color = cur[bi + rx][bj + ry];
if (color == STAR) {
key += '*';
} else {
key += char('0' + color);
}
}
}
keys.push_back(key);
}
return *ranges::min_element(keys);
}
inline bool better_plan(const ReversePlan& lhs, const ReversePlan& rhs) {
if (lhs.saving != rhs.saving) return lhs.saving > rhs.saving;
if (lhs.total_gain != rhs.total_gain) return lhs.total_gain > rhs.total_gain;
if (lhs.cells.size() != rhs.cells.size()) {
return lhs.cells.size() < rhs.cells.size();
}
return lhs.size < rhs.size;
}
inline bool better_seed(const SeedCandidate& lhs, const SeedCandidate& rhs) {
if (lhs.base_plan.saving != rhs.base_plan.saving) {
return lhs.base_plan.saving > rhs.base_plan.saving;
}
if (lhs.base_plan.total_gain != rhs.base_plan.total_gain) {
return lhs.base_plan.total_gain > rhs.base_plan.total_gain;
}
if (lhs.opaque != rhs.opaque) return lhs.opaque > rhs.opaque;
return lhs.s < rhs.s;
}
inline V<Cell> collect_cells_in_square(const VV<int>& cur, int bi, int bj, int s) {
V<Cell> cells;
for (int x = 0; x < s; ++x) {
for (int y = 0; y < s; ++y) {
int color = cur[bi + x][bj + y];
if (color > 0) {
cells.push_back({x, y, color});
}
}
}
return cells;
}
inline pair<V<Cell>, int> normalize_cells(const V<Cell>& raw_cells) {
if (raw_cells.empty()) {
return {{}, 0};
}
int min_x = MAX_STAMP_SIZE;
int min_y = MAX_STAMP_SIZE;
int max_x = -1;
int max_y = -1;
for (const auto& cell : raw_cells) {
min_x = min(min_x, cell.x);
min_y = min(min_y, cell.y);
max_x = max(max_x, cell.x);
max_y = max(max_y, cell.y);
}
int h = max_x - min_x + 1;
int w = max_y - min_y + 1;
int s = max(h, w);
V<Cell> cells;
cells.reserve(raw_cells.size());
for (const auto& cell : raw_cells) {
cells.push_back({cell.x - min_x, cell.y - min_y, cell.color});
}
sort(cells, [](const Cell& a, const Cell& b) {
if (a.x != b.x) return a.x < b.x;
if (a.y != b.y) return a.y < b.y;
return a.color < b.color;
});
cells.erase(ranges::unique(cells, [](const Cell& a, const Cell& b) {
return a.x == b.x && a.y == b.y && a.color == b.color;
}).begin(),
cells.end());
return {cells, s};
}
inline VV<int> cells_to_stamp(const V<Cell>& cells, int s) {
VV<int> stamp(s, V<int>(s, 0));
for (const auto& cell : cells) {
stamp[cell.x][cell.y] = cell.color;
}
return stamp;
}
inline V<Cell> stamp_to_cells(const VV<int>& stamp) {
int s = (int)stamp.size();
V<Cell> cells;
for (int x = 0; x < s; ++x) {
for (int y = 0; y < s; ++y) {
if (stamp[x][y] > 0) {
cells.push_back({x, y, stamp[x][y]});
}
}
}
return cells;
}
inline int current_reverse_gain(const V<Cell>& cells,
int s,
int r,
int ai,
int aj,
const VV<int>& cur) {
int gain = 0;
for (const auto& cell : cells) {
auto [rx, ry] = rotate_in_square(cell.x, cell.y, s, r);
if (cur[ai + rx][aj + ry] == cell.color) {
++gain;
}
}
return gain;
}
inline V<Occurrence> select_occurrences_reverse_greedily(const V<Cell>& cells,
int s,
const VV<int>& cur,
StopWatch& timer,
int time_budget_ms) {
const int n = (int)cur.size();
V<Occurrence> candidates;
int probe = 0;
for (int r = 0; r < 4; ++r) {
for (int ai = 0; ai + s <= n; ++ai) {
for (int aj = 0; aj + s <= n; ++aj) {
if (((probe++) & 63) == 0 && time_over(timer, time_budget_ms)) {
return {};
}
bool ok = true;
int gain = 0;
for (const auto& cell : cells) {
auto [rx, ry] = rotate_in_square(cell.x, cell.y, s, r);
int v = cur[ai + rx][aj + ry];
if (v != STAR && v != cell.color) {
ok = false;
break;
}
if (v == cell.color) {
++gain;
}
}
if (ok && gain >= 2) {
candidates.push_back({r, ai, aj, gain});
}
}
}
}
VV<int> temp = cur;
V<Occurrence> chosen;
V<char> used(candidates.size(), 0);
while (true) {
if (time_over(timer, time_budget_ms)) {
return chosen;
}
int best_idx = -1;
int best_gain = 0;
for (int idx = 0; idx < (int)candidates.size(); ++idx) {
if ((idx & 255) == 0 && time_over(timer, time_budget_ms)) {
return chosen;
}
if (used[idx]) continue;
int gain = current_reverse_gain(cells, s, candidates[idx].r,
candidates[idx].ai,
candidates[idx].aj, temp);
if (gain > best_gain) {
best_gain = gain;
best_idx = idx;
}
}
if (best_idx == -1 || best_gain < 2) {
break;
}
used[best_idx] = 1;
auto occ = candidates[best_idx];
occ.gain = best_gain;
chosen.push_back(occ);
for (const auto& cell : cells) {
auto [rx, ry] = rotate_in_square(cell.x, cell.y, s, occ.r);
int& v = temp[occ.ai + rx][occ.aj + ry];
if (v == cell.color) {
v = STAR;
}
}
}
return chosen;
}
inline ReversePlan evaluate_stamp_reverse(const V<Cell>& cells,
int s,
const VV<int>& cur,
bool need_clear,
StopWatch& timer,
int time_budget_ms) {
ReversePlan plan;
if ((int)cells.size() < 4) {
plan.size = s;
plan.cells = cells;
return plan;
}
auto uses =
select_occurrences_reverse_greedily(cells, s, cur, timer, time_budget_ms);
int total_gain = 0;
for (const auto& occ : uses) {
total_gain += occ.gain;
}
int setup_cost =
(int)cells.size() + (int)uses.size() + (need_clear ? 1 : 0);
int saving = total_gain - setup_cost;
plan.saving = saving;
plan.total_gain = total_gain;
plan.size = s;
plan.cells = cells;
plan.uses = std::move(uses);
return plan;
}
inline ReversePlan evaluate_normalized_stamp(const VV<int>& stamp,
const VV<int>& cur,
bool need_clear,
StopWatch& timer,
int time_budget_ms) {
auto cells = stamp_to_cells(stamp);
auto [normalized_cells, s] = normalize_cells(cells);
return evaluate_stamp_reverse(normalized_cells, s, cur, need_clear, timer,
time_budget_ms);
}
inline VV<int> normalize_stamp(const VV<int>& stamp) {
auto cells = stamp_to_cells(stamp);
auto [normalized_cells, s] = normalize_cells(cells);
return cells_to_stamp(normalized_cells, s);
}
inline VV<int> mutate_stamp(const VV<int>& stamp,
XorShift64& rng,
int color_count) {
VV<int> next = stamp;
int s = (int)next.size();
V<pair<int, int>> filled, empty;
for (int x = 0; x < s; ++x) {
for (int y = 0; y < s; ++y) {
if (next[x][y] > 0) {
filled.push_back({x, y});
} else {
empty.push_back({x, y});
}
}
}
int op = rng.randint(0, 7);
if (op <= 2 && !filled.empty()) {
auto [x, y] = filled[rng.randint(0, (int)filled.size() - 1)];
next[x][y] = 0;
return normalize_stamp(next);
}
if (op == 3 && !filled.empty()) {
auto [x, y] = filled[rng.randint(0, (int)filled.size() - 1)];
int color = next[x][y];
if (color_count >= 2) {
int new_color = rng.randint(1, color_count - 1);
if (new_color >= color) ++new_color;
next[x][y] = new_color;
}
return normalize_stamp(next);
}
if (op == 4 && !filled.empty() && !empty.empty()) {
auto [fx, fy] = filled[rng.randint(0, (int)filled.size() - 1)];
int color = next[fx][fy];
next[fx][fy] = 0;
auto [tx, ty] = empty[rng.randint(0, (int)empty.size() - 1)];
next[tx][ty] = color;
return normalize_stamp(next);
}
if (op == 5 && !empty.empty()) {
auto [x, y] = empty[rng.randint(0, (int)empty.size() - 1)];
next[x][y] = rng.randint(1, color_count);
return normalize_stamp(next);
}
if (op >= 6 && s < MAX_STAMP_SIZE) {
VV<int> bigger(s + 1, V<int>(s + 1, 0));
int ox = rng.randint(0, 1);
int oy = rng.randint(0, 1);
for (int x = 0; x < s; ++x) {
for (int y = 0; y < s; ++y) {
bigger[x + ox][y + oy] = next[x][y];
}
}
V<pair<int, int>> bigger_empty;
for (int x = 0; x <= s; ++x) {
for (int y = 0; y <= s; ++y) {
if (bigger[x][y] == 0) {
bigger_empty.push_back({x, y});
}
}
}
if (!bigger_empty.empty()) {
auto [x, y] =
bigger_empty[rng.randint(0, (int)bigger_empty.size() - 1)];
bigger[x][y] = rng.randint(1, color_count);
}
return normalize_stamp(bigger);
}
return normalize_stamp(next);
}
inline ReversePlan hill_climb_stamp(VV<int> stamp,
const VV<int>& cur,
bool need_clear,
int color_count,
XorShift64& rng,
StopWatch& timer,
int time_budget_ms) {
stamp = normalize_stamp(stamp);
ReversePlan current =
evaluate_normalized_stamp(stamp, cur, need_clear, timer, time_budget_ms);
ReversePlan best = current;
int stalled = 0;
for (int iter = 0; iter < LOCAL_ITERS; ++iter) {
if (remaining_ms(timer, time_budget_ms) < kHillMarginMs) {
break;
}
auto next_stamp = mutate_stamp(stamp, rng, color_count);
ReversePlan next = evaluate_normalized_stamp(next_stamp, cur, need_clear,
timer, time_budget_ms);
if (better_plan(next, current)) {
current = next;
stamp = std::move(next_stamp);
stalled = 0;
if (better_plan(current, best)) {
best = current;
}
continue;
}
++stalled;
if (stalled >= 12) {
break;
}
}
return best;
}
inline void push_seed(V<SeedCandidate>& seeds, SeedCandidate seed) {
seeds.push_back(std::move(seed));
sort(seeds, better_seed);
if ((int)seeds.size() > LOCAL_SEED_LIMIT) {
seeds.resize(LOCAL_SEED_LIMIT);
}
}
inline ReversePlan find_best_reverse_plan(const VV<int>& cur,
bool need_clear,
int color_count,
StopWatch& timer,
int time_budget_ms) {
const int n = (int)cur.size();
int remaining = 0;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
remaining += (cur[i][j] > 0);
}
}
if (remaining < 4) {
return {};
}
ReversePlan best;
V<SeedCandidate> seeds;
const V<int> sizes = {2, 3, 4, 5, 6, 7, 8, 9, 10};
int probe = 0;
for (int s : sizes) {
if (remaining_ms(timer, time_budget_ms) < kSearchMarginMs) {
return best;
}
std::unordered_set<string> seen;
for (int bi = 0; bi + s <= n; ++bi) {
for (int bj = 0; bj + s <= n; ++bj) {
if (((probe++) & 63) == 0 &&
remaining_ms(timer, time_budget_ms) < kSearchMarginMs) {
return best;
}
string key = canonical_key(cur, bi, bj, s);
if (!seen.insert(key).second) {
continue;
}
auto cells = collect_cells_in_square(cur, bi, bj, s);
auto [normalized_cells, normalized_s] = normalize_cells(cells);
auto plan = evaluate_stamp_reverse(normalized_cells,
normalized_s, cur,
need_clear, timer,
time_budget_ms);
if (better_plan(plan, best)) {
best = plan;
}
push_seed(seeds,
{bi, bj, s, (int)cells.size(), std::move(cells), plan});
}
}
}
ull seed = 1469598103934665603ULL;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
seed ^= ull(cur[i][j] + 7);
seed *= 1099511628211ULL;
}
}
XorShift64 rng(seed ^ ull(need_clear ? 1 : 0));
for (const auto& seed_candidate : seeds) {
if (remaining_ms(timer, time_budget_ms) < kSearchMarginMs) {
return best;
}
V<pair<int, int>> starts = {
{seed_candidate.bi, seed_candidate.bj},
{seed_candidate.bi - 1, seed_candidate.bj},
{seed_candidate.bi + 1, seed_candidate.bj},
{seed_candidate.bi, seed_candidate.bj - 1},
{seed_candidate.bi, seed_candidate.bj + 1},
};
for (const auto& [bi, bj] : starts) {
if (bi < 0 || bj < 0 || bi + seed_candidate.s > n ||
bj + seed_candidate.s > n) {
continue;
}
auto cells = collect_cells_in_square(cur, bi, bj, seed_candidate.s);
auto [normalized_cells, normalized_s] = normalize_cells(cells);
auto stamp = cells_to_stamp(normalized_cells, normalized_s);
auto improved = hill_climb_stamp(stamp, cur, need_clear, color_count,
rng, timer, time_budget_ms);
if (better_plan(improved, best)) {
best = std::move(improved);
}
}
}
return best;
}
inline void apply_reverse_plan(VV<int>& cur, const ReversePlan& plan) {
for (const auto& occ : plan.uses) {
for (const auto& cell : plan.cells) {
auto [rx, ry] = rotate_in_square(cell.x, cell.y, plan.size, occ.r);
int& v = cur[occ.ai + rx][occ.aj + ry];
if (v == cell.color) {
v = STAR;
}
}
}
}
inline Answer build_forward_actions(const VV<int>& base,
const V<ReversePlan>& reverse_plans,
int n) {
Answer actions;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
if (base[i][j] > 0) {
marathon::push_paint(actions, 0, i, j, base[i][j]);
}
}
}
bool aux_initialized = false;
for (int idx = (int)reverse_plans.size() - 1; idx >= 0; --idx) {
const auto& plan = reverse_plans[idx];
if (aux_initialized) {
marathon::push_clear(actions, 1);
}
aux_initialized = true;
for (const auto& cell : plan.cells) {
marathon::push_paint(actions, 1, cell.x, cell.y, cell.color);
}
int shift = n - plan.size;
for (int t = (int)plan.uses.size() - 1; t >= 0; --t) {
const auto& occ = plan.uses[t];
int di = occ.ai;
int dj = occ.aj;
if (occ.r == 1) {
dj -= shift;
} else if (occ.r == 2) {
di -= shift;
dj -= shift;
} else if (occ.r == 3) {
di -= shift;
}
marathon::push_copy(actions, 0, 1, occ.r, di, dj);
}
}
return actions;
}
inline Answer build_fallback_actions(const VV<int>& goal) {
const int n = (int)goal.size();
Answer actions;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
if (goal[i][j] != 0) {
marathon::push_paint(actions, 0, i, j, goal[i][j]);
}
}
}
return actions;
}
inline bool is_applicable(const Problem& problem) {
return problem.n == marathon::kBoardSize && problem.k >= 2 && problem.c == 2;
}
inline std::optional<Answer> solve_if_applicable(const Problem& problem,
int available_ms) {
if (!is_applicable(problem)) {
return std::nullopt;
}
int time_budget_ms = available_ms - kStopGuardMs;
if (time_budget_ms <= 0) {
return std::nullopt;
}
StopWatch timer;
VV<int> cur = problem.g;
V<ReversePlan> reverse_plans;
while (!time_over(timer, time_budget_ms)) {
auto plan = find_best_reverse_plan(cur, !reverse_plans.empty(), problem.c,
timer, time_budget_ms);
if (plan.saving <= 0) {
break;
}
reverse_plans.push_back(plan);
apply_reverse_plan(cur, plan);
if ((int)reverse_plans.size() > problem.n * problem.n) {
break;
}
}
auto actions = build_forward_actions(cur, reverse_plans, problem.n);
auto fallback = build_fallback_actions(problem.g);
if (!marathon::is_valid_answer(problem, actions) ||
actions.size() >= fallback.size()) {
return std::nullopt;
}
return actions;
}
} // namespace inb0045_solver
namespace {
inline constexpr int kTimeLimitMs = 1750;
void log_answer(const char* name,
const Problem& problem,
int elapsed_ms,
const Answer& answer,
bool improved) {
int cost = my1_solver::answer_cost(problem, answer);
cerr << "[solver] " << name << " time_ms=" << elapsed_ms;
if (cost >= my1_solver::kInvalidCost) {
cerr << " valid=0 score=0";
} else {
cerr << " valid=1"
<< " ops=" << cost
<< " score=" << marathon::calc_actual_score(problem, answer);
}
if (improved) {
cerr << " best";
}
cerr << '\n';
}
void log_best_summary(const char* best_solver,
const Problem& problem,
int elapsed_ms,
const Answer& best,
const std::vector<std::string>& best_solvers) {
cerr << "[best] solver=" << best_solver << " ops=" << my1_solver::answer_cost(problem, best)
<< " score=" << marathon::calc_actual_score(problem, best)
<< " time_ms=" << elapsed_ms << '\n';
cerr << "[best-solvers]";
for (const auto& name : best_solvers) {
cerr << ' ' << name;
}
cerr << '\n';
}
} // namespace
int main() {
Problem problem = marathon::read_problem(sc);
StopWatch timer;
auto remaining_ms = [&]() { return max(0, kTimeLimitMs - timer.msecs()); };
Answer best = my1_solver::build_fallback_actions(problem);
int best_cost = my1_solver::answer_cost(problem, best);
std::string best_solver = "fallback";
std::vector<std::string> best_solvers = {best_solver};
log_answer("fallback", problem, timer.msecs(), best, true);
auto submit = [&](const char* name, Answer candidate) {
if (candidate.empty()) {
cerr << "[solver] " << name << " time_ms=" << timer.msecs()
<< " skipped=empty\n";
return;
}
int cost = my1_solver::answer_cost(problem, candidate);
bool improved = cost < best_cost;
log_answer(name, problem, timer.msecs(), candidate, improved);
if (improved) {
best = std::move(candidate);
best_cost = cost;
best_solver = name;
best_solvers = {best_solver};
} else if (cost == best_cost) {
best_solvers.push_back(name);
}
};
auto submit_with_budget = [&](const char* name, auto&& run_solver) {
int budget_ms = remaining_ms();
if (budget_ms <= 0) {
cerr << "[solver] " << name << " time_ms=" << timer.msecs()
<< " skipped=timeout\n";
return;
}
submit(name, run_solver(budget_ms));
};
submit_with_budget("inb0020",
[&](int budget_ms) {
return inb0020_solver::solve(problem, budget_ms);
});
submit_with_budget("inb0001",
[&](int budget_ms) {
return inb0001_solver::solve(problem, budget_ms);
});
submit_with_budget("inb0007",
[&](int budget_ms) {
return inb0007_solver::solve(problem, budget_ms);
});
//submit("inb0016", inb0016_solver::solve(problem));
submit_with_budget("inb0018",
[&](int budget_ms) {
return inb0018_solver::solve(problem.g, problem.k,
problem.c, budget_ms);
});
submit_with_budget("sol0042",
[&](int budget_ms) {
return sol0042::solve(problem, budget_ms)
.value_or(Answer{});
});
submit_with_budget("inb0045",
[&](int budget_ms) {
return inb0045_solver::solve_if_applicable(problem,
budget_ms)
.value_or(Answer{});
});
// submit_with_budget("sigma3",
// [&](int budget_ms) {
// return my1_solver::solve_sigma3(problem, budget_ms);
// });
submit_with_budget("sol-md",
[&](int budget_ms) {
return sol_md_solver::solve(problem, budget_ms);
});
//submit_with_budget("my1", [&](int budget_ms) {
// return my1_solver::solve(problem, budget_ms);
//});
log_best_summary(best_solver.c_str(), problem, timer.msecs(), best,
best_solvers);
marathon::print_answer(best, pr);
return 0;
}
提出情報
ジャッジ結果
| セット名 |
test_ALL |
| 得点 / 配点 |
441989300 / 15000000000 |
| 結果 |
|
| セット名 |
テストケース |
| test_ALL |
test_0000.txt, test_0001.txt, test_0002.txt, test_0003.txt, test_0004.txt, test_0005.txt, test_0006.txt, test_0007.txt, test_0008.txt, test_0009.txt, test_0010.txt, test_0011.txt, test_0012.txt, test_0013.txt, test_0014.txt, test_0015.txt, test_0016.txt, test_0017.txt, test_0018.txt, test_0019.txt, test_0020.txt, test_0021.txt, test_0022.txt, test_0023.txt, test_0024.txt, test_0025.txt, test_0026.txt, test_0027.txt, test_0028.txt, test_0029.txt, test_0030.txt, test_0031.txt, test_0032.txt, test_0033.txt, test_0034.txt, test_0035.txt, test_0036.txt, test_0037.txt, test_0038.txt, test_0039.txt, test_0040.txt, test_0041.txt, test_0042.txt, test_0043.txt, test_0044.txt, test_0045.txt, test_0046.txt, test_0047.txt, test_0048.txt, test_0049.txt, test_0050.txt, test_0051.txt, test_0052.txt, test_0053.txt, test_0054.txt, test_0055.txt, test_0056.txt, test_0057.txt, test_0058.txt, test_0059.txt, test_0060.txt, test_0061.txt, test_0062.txt, test_0063.txt, test_0064.txt, test_0065.txt, test_0066.txt, test_0067.txt, test_0068.txt, test_0069.txt, test_0070.txt, test_0071.txt, test_0072.txt, test_0073.txt, test_0074.txt, test_0075.txt, test_0076.txt, test_0077.txt, test_0078.txt, test_0079.txt, test_0080.txt, test_0081.txt, test_0082.txt, test_0083.txt, test_0084.txt, test_0085.txt, test_0086.txt, test_0087.txt, test_0088.txt, test_0089.txt, test_0090.txt, test_0091.txt, test_0092.txt, test_0093.txt, test_0094.txt, test_0095.txt, test_0096.txt, test_0097.txt, test_0098.txt, test_0099.txt, test_0100.txt, test_0101.txt, test_0102.txt, test_0103.txt, test_0104.txt, test_0105.txt, test_0106.txt, test_0107.txt, test_0108.txt, test_0109.txt, test_0110.txt, test_0111.txt, test_0112.txt, test_0113.txt, test_0114.txt, test_0115.txt, test_0116.txt, test_0117.txt, test_0118.txt, test_0119.txt, test_0120.txt, test_0121.txt, test_0122.txt, test_0123.txt, test_0124.txt, test_0125.txt, test_0126.txt, test_0127.txt, test_0128.txt, test_0129.txt, test_0130.txt, test_0131.txt, test_0132.txt, test_0133.txt, test_0134.txt, test_0135.txt, test_0136.txt, test_0137.txt, test_0138.txt, test_0139.txt, test_0140.txt, test_0141.txt, test_0142.txt, test_0143.txt, test_0144.txt, test_0145.txt, test_0146.txt, test_0147.txt, test_0148.txt, test_0149.txt |
| ケース名 |
結果 |
実行時間 |
メモリ |
| test_0000.txt |
AC |
1742 ms |
14608 KiB |
| test_0001.txt |
AC |
1742 ms |
17432 KiB |
| test_0002.txt |
AC |
1088 ms |
26012 KiB |
| test_0003.txt |
AC |
31 ms |
4924 KiB |
| test_0004.txt |
AC |
800 ms |
9876 KiB |
| test_0005.txt |
AC |
1751 ms |
40396 KiB |
| test_0006.txt |
AC |
697 ms |
15128 KiB |
| test_0007.txt |
AC |
1730 ms |
13488 KiB |
| test_0008.txt |
AC |
1422 ms |
13760 KiB |
| test_0009.txt |
AC |
1621 ms |
34596 KiB |
| test_0010.txt |
AC |
983 ms |
22488 KiB |
| test_0011.txt |
AC |
1570 ms |
33748 KiB |
| test_0012.txt |
AC |
1514 ms |
25680 KiB |
| test_0013.txt |
AC |
209 ms |
10032 KiB |
| test_0014.txt |
AC |
792 ms |
17928 KiB |
| test_0015.txt |
AC |
1325 ms |
24152 KiB |
| test_0016.txt |
AC |
1208 ms |
24300 KiB |
| test_0017.txt |
AC |
1375 ms |
13260 KiB |
| test_0018.txt |
AC |
980 ms |
12980 KiB |
| test_0019.txt |
AC |
1512 ms |
26212 KiB |
| test_0020.txt |
AC |
875 ms |
20736 KiB |
| test_0021.txt |
AC |
111 ms |
3536 KiB |
| test_0022.txt |
AC |
1742 ms |
35608 KiB |
| test_0023.txt |
AC |
667 ms |
15020 KiB |
| test_0024.txt |
AC |
1091 ms |
23384 KiB |
| test_0025.txt |
AC |
1740 ms |
3600 KiB |
| test_0026.txt |
AC |
1751 ms |
44696 KiB |
| test_0027.txt |
AC |
1752 ms |
47000 KiB |
| test_0028.txt |
AC |
230 ms |
10332 KiB |
| test_0029.txt |
AC |
138 ms |
9032 KiB |
| test_0030.txt |
AC |
981 ms |
24336 KiB |
| test_0031.txt |
AC |
1741 ms |
13396 KiB |
| test_0032.txt |
AC |
1601 ms |
28344 KiB |
| test_0033.txt |
AC |
1187 ms |
24464 KiB |
| test_0034.txt |
AC |
1741 ms |
14792 KiB |
| test_0035.txt |
AC |
603 ms |
11092 KiB |
| test_0036.txt |
AC |
711 ms |
18508 KiB |
| test_0037.txt |
AC |
1743 ms |
19856 KiB |
| test_0038.txt |
AC |
1034 ms |
12628 KiB |
| test_0039.txt |
AC |
1382 ms |
28956 KiB |
| test_0040.txt |
AC |
1035 ms |
21696 KiB |
| test_0041.txt |
AC |
1747 ms |
21080 KiB |
| test_0042.txt |
AC |
736 ms |
16920 KiB |
| test_0043.txt |
AC |
1349 ms |
17264 KiB |
| test_0044.txt |
AC |
1298 ms |
26312 KiB |
| test_0045.txt |
AC |
40 ms |
4656 KiB |
| test_0046.txt |
AC |
1739 ms |
4296 KiB |
| test_0047.txt |
AC |
1742 ms |
18512 KiB |
| test_0048.txt |
AC |
1443 ms |
27124 KiB |
| test_0049.txt |
AC |
1751 ms |
44124 KiB |
| test_0050.txt |
AC |
127 ms |
3672 KiB |
| test_0051.txt |
AC |
728 ms |
18448 KiB |
| test_0052.txt |
AC |
843 ms |
17276 KiB |
| test_0053.txt |
AC |
1742 ms |
14972 KiB |
| test_0054.txt |
AC |
975 ms |
20676 KiB |
| test_0055.txt |
AC |
1485 ms |
29968 KiB |
| test_0056.txt |
AC |
742 ms |
10208 KiB |
| test_0057.txt |
AC |
1611 ms |
15936 KiB |
| test_0058.txt |
AC |
137 ms |
5968 KiB |
| test_0059.txt |
AC |
1743 ms |
21292 KiB |
| test_0060.txt |
AC |
1079 ms |
22492 KiB |
| test_0061.txt |
AC |
1296 ms |
26064 KiB |
| test_0062.txt |
AC |
1561 ms |
19684 KiB |
| test_0063.txt |
AC |
133 ms |
3640 KiB |
| test_0064.txt |
AC |
38 ms |
4504 KiB |
| test_0065.txt |
AC |
1523 ms |
16408 KiB |
| test_0066.txt |
AC |
1342 ms |
25232 KiB |
| test_0067.txt |
AC |
31 ms |
4248 KiB |
| test_0068.txt |
AC |
1619 ms |
34788 KiB |
| test_0069.txt |
AC |
1584 ms |
30500 KiB |
| test_0070.txt |
AC |
1298 ms |
18292 KiB |
| test_0071.txt |
AC |
133 ms |
6152 KiB |
| test_0072.txt |
AC |
1587 ms |
15112 KiB |
| test_0073.txt |
AC |
1743 ms |
17748 KiB |
| test_0074.txt |
AC |
1420 ms |
13528 KiB |
| test_0075.txt |
AC |
1002 ms |
7724 KiB |
| test_0076.txt |
AC |
906 ms |
20684 KiB |
| test_0077.txt |
AC |
1750 ms |
37984 KiB |
| test_0078.txt |
AC |
1743 ms |
16692 KiB |
| test_0079.txt |
AC |
1741 ms |
15540 KiB |
| test_0080.txt |
AC |
1381 ms |
14420 KiB |
| test_0081.txt |
AC |
1741 ms |
12244 KiB |
| test_0082.txt |
AC |
1048 ms |
20760 KiB |
| test_0083.txt |
AC |
1725 ms |
32432 KiB |
| test_0084.txt |
AC |
703 ms |
12384 KiB |
| test_0085.txt |
AC |
1548 ms |
13660 KiB |
| test_0086.txt |
AC |
38 ms |
4564 KiB |
| test_0087.txt |
AC |
1751 ms |
40308 KiB |
| test_0088.txt |
AC |
1739 ms |
4340 KiB |
| test_0089.txt |
AC |
273 ms |
10348 KiB |
| test_0090.txt |
AC |
1271 ms |
26324 KiB |
| test_0091.txt |
AC |
1752 ms |
45932 KiB |
| test_0092.txt |
AC |
313 ms |
8592 KiB |
| test_0093.txt |
AC |
299 ms |
13100 KiB |
| test_0094.txt |
AC |
1751 ms |
45160 KiB |
| test_0095.txt |
AC |
808 ms |
20012 KiB |
| test_0096.txt |
AC |
1208 ms |
23260 KiB |
| test_0097.txt |
AC |
115 ms |
7524 KiB |
| test_0098.txt |
AC |
605 ms |
14000 KiB |
| test_0099.txt |
AC |
1618 ms |
12624 KiB |
| test_0100.txt |
AC |
699 ms |
13888 KiB |
| test_0101.txt |
AC |
812 ms |
18780 KiB |
| test_0102.txt |
AC |
1203 ms |
23184 KiB |
| test_0103.txt |
AC |
1743 ms |
20512 KiB |
| test_0104.txt |
AC |
1742 ms |
19448 KiB |
| test_0105.txt |
AC |
370 ms |
8916 KiB |
| test_0106.txt |
AC |
907 ms |
11024 KiB |
| test_0107.txt |
AC |
1111 ms |
16912 KiB |
| test_0108.txt |
AC |
1743 ms |
22416 KiB |
| test_0109.txt |
AC |
1738 ms |
4692 KiB |
| test_0110.txt |
AC |
1573 ms |
26064 KiB |
| test_0111.txt |
AC |
31 ms |
4148 KiB |
| test_0112.txt |
AC |
1744 ms |
12732 KiB |
| test_0113.txt |
AC |
1355 ms |
27724 KiB |
| test_0114.txt |
AC |
1747 ms |
19984 KiB |
| test_0115.txt |
AC |
1674 ms |
16664 KiB |
| test_0116.txt |
AC |
1246 ms |
27256 KiB |
| test_0117.txt |
AC |
708 ms |
16656 KiB |
| test_0118.txt |
AC |
531 ms |
7120 KiB |
| test_0119.txt |
AC |
1741 ms |
13124 KiB |
| test_0120.txt |
AC |
1743 ms |
19592 KiB |
| test_0121.txt |
AC |
1742 ms |
16828 KiB |
| test_0122.txt |
AC |
1316 ms |
15612 KiB |
| test_0123.txt |
AC |
1744 ms |
21676 KiB |
| test_0124.txt |
AC |
823 ms |
17348 KiB |
| test_0125.txt |
AC |
1742 ms |
18232 KiB |
| test_0126.txt |
AC |
1081 ms |
23064 KiB |
| test_0127.txt |
AC |
1751 ms |
44972 KiB |
| test_0128.txt |
AC |
1740 ms |
3472 KiB |
| test_0129.txt |
AC |
693 ms |
12552 KiB |
| test_0130.txt |
AC |
214 ms |
9852 KiB |
| test_0131.txt |
AC |
1754 ms |
46164 KiB |
| test_0132.txt |
AC |
1741 ms |
14004 KiB |
| test_0133.txt |
AC |
1751 ms |
41064 KiB |
| test_0134.txt |
AC |
1653 ms |
14780 KiB |
| test_0135.txt |
AC |
1743 ms |
19352 KiB |
| test_0136.txt |
AC |
1743 ms |
18312 KiB |
| test_0137.txt |
AC |
1411 ms |
13028 KiB |
| test_0138.txt |
AC |
1029 ms |
20908 KiB |
| test_0139.txt |
AC |
1650 ms |
15572 KiB |
| test_0140.txt |
AC |
1751 ms |
40568 KiB |
| test_0141.txt |
AC |
1740 ms |
12220 KiB |
| test_0142.txt |
AC |
1741 ms |
13484 KiB |
| test_0143.txt |
AC |
1563 ms |
15000 KiB |
| test_0144.txt |
AC |
761 ms |
17612 KiB |
| test_0145.txt |
AC |
1743 ms |
19632 KiB |
| test_0146.txt |
AC |
1331 ms |
28264 KiB |
| test_0147.txt |
AC |
1645 ms |
9044 KiB |
| test_0148.txt |
AC |
32 ms |
4184 KiB |
| test_0149.txt |
AC |
1739 ms |
4660 KiB |