結果
| 問題 | No.5020 Averaging |
| ユーザー |
👑  hitonanode
|
| 提出日時 | 2024-02-26 23:01:35 |
| 言語 | C++23 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
AC
|
| 実行時間 | 951 ms / 1,000 ms |
| コード長 | 24,638 bytes |
| コンパイル時間 | 2,963 ms |
| コンパイル使用メモリ | 206,196 KB |
| 実行使用メモリ | 6,676 KB |
| スコア | 81,718,344 |
| 最終ジャッジ日時 | 2024-02-26 23:02:28 |
| 合計ジャッジ時間 | 52,530 ms |
|
ジャッジサーバーID （参考情報） |
judge15 / judge10 |
| 純コード判定しない問題か言語 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 924 ms
6,676 KB |
| testcase_01 | AC | 941 ms
6,676 KB |
| testcase_02 | AC | 946 ms
6,676 KB |
| testcase_03 | AC | 944 ms
6,676 KB |
| testcase_04 | AC | 945 ms
6,676 KB |
| testcase_05 | AC | 922 ms
6,676 KB |
| testcase_06 | AC | 920 ms
6,676 KB |
| testcase_07 | AC | 946 ms
6,676 KB |
| testcase_08 | AC | 923 ms
6,676 KB |
| testcase_09 | AC | 942 ms
6,676 KB |
| testcase_10 | AC | 919 ms
6,676 KB |
| testcase_11 | AC | 943 ms
6,676 KB |
| testcase_12 | AC | 918 ms
6,676 KB |
| testcase_13 | AC | 922 ms
6,676 KB |
| testcase_14 | AC | 947 ms
6,676 KB |
| testcase_15 | AC | 925 ms
6,676 KB |
| testcase_16 | AC | 920 ms
6,676 KB |
| testcase_17 | AC | 921 ms
6,676 KB |
| testcase_18 | AC | 916 ms
6,676 KB |
| testcase_19 | AC | 925 ms
6,676 KB |
| testcase_20 | AC | 923 ms
6,676 KB |
| testcase_21 | AC | 924 ms
6,676 KB |
| testcase_22 | AC | 916 ms
6,676 KB |
| testcase_23 | AC | 915 ms
6,676 KB |
| testcase_24 | AC | 922 ms
6,676 KB |
| testcase_25 | AC | 944 ms
6,676 KB |
| testcase_26 | AC | 923 ms
6,676 KB |
| testcase_27 | AC | 946 ms
6,676 KB |
| testcase_28 | AC | 921 ms
6,676 KB |
| testcase_29 | AC | 948 ms
6,676 KB |
| testcase_30 | AC | 922 ms
6,676 KB |
| testcase_31 | AC | 951 ms
6,676 KB |
| testcase_32 | AC | 918 ms
6,676 KB |
| testcase_33 | AC | 941 ms
6,676 KB |
| testcase_34 | AC | 918 ms
6,676 KB |
| testcase_35 | AC | 946 ms
6,676 KB |
| testcase_36 | AC | 925 ms
6,676 KB |
| testcase_37 | AC | 946 ms
6,676 KB |
| testcase_38 | AC | 921 ms
6,676 KB |
| testcase_39 | AC | 945 ms
6,676 KB |
| testcase_40 | AC | 922 ms
6,676 KB |
| testcase_41 | AC | 922 ms
6,676 KB |
| testcase_42 | AC | 927 ms
6,676 KB |
| testcase_43 | AC | 925 ms
6,676 KB |
| testcase_44 | AC | 945 ms
6,676 KB |
| testcase_45 | AC | 942 ms
6,676 KB |
| testcase_46 | AC | 920 ms
6,676 KB |
| testcase_47 | AC | 939 ms
6,676 KB |
| testcase_48 | AC | 921 ms
6,676 KB |
| testcase_49 | AC | 949 ms
6,676 KB |
ソースコード
#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <chrono>
#include <cmath>
#include <complex>
#include <deque>
#include <forward_list>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iostream>
#include <limits>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
#include <iostream>
#include <string>
#include <utility>
#include <vector>
class JsonDumper {
struct KeyValue {
std::string key;
std::string value;
};
std::vector<KeyValue> _items;
bool dump_at_end = false;
public:
JsonDumper(bool dump_at_end_ = false) : dump_at_end(dump_at_end_) {}
~JsonDumper() {
if (dump_at_end) std::cout << dump() << std::endl;
}
void set_dump_at_end() { dump_at_end = true; }
void operator()(const std::string &key, const std::string &value) {
_items.push_back(KeyValue{key, "\"" + value + "\""});
}
template <class T> void operator()(const std::string &key, T value) {
_items.push_back(KeyValue{key, std::to_string(value)});
}
std::string dump() const {
std::string ret = "{\n";
if (!_items.empty()) {
for (const auto &[k, v] : _items) ret += " \"" + k + "\": " + v + ",\n";
ret.erase(ret.end() - 2);
}
ret += "}";
return ret;
}
} jdump;
#define ALL(x) (x).begin(), (x).end()
#define FOR(i, begin, end) for (int i = (begin), i##_end_ = (end); i < i##_end_; i++)
#define IFOR(i, begin, end) for (int i = (end)-1, i##_begin_ = (begin); i >= i##_begin_; i--)
#define REP(i, n) FOR(i, 0, n)
#define IREP(i, n) IFOR(i, 0, n)
template <typename T> bool chmax(T &m, const T q) { return m < q ? (m = q, true) : false; }
template <typename T> bool chmin(T &m, const T q) { return m > q ? (m = q, true) : false; }
int floor_lg(long long x) { return x <= 0 ? -1 : 63 - __builtin_clzll(x); }
template <class T1, class T2> T1 floor_div(T1 num, T2 den) {
return (num > 0 ? num / den : -((-num + den - 1) / den));
}
template <class T1, class T2> std::pair<T1, T2> operator+(const std::pair<T1, T2> &l, const std::pair<T1, T2> &r) {
return std::make_pair(l.first + r.first, l.second + r.second);
}
template <class T1, class T2> std::pair<T1, T2> operator-(const std::pair<T1, T2> &l, const std::pair<T1, T2> &r) {
return std::make_pair(l.first - r.first, l.second - r.second);
}
template <class T> std::vector<T> sort_unique(std::vector<T> vec) {
sort(vec.begin(), vec.end()), vec.erase(unique(vec.begin(), vec.end()), vec.end());
return vec;
}
template <class T> int arglb(const std::vector<T> &v, const T &x) {
return std::distance(v.begin(), std::lower_bound(v.begin(), v.end(), x));
}
template <class T> int argub(const std::vector<T> &v, const T &x) {
return std::distance(v.begin(), std::upper_bound(v.begin(), v.end(), x));
}
template <class IStream, class T> IStream &operator>>(IStream &is, std::vector<T> &vec) {
for (auto &v : vec) is >> v;
return is;
}
template <class OStream, class T> OStream &operator<<(OStream &os, const std::vector<T> &vec);
template <class OStream, class T, size_t sz> OStream &operator<<(OStream &os, const std::array<T, sz> &arr);
template <class OStream, class T, class TH> OStream &operator<<(OStream &os, const std::unordered_set<T, TH> &vec);
template <class OStream, class T, class U> OStream &operator<<(OStream &os, const std::pair<T, U> &pa);
template <class OStream, class T> OStream &operator<<(OStream &os, const std::deque<T> &vec);
template <class OStream, class T> OStream &operator<<(OStream &os, const std::set<T> &vec);
template <class OStream, class T> OStream &operator<<(OStream &os, const std::multiset<T> &vec);
template <class OStream, class T> OStream &operator<<(OStream &os, const std::unordered_multiset<T> &vec);
template <class OStream, class T, class U> OStream &operator<<(OStream &os, const std::pair<T, U> &pa);
template <class OStream, class TK, class TV> OStream &operator<<(OStream &os, const std::map<TK, TV> &mp);
template <class OStream, class TK, class TV, class TH>
OStream &operator<<(OStream &os, const std::unordered_map<TK, TV, TH> &mp);
template <class OStream, class... T> OStream &operator<<(OStream &os, const std::tuple<T...> &tpl);
template <class OStream, class T> OStream &operator<<(OStream &os, const std::vector<T> &vec) {
os << '[';
for (auto v : vec) os << v << ',';
os << ']';
return os;
}
template <class OStream, class T, size_t sz> OStream &operator<<(OStream &os, const std::array<T, sz> &arr) {
os << '[';
for (auto v : arr) os << v << ',';
os << ']';
return os;
}
template <class... T> std::istream &operator>>(std::istream &is, std::tuple<T...> &tpl) {
std::apply([&is](auto &&...args) { ((is >> args), ...); }, tpl);
return is;
}
template <class OStream, class... T> OStream &operator<<(OStream &os, const std::tuple<T...> &tpl) {
os << '(';
std::apply([&os](auto &&...args) { ((os << args << ','), ...); }, tpl);
return os << ')';
}
template <class OStream, class T, class TH> OStream &operator<<(OStream &os, const std::unordered_set<T, TH> &vec) {
os << '{';
for (auto v : vec) os << v << ',';
os << '}';
return os;
}
template <class OStream, class T> OStream &operator<<(OStream &os, const std::deque<T> &vec) {
os << "deq[";
for (auto v : vec) os << v << ',';
os << ']';
return os;
}
template <class OStream, class T> OStream &operator<<(OStream &os, const std::set<T> &vec) {
os << '{';
for (auto v : vec) os << v << ',';
os << '}';
return os;
}
template <class OStream, class T> OStream &operator<<(OStream &os, const std::multiset<T> &vec) {
os << '{';
for (auto v : vec) os << v << ',';
os << '}';
return os;
}
template <class OStream, class T> OStream &operator<<(OStream &os, const std::unordered_multiset<T> &vec) {
os << '{';
for (auto v : vec) os << v << ',';
os << '}';
return os;
}
template <class OStream, class T, class U> OStream &operator<<(OStream &os, const std::pair<T, U> &pa) {
return os << '(' << pa.first << ',' << pa.second << ')';
}
template <class OStream, class TK, class TV> OStream &operator<<(OStream &os, const std::map<TK, TV> &mp) {
os << '{';
for (auto v : mp) os << v.first << "=>" << v.second << ',';
os << '}';
return os;
}
template <class OStream, class TK, class TV, class TH>
OStream &operator<<(OStream &os, const std::unordered_map<TK, TV, TH> &mp) {
os << '{';
for (auto v : mp) os << v.first << "=>" << v.second << ',';
os << '}';
return os;
}
#ifdef HITONANODE_LOCAL
const std::string COLOR_RESET = "\033[0m", BRIGHT_GREEN = "\033[1;32m", BRIGHT_RED = "\033[1;31m",
BRIGHT_CYAN = "\033[1;36m", NORMAL_CROSSED = "\033[0;9;37m", RED_BACKGROUND = "\033[1;41m",
NORMAL_FAINT = "\033[0;2m";
#define dbg(x) \
std::cerr << BRIGHT_CYAN << #x << COLOR_RESET << " = " << (x) << NORMAL_FAINT << " (L" << __LINE__ << ") " \
<< __FILE__ << COLOR_RESET << std::endl
#define dbgif(cond, x) \
((cond) ? std::cerr << BRIGHT_CYAN << #x << COLOR_RESET << " = " << (x) << NORMAL_FAINT << " (L" << __LINE__ \
<< ") " << __FILE__ << COLOR_RESET << std::endl \
: std::cerr)
#else
#define dbg(x) 0
#define dbgif(cond, x) 0
#endif
#ifdef BENCHMARK
#define dump_onlinejudge(x) 0
struct setenv {
setenv() { jdump.set_dump_at_end(); }
} setenv_;
#else
#define dump_onlinejudge(x) (std::cout << (x) << std::endl)
#endif
#include <array>
#include <cassert>
#include <cmath>
#include <cstdlib>
#include <vector>
using namespace std;
using lint = long long;
using pint = std::pair<int, int>;
using plint = std::pair<lint, lint>;
struct fast_ios {
fast_ios() {
std::cin.tie(nullptr), std::ios::sync_with_stdio(false), std::cout << std::fixed << std::setprecision(20);
};
} fast_ios_;
constexpr int N = 45;
// void gen
constexpr lint AMIN = 100000000000000000;
constexpr lint AMAX = 1000000000000000000;
constexpr lint goalx = 500000000000000000;
constexpr lint goaly = 500000000000000000;
constexpr int MAXT = 50;
#include <cstdint>
#include <vector>
uint32_t rand_int() // XorShift random integer generator
{
static uint32_t x = 123456789, y = 362436069, z = 521288629, w = 88675123;
uint32_t t = x ^ (x << 11);
x = y;
y = z;
z = w;
return w = (w ^ (w >> 19)) ^ (t ^ (t >> 8));
}
double rand_double() { return (double)rand_int() / UINT32_MAX; }
template <class T> void shuffle_vec(std::vector<T> &vec) {
for (int i = 1; i < (int)vec.size(); ++i) {
const int j = rand_int() % (i + 1);
std::swap(vec.at(i), vec.at(j));
}
}
#include <chrono>
#include <random>
struct rand_int_ {
using lint = long long;
std::mt19937 mt;
rand_int_() : mt(std::chrono::steady_clock::now().time_since_epoch().count()) {}
lint operator()(lint x) { return this->operator()(0, x); } // [0, x)
lint operator()(lint l, lint r) {
std::uniform_int_distribution<lint> d(l, r - 1);
return d(mt);
}
} rnd;
double eval_diversity(const array<lint, N> &A, const array<lint, N> &B, const bitset<N> &alives, lint cx, lint cy) {
const int Z = 60;
// const double r = 0.9;
const double dec = 2.0;
vector<double> hi(Z, -1e18);
vector<double> invdsum(Z);
REP(i, A.size()) {
if (!alives[i]) continue;
const lint a = A.at(i);
const lint b = B.at(i);
const double theta = atan2(b - cy, a - cx);
int z = (theta / (2 * M_PI) + 0.5) * Z;
// z = (z % Z + Z) % Z;
const double dist = max(abs(a - cx), abs(b - cy)) + 1;
// chmax(hi.at(z), -log10(dist));
invdsum.at(z) += 1.0 / dist;
}
REP(z, Z) {
if (invdsum.at(z)) hi.at(z) = log10(invdsum.at(z));
}
REP(_, 2) {
FOR(i, 1, Z) {
chmax(hi.at(i), hi.at(i - 1) - dec);
}
chmax(hi.at(0), hi.at(Z - 1) - dec);
IFOR(i, 1, Z) {
chmax(hi.at(i - 1), hi.at(i) - dec);
}
chmax(hi.at(Z - 1), hi.at(0) - dec);
}
return accumulate(ALL(hi), 0.0);
}
struct State {
State *par = nullptr;
std::vector<pint> par_op; // par からどのような手でこれに到達するか
int num_steps = 0;
std::bitset<N> alives;
std::array<lint, N> A, B;
static State gen_root(const array<lint, N> &A, const array<lint, N> &B) {
State s;
s.alives.set();
s.A = A;
s.B = B;
return s;
}
State gen_next(const vector<pint> ops) {
State next;
next.par = this;
next.par_op = ops;
next.num_steps = num_steps + (int)ops.size();
next.alives = alives;
next.A = A;
next.B = B;
for (auto [i, j] : ops) {
lint tmpa = (next.A.at(i) + next.A.at(j)) / 2;
lint tmpb = (next.B.at(i) + next.B.at(j)) / 2;
next.A.at(i) = next.A.at(j) = tmpa;
next.B.at(i) = next.B.at(j) = tmpb;
}
return next;
}
State try_drop(bool force) {
lint sumx = 0, sumy = 0;
const int nalive = alives.count();
REP(i, N) {
if (alives[i]) {
sumx += A.at(i) - goalx;
sumy += B.at(i) - goaly;
}
}
const double error = 1.0 * max(abs(sumx), abs(sumy)) / nalive;
int besti = -1;
double besterror = error;
// dbg(force);
if (force) besterror = 1e30;
FOR(i, 1, N) {
if (!alives[i]) continue;
// if ((sumx > 0) != (A.at(i) > goalx)) continue;
// if ((sumy > 0) != (B.at(i) > goaly)) continue;
// if (abs(sumx) < abs(A.at(i) - goalx)) continue;
// if (abs(sumy) < abs(B.at(i) - goaly)) continue;
const double errornew = 1.0 * max(abs(sumx - A.at(i) + goalx), abs(sumy - B.at(i) + goaly)) / (nalive - 1);
if (chmin(besterror, errornew)) besti = i;
}
if (besti < 0) return *this;
dbg(make_tuple("Drop", 1.0 * sumx / nalive, 1.0 * sumy / nalive, nalive, besti));
State next = *this;
next.alives[besti] = false;
return next;
}
State step() {
lint sumx = 0, sumy = 0;
const int nalive = alives.count();
REP(i, N) {
if (alives[i]) {
sumx += A.at(i);
sumy += B.at(i);
}
}
vector<pint> best_way;
double min_error = 1e30;
int xmini = -1, xmaxi = -1, ymini = -1, ymaxi = -1;
lint xmin = AMAX + 1, xmax = -1e18, ymin = AMAX + 1, ymax = -1e18;
REP(i, N) {
if (!alives[i]) continue;
if (chmin(xmin, A.at(i))) xmini = i;
if (chmax(xmax, A.at(i))) xmaxi = i;
if (chmin(ymin, B.at(i))) ymini = i;
if (chmax(ymax, B.at(i))) ymaxi = i;
}
if (abs(ymax - ymin) > abs(xmax - xmin)) {
best_way.emplace_back(ymini, ymaxi);
} else {
best_way.emplace_back(xmini, xmaxi);
}
// if (mode & 1) best_way.emplace_back(xmini, xmaxi);
// if (mode & 2) best_way.emplace_back(ymini, ymaxi);
return gen_next(best_way);
}
State primer() {
vector<pint> best_ops;
double best = AMAX;
// const lint cx = goalx * 2 - A.at(0);
const lint cx = goalx;
// const lint cy = goaly * 2 - B.at(0);
const lint cy = goaly;
const lint d0 = max(abs(A.at(0) - cx), abs(B.at(0) - cy));
auto Anxt = A, Bnxt = B;
REP(i, N) REP(j, i) {
if (!alives[i] or !alives[j]) continue;
lint a = (A.at(i) + A.at(j)) / 2;
lint b = (B.at(i) + B.at(j)) / 2;
lint d = max(abs(a - cx), abs(b - cy));
if (d > d0) continue;
Anxt.at(i) = Anxt.at(j) = a;
Bnxt.at(i) = Bnxt.at(j) = b;
double after = eval_diversity(Anxt, Bnxt, alives, cx, cy);
Anxt.at(i) = A.at(i);
Anxt.at(j) = A.at(j);
Bnxt.at(i) = B.at(i);
Bnxt.at(j) = B.at(j);
// double after = log(1.0 * d * d);
if (chmin(best, -after)) best_ops = {{i, j}};
}
return gen_next(best_ops);
}
State greedy2() {
lint best = AMAX;
vector<pint> best_ops;
// 0-i
FOR(i, 1, N) {
lint a = (A.at(0) + A.at(i)) / 2;
lint b = (B.at(0) + B.at(i)) / 2;
if (chmin(best, max(abs(a - goalx), abs(b - goaly)))) {
best_ops = {{0, i}};
}
}
// i-j, 0-i
// i-j, 0-i, 0-j
if (num_steps + 2 <= MAXT) {
FOR(i, 1, N) FOR(j, 1, i) {
const lint a1 = (A.at(i) + A.at(j)) / 2;
const lint b1 = (B.at(i) + B.at(j)) / 2;
{
const lint a = (A.at(0) + a1) / 2;
const lint b = (B.at(0) + b1) / 2;
if (chmin(best, max(abs(a - goalx), abs(b - goaly)))) {
best_ops = {{i, j}, {0, i}};
}
if (num_steps + 3 <= MAXT) {
const lint a2 = (a + a1) / 2;
const lint b2 = (b + b1) / 2;
if (chmin(best, max(abs(a2 - goalx), abs(b2 - goaly)))) {
best_ops = {{i, j}, {0, i}, {0, j}};
}
}
}
}
}
return gen_next(best_ops);
}
lint eval_linf() const { return max(abs(A.at(0) - goalx), abs(B.at(0) - goaly)); }
};
int calc_score(lint max_v1v2) {
if (!max_v1v2) return 2000000 + 50;
double sol = 2000000 - 100000 * log10(max_v1v2 + 1);
return floor(sol);
}
void experiment() {
constexpr int D = 28;
vector<lint> A(D), B(D);
REP(i, D) {
A.at(i) = rnd(AMIN, AMAX);
B.at(i) = rnd(AMIN, AMAX);
}
lint best_s = 0;
lint best = 1LL << 60;
FOR(S, 1, 1 << D) {
lint asum = 0, bsum = 0, num = 0;
REP(i, D) {
if ((S >> i) & 1) {
asum += A.at(i);
bsum += B.at(i);
++num;
}
}
asum /= num;
bsum /= num;
const lint eval = max(abs(asum - goalx), abs(bsum - goaly));
if (chmin(best, eval)) {
best_s = S;
}
if (__builtin_popcount(S + 1) == 1) {
dbg(make_tuple(best, best_s, S));
}
}
}
vector<pint> generate_seq(const State *s) {
vector<pint> res;
while (s->par) {
res.insert(res.end(), s->par_op.rbegin(), s->par_op.rend());
s = s->par;
}
reverse(ALL(res));
return res;
}
using SolutionState = vector<pint>;
double eval_l2(const array<long long, N> &Ainit, const array<long long, N> &Binit, const SolutionState &sol) {
array<long long, N> A = Ainit, B = Binit;
for (auto [i, j] : sol) {
lint tmpa = (A.at(i) + A.at(j)) / 2;
lint tmpb = (B.at(i) + B.at(j)) / 2;
A.at(i) = A.at(j) = tmpa;
B.at(i) = B.at(j) = tmpb;
}
const double dx = abs(A.at(0) - goalx), dy = abs(B.at(0) - goaly);
return sqrt(dx * dx + dy * dy);
}
lint eval_linf(const array<long long, N> &Ainit, const array<long long, N> &Binit, const SolutionState &sol) {
array<long long, N> A = Ainit, B = Binit;
for (auto [i, j] : sol) {
lint tmpa = (A.at(i) + A.at(j)) / 2;
lint tmpb = (B.at(i) + B.at(j)) / 2;
A.at(i) = A.at(j) = tmpa;
B.at(i) = B.at(j) = tmpb;
}
const lint dx = abs(A.at(0) - goalx), dy = abs(B.at(0) - goaly);
return max(dx, dy);
}
struct Solver {
array<long long, N> initA, initB;
vector<pint> intro_ops;
vector<pint> best_intro_ops;
vector<int> after_intro;
vector<int> best_after_intro;
double best_cost = 1e300;
void check_best() {
if (chmin(best_cost, cost)) {
best_intro_ops = intro_ops;
best_after_intro = after_intro;
}
}
array<long long, N> preprocessedA, preprocessedB;
long long gx2, gy2;
double cost;
static constexpr int E = 1;
void precalc() {
preprocessedA = initA;
preprocessedB = initB;
for (auto [i, j] : intro_ops) {
lint tmpa = (preprocessedA.at(i) + preprocessedA.at(j)) / 2;
lint tmpb = (preprocessedB.at(i) + preprocessedB.at(j)) / 2;
preprocessedA.at(i) = preprocessedA.at(j) = tmpa;
preprocessedB.at(i) = preprocessedB.at(j) = tmpb;
}
gx2 = preprocessedA.at(0) >> (after_intro.size() - E);
gy2 = preprocessedB.at(0) >> (after_intro.size() - E);
REP(d, after_intro.size()) {
const int i = after_intro.at(d);
gx2 += preprocessedA.at(i) >> (after_intro.size() - d - E);
gy2 += preprocessedB.at(i) >> (after_intro.size() - d - E);
}
cost = hypot(abs((gx2 >> E) - goalx), abs((gy2 >> E) - goaly));
check_best();
}
Solver(const array<long long, N> &A, const array<long long, N> &B) : initA(A), initB(B) {
after_intro.resize(N - 1);
REP(i, N - 1) after_intro.at(i) = i + 1;
precalc();
}
void swap2(int d, int e, double temp) {
const int i = after_intro.at(d);
const int j = after_intro.at(e);
lint tmpgx2 = gx2 - (preprocessedA.at(i) >> (after_intro.size() - d - E)) +
(preprocessedA.at(j) >> (after_intro.size() - d - E));
tmpgx2 += (preprocessedA.at(i) >> (after_intro.size() - e - E)) -
(preprocessedA.at(j) >> (after_intro.size() - e - E));
lint tmpgy2 = gy2 - (preprocessedB.at(i) >> (after_intro.size() - d - E)) +
(preprocessedB.at(j) >> (after_intro.size() - d - E));
tmpgy2 += (preprocessedB.at(i) >> (after_intro.size() - e - E)) -
(preprocessedB.at(j) >> (after_intro.size() - e - E));
double tmpcost = hypot(abs((tmpgx2 >> E) - goalx), abs((tmpgy2 >> E) - goaly));
if (tmpcost <= cost or exp((cost - tmpcost) / temp) > rand_double()) {
swap(after_intro.at(d), after_intro.at(e));
gx2 = tmpgx2;
gy2 = tmpgy2;
cost = tmpcost;
check_best();
}
}
};
int main(int argc, char *argv[]) {
{
int n_;
cin >> n_;
assert(N == n_);
}
array<long long, N> A, B;
{
for (int i = 0; i < N; i++) {
cin >> A.at(i) >> B.at(i);
}
}
Solver solver(A, B);
auto A0 = A, B0 = B;
// SolutionState state;
REP(_, 6) {
lint maxdiff = 0;
int a = 0, b = 0;
REP(i, N) REP(j, i) {
lint diff = max(abs(A0.at(i) - A0.at(j)), abs(B0.at(i) - B0.at(j)));
if (chmax(maxdiff, diff)) {
a = i, b = j;
}
}
solver.intro_ops.emplace_back(a, b);
lint tmpa = (A0.at(a) + A0.at(b)) / 2;
lint tmpb = (B0.at(a) + B0.at(b)) / 2;
A0.at(a) = A0.at(b) = tmpa;
B0.at(a) = B0.at(b) = tmpb;
}
solver.precalc();
// REP(i, N - 1) state.emplace_back(0, i + 1);
// // REP(_, 6) state.emplace_back(0, _ + 1);
// auto best = state;
// double estate = eval_l2(A, B, state);
// double ebest = estate;
const double Tbegin = 1e17, Tend = 10;
constexpr int L = 9000000;
REP(_, L) {
double T = Tbegin * pow(Tend / Tbegin, 1.0 * _ / L);
int a = 0, b = 0;
if (rand_double() < 0.5) {
while (a == b) {
a = rand_int() % (N - 1);
b = rand_int() % (N - 1);
}
} else {
const int s = rand_int() % 3 + 1;
a = rand_int() % (N - 1 - s);
b = a + s;
}
solver.swap2(a, b, T);
}
vector<pint> best = solver.best_intro_ops;
for (int i : solver.best_after_intro) {
best.emplace_back(0, i);
}
dump_onlinejudge(best.size());
for (auto [i, j] : best) {
dump_onlinejudge(to_string(i + 1) + " " + to_string(j + 1));
}
// vector<State> states(10000);
// states.at(0) = State::gen_root(A, B);
// int h = 0;
// bool mode = false;
// while (states.at(h).num_steps < MAXT and states.at(h).alives.count() > 1) {
// const int nalive = states.at(h).alives.count();
// const int rem_turn = MAXT - states.at(h).num_steps;
// dbg(make_tuple(h, nalive, rem_turn));
// states.at(h + 1) = states.at(h).try_drop(rem_turn * 0.5 + 1 < nalive);
// ++h;
// // dbg(states.at(h).alives.count());
// // states.at(h + 1) = states.at(h).step(mode);
// // mode ^= 1;
// // ++h;
// if (states.at(h).num_steps < MAXT) {
// if (states.at(h).num_steps > MAXT * 0.9) {
// states.at(h + 1) = states.at(h).greedy2();
// ++h;
// } else {
// states.at(h + 1) = states.at(h).step();
// // states.at(h + 1) = states.at(h).primer();
// ++h;
// }
// mode ^= 1;
// }
// // if (h % 3 != 2 or states.at(h).num_steps < MAXT * 0.5) {
// // states.at(h + 1) = states.at(h).primer();
// // } else {
// // states.at(h + 1) = states.at(h).greedy2();
// // }
// // ++h;
// // dbg(make_tuple(states.at(h).num_steps, states.at(h).eval_linf()));
// }
// const State *goal_state = &states.at(h);
// dbg(goal_state->alives);
// auto sol = generate_seq(goal_state);
// dump_onlinejudge(sol.size());
// for (auto [i, j] : sol) {
// dump_onlinejudge(to_string(i + 1) + " " + to_string(j + 1));
// }
const lint cost = eval_linf(A, B, best);
const int score = calc_score(cost);
jdump("score", score);
dbg(cost);
dbg(score);
}