Submission #33001443

---

Source Code Expand

#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")

#ifndef TIMER_H
#define TIMER_H

#include <cstdint>

#ifdef ONLY_MY_ENVIR

#include <chrono>
class Timer {
	const std::chrono::time_point<std::chrono::system_clock> start;
	std::int64_t limit_microsec = 0;

public:
	Timer();
	void set(std::int64_t time_microsec);
	bool elapsed() const;
	std::int64_t getMicrosec() const;
};

#else

class Timer {
	static const std::uint64_t ClocksPerMicrosec;
	const std::uint64_t start_clocks;
	std::uint64_t limit_clocks;

	std::uint64_t getClocks() const;

public:
	Timer();
	void set(std::int64_t time_microsec);
	bool elapsed() const;
	std::int64_t getMicrosec() const;
};

#endif

#endif

#ifdef ONLY_MY_ENVIR
#include "Timer.h"
#endif

#ifdef ONLY_MY_ENVIR

using namespace std::chrono;

Timer::Timer()
	: start(system_clock::now()) {
}

void Timer::set(std::int64_t time_microsec) {
	limit_microsec += time_microsec;
}

bool Timer::elapsed() const {
	return getMicrosec() >= limit_microsec;
}

std::int64_t Timer::getMicrosec() const {
	return duration_cast<microseconds>(system_clock::now() - start).count();
}

#else

const std::uint64_t Timer::ClocksPerMicrosec = 2987;

std::uint64_t Timer::getClocks() const {
	unsigned int lo, hi;
	__asm__ volatile ("rdtsc" : "=a" (lo), "=d" (hi));
	return ((std::uint64_t)hi << 32) | lo;
}

Timer::Timer() 
	: start_clocks(getClocks()), limit_clocks(start_clocks) {
}

void Timer::set(std::int64_t time_microsec) {
	limit_clocks += time_microsec * ClocksPerMicrosec;
}

bool Timer::elapsed() const {
	return getClocks() >= limit_clocks;
}

std::int64_t Timer::getMicrosec() const {
	return (getClocks() - start_clocks) / ClocksPerMicrosec;
}

#endif

#ifndef RANDOM_H
#define RANDOM_H

#include <cassert>
#include <cstdint>
#include <utility>
#include <vector>

class Random {
	std::uint32_t seed_;

public:
	Random(std::uint32_t seed = 3141592653ul);

	std::uint32_t rnd();
	std::uint32_t rnd(std::uint32_t max);

	// [min, max) の一様乱数
	std::uint32_t rnd(std::uint32_t min, std::uint32_t max);

	template <class Container>
	auto sample(const Container& arr) -> decltype(arr[0]);
	template <class Container>
	void shuffle(Container& arr);

	template <class T>
	std::vector<T> generateVector(int size, std::uint32_t max);
	template <class T>
	std::vector<T> generateVector(int size, std::int32_t min, std::int32_t max);
};

template <class Container>
auto Random::sample(const Container& arr) -> decltype(arr[0]) {
	assert(!arr.empty());
	return arr[rnd(arr.size())];
}

template <class Container>
void Random::shuffle(Container& arr) {
	for (int i = std::size(arr); i > 1; --i) {
		std::swap(arr[i - 1], arr[rnd(i)]);
	}
}

template <class T>
std::vector<T> Random::generateVector(int size, std::uint32_t max) {
	std::vector<T> ret(size);
	for (int i = 0; i < size; ++i) {
		ret[i] = rnd(max);
	}
	return ret;
}

template <class T>
std::vector<T> Random::generateVector(int size, std::int32_t min, std::int32_t max) {
	assert(min < max);
	std::vector<T> ret(size);
	for (int i = 0; i < size; ++i) {
		ret[i] = min + (std::int64_t)rnd(std::int64_t(max) - min);
	}
	return ret;
}

#endif
#ifdef ONLY_MY_ENVIR
#include "Random.h"
#endif

Random::Random(std::uint32_t seed) :
	seed_(seed) {
	assert(seed != 0);
}

std::uint32_t Random::rnd() {
	seed_ ^= seed_ << 13;
	seed_ ^= seed_ >> 17;
	seed_ ^= seed_ << 15;
	return seed_;
}

std::uint32_t Random::rnd(std::uint32_t max) {
	return rnd() % max;
}

std::uint32_t Random::rnd(std::uint32_t min, std::uint32_t max) {
	assert(min < max);
	return min + rnd(max - min);
}

#ifndef __COMPRESSOR_H__
#define __COMPRESSOR_H__

/* updated: 2021-07-13 */

#include <cstdint>
#include <vector>
#include <map>
#include <functional>

/* 座標圧縮を行うクラス */
/* クラス T は比較可能である必要がある */
/* add(要素追加) -> execute(対応づけ) -> get(ID取得) という流れ */
template <class T, class Pred = std::less<T>>
class Compressor {
	using Dict = std::map<T, std::int32_t, Pred>;
	Dict dict_;					// 要素 -> ID
	std::vector<T> objects_;		// ID -> 要素

public:
	Compressor() = default;
	explicit Compressor(const Pred& pred);
	void add(const T& object);
	void execute();
	std::int32_t getId(const T& object) const;
	const T& getObject(std::int32_t id) const;
	int size() const;

	std::int32_t lowerBound(const T& object) const;
	std::int32_t upperBound(const T& object) const;
};

/* 比較関数により初期化するときに用いるコンストラクタ */
template<class T, class Pred>
Compressor<T, Pred>::Compressor(const Pred& pred) 
	: dict_(pred) {
}

/* 要素を登録する O(log n) */
template <class T, class Pred>
void Compressor<T, Pred>::add(const T& object) {
	dict_.emplace(object, std::int32_t());
}

/* 各要素に座標圧縮後の ID を対応づける O(n) */
template <class T, class Pred>
void Compressor<T, Pred>::execute() {
	objects_.reserve(dict_.size());
	std::int32_t current = std::int32_t();
	for (auto&& pair : dict_) {
		pair.second = current;
		objects_.push_back(pair.first);
		++current;
	}
}

/* 各要素に対応付けられた ID を得る O(log n) */
/* 存在しない場合は例外を投げる */
template <class T, class Pred>
std::int32_t Compressor<T, Pred>::getId(const T& object) const {
	return dict_.at(object);
}

/* 圧縮圧縮後の ID に対応する要素を得る O(1) */
template <class T, class Pred>
const T& Compressor<T, Pred>::getObject(std::int32_t id) const {
	return objects_[id];
}

/* 現在登録されている要素数を取得 */
template <class T, class Pred>
int Compressor<T, Pred>::size() const {
	return dict_.size();
}

/* object 以上の要素で最小のものの ID を取得 O(log n) */
/* object 以上の要素がない場合 size() を返す */
template<class T, class Pred>
std::int32_t Compressor<T, Pred>::lowerBound(const T& object) const {
	auto it = dict_.lower_bound(object);
	if (it == dict_.end()) return size();
	return it->second;
}

/* object より大きい要素で最小のものの ID を取得 O(log n) */
/* object より大きい要素がない場合 size() を返す */
template<class T, class Pred>
std::int32_t Compressor<T, Pred>::upperBound(const T& object) const {
	auto it = dict_.upper_bound(object);
	if (it == dict_.end()) return size();
	return it->second;
}

template <class T, class Pred>
std::vector<std::int32_t> compress(const std::vector<T>& arr, Pred pred);
template <class T>
std::vector<std::int32_t> compress(const std::vector<T>& arr);

/* 配列の各要素を座標圧縮した結果を返す O(n log n) */
template <class T, class Pred>
std::vector<std::int32_t> compress(const std::vector<T>& arr, Pred pred) {
	/* 要素を全て登録 */
	Compressor<T, Pred> compressor(pred);
	for (const T& object : arr) {
		compressor.add(object);
	}
	compressor.execute();
	
	/* 各要素に対応づけられた ID を得る */
	std::vector<std::int32_t> ret;
	ret.reserve(arr.size());
	for (const T& object : arr) {
		std::int32_t id = compressor.getId(object);
		ret.push_back(id);
	}
	return ret;
}

template <class T>
std::vector<std::int32_t> compress(const std::vector<T>& arr) {
	return compress(arr, std::less<T>());
}

#endif


#ifndef __ACCUMULATOR_H__
#define __ACCUMULATOR_H__

/* updated: 2020-08-02 */

#include <cassert>
#include <vector>
#include <algorithm>

template <class T>
class Accumulator2D {
	int height_ = 0;
	int width_ = 0;
	std::vector<std::vector<T>> sum_;

	bool is_calculated = false;

public:
	Accumulator2D();
	explicit Accumulator2D(int height, int width);
	explicit Accumulator2D(const std::vector<std::vector<T>>& arr);
	void initialize(int height, int width);
	void initialize(const std::vector<std::vector<T>>& arr);
	void add(int i, int j, const T& increment);
	void execute();
	T get(int i, int j) const;
	T get(int ai, int aj, int bi, int bj) const;
};

template<class T>
Accumulator2D<T>::Accumulator2D() 
	: Accumulator2D(0, 0) {
}

template<class T>
Accumulator2D<T>::Accumulator2D(int height, int width) {
	initialize(height, width);
}

template <class T>
Accumulator2D<T>::Accumulator2D(const std::vector<std::vector<T>>& arr)	{
	initialize(arr);
}

template<class T>
void Accumulator2D<T>::initialize(int height, int width) {
	height_ = height;
	width_ = width;
	sum_.assign(height_ + 1, std::vector<T>(width_ + 1, T()));

	is_calculated = false;
}

template<class T>
void Accumulator2D<T>::initialize(const std::vector<std::vector<T>>& arr) {
	int height = arr.size();
	int width = height == 0 ? 0 : arr.front().size();
	initialize(height, width);

	/* 累積和をとるとき in_-place にできるように1つ添字をずらしておく */
	for (int i = 0; i < height_; ++i) {
		for (int j = 0; j < width_; ++j) {
			sum_[i + 1][j + 1] = arr[i][j];
		}
	}

	is_calculated = false;
}

/* 要素 (i, j) の値を increment だけ増加させる (累積和の計算前) O(1) */
template<class T>
void Accumulator2D<T>::add(int i, int j, const T& increment) {
	assert(i >= 0 && i < height_);
	assert(j >= 0 && j < width_);
	sum_[i + 1][j + 1] += increment;
}

/* 累積和を計算する O(H * W) */
template<class T>
void Accumulator2D<T>::execute() {
	for (int i = 0; i < height_; ++i) {
		for (int j = 0; j < width_; ++j) {
			sum_[i + 1][j + 1] += sum_[i][j + 1] + sum_[i + 1][j] - sum_[i][j];
		}
	}

	is_calculated = true;
}

/* 領域 [0, i) * [0, j) 内の要素の和を得る O(1) */
template <class T>
T Accumulator2D<T>::get(int i, int j) const {
	assert(is_calculated);

	int new_i = std::max(0, std::min(height_, i));
	int new_j = std::max(0, std::min(width_, j));
	return sum_[new_i][new_j];
}

/* 領域 [ai, bi) * [aj, bj) 内の要素の和を得る O(1) */
template <class T>
T Accumulator2D<T>::get(int ai, int aj, int bi, int bj) const {
	assert(is_calculated);

	return get(ai, aj) - get(ai, bj) - get(bi, aj) + get(bi, bj);
}

#endif

#ifndef __MAIN_H__
#define __MAIN_H__

#ifndef ONLY_MY_ENVIR
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cassert>
#include <iostream>
#include <string>
#include <vector>
#include <list>
#include <utility>
#include <algorithm>
#include <functional>
#include <cmath>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <iomanip>
#include <sstream>
#include <bitset>
#include <limits>
#include <numeric>
#include <valarray>
#include <fstream>
#include <array>
#include <random>
#include <unordered_set>
#include <unordered_map>
#endif

#ifdef ONLY_MY_ENVIR
#include "Includes.h"
#endif

using namespace std;
using uint = std::uint32_t;
using LL = std::int64_t;
using ULL = std::uint64_t;
using PP = pair<LL, LL>;
template <typename T> using PriorityQ = priority_queue<T, vector<T>, greater<T> >;
#define REP(i, a, n) for(LL i = (a), i##_max_ = (n); i < i##_max_; ++i)
#define REM(i, a, n) for(LL i = (LL)(n) - 1, i##_min_ = (a); i >= i##_min_; --i)
#define FLOAT fixed << setprecision(16)
#define SPEEDUP { cin.tie(NULL); ios::sync_with_stdio(false); }
const int INF = 0x3FFFFFFF;
const LL INFLL = 0x3FFFFFFF3FFFFFFF;
const double INFD = 1.0e+308;
const double EPS = 1.0e-9;

void YesNo(bool b) { cout << (b ? "Yes" : "No") << endl; }
void YESNO(bool b) { cout << (b ? "YES" : "NO") << endl; }
template <class T, class U> istream& operator>>(istream& ist, pair<T, U>& right) { return ist >> right.first >> right.second; }
template <class T, class U> ostream& operator<<(ostream& ost, const pair<T, U>& right) { return ost << right.first << ' ' << right.second; }
template <class T, class TCompatible, size_t N> void Fill(T(&dest)[N], const TCompatible& val) { fill(dest, dest + N, val); }
template <class T, class TCompatible, size_t M, size_t N> void Fill(T(&dest)[M][N], const TCompatible& val) { for (int i = 0; i < M; ++i) Fill(dest[i], val); }
template <class T> T Next() { T buf; cin >> buf; return buf; }
istream& Ignore(istream& ist) { string s; ist >> s; return ist; }
bool Inside(int i, int j, int h, int w) { return i >= 0 && i < h&& j >= 0 && j < w; }
void pL() { std::cout << std::endl; }
template <class Head> void pL(Head&& head) { std::cout << head << std::endl; }
template <class Head, class... Tail> void pL(Head&& head, Tail&&... tail) { std::cout << head << ' '; pL(std::forward<Tail>(tail)...); }

#ifdef __GNUC__
using LLL = __int128;
istream& operator>>(istream& ist, __int128& val) { LL tmp; ist >> tmp; val = tmp; return ist; }
ostream& operator<<(ostream& ost, __int128 val) { LL tmp = val; ost << tmp; return ost; }
#else
using LLL = LL;
#endif

#endif
#ifdef ONLY_MY_ENVIR
#include "Main.h"

std::ifstream input_stream("ain.txt");
std::ofstream output_stream("aout.txt");
#define cin input_stream
#define cout output_stream
#endif

constexpr int dmax = 10;
constexpr int lmax = 100;
constexpr int rad = 10000;
int n, kmax;
int a[dmax];
int x[10000];
int y[10000];
Compressor<int> xcmp;
Compressor<int> ycmp;

using Pos = pair<int, int>;
using Line = pair<Pos, Pos>;
Line hLine(int x) { return { { x - 1, -rad }, { x, rad } }; }
Line vLine(int y) { return { { -rad, y - 1 }, { rad, y } }; }

void input() {
    cin >> n >> kmax;
    REP(d, 0, dmax) cin >> a[d];
    REP(i, 0, n) cin >> x[i] >> y[i];
}

void output(const vector<Line>& ls) {
    cout << ls.size() << endl;
    for (auto&& l : ls) {
        cout
            << l.first.first << ' '
            << l.first.second << ' '
            << l.second.first << ' '
            << l.second.second << endl;
    }
}

void comp() {
    xcmp.add(-rad);
    ycmp.add(-rad);
    xcmp.add(rad);
    ycmp.add(rad);
    REP(i, 0, n) {
        xcmp.add(x[i]);
        ycmp.add(y[i]);
    }
    xcmp.execute();
    ycmp.execute();
}

class Histogram {
    vector<int> arr_;
    int size_ = 0;

    vector<pair<int, int>> history_;
    int psize_ = 0;

public:
    Histogram()
        : arr_(10000)
    {
        history_.reserve(200);
    }

    int get(int index) const {
        return arr_[index];
    }

    void add(int index, int value) {
        arr_[index] += value;
        
        if (value != 0) {
            history_.emplace_back(index, value);
            update(index);
        }
    }

    int size() const {
        return size_;
    }

    void save() {
        history_.clear();
        psize_ = size_;
    }

    void restore() {
        for (auto&& p : history_) {
            arr_[p.first] -= p.second;
        }
        history_.clear();
        size_ = psize_;
    }

private:
    void update(int index) {
        if (index < size_ - 1) {
            return;
        } else if (index == size_ - 1) {
            while (index >= 0 && arr_[index] == 0) {
                --size_;
                --index;
            }
        } else {
            size_ = index + 1;
        }
    }
};

class Helper {
    Random rnd_;
    int score_ = 0;
    int pscore_ = 0;

    int h = 0;
    int w = 0;
    Accumulator2D<short> acc;
    vector<int> amod;

    vector<int> xs;
    vector<int> ys;
    Histogram histo;

    vector<int> best_xs;
    vector<int> best_ys;
    int mn_loss = 10;

public:
    void init() {
        acc = Accumulator2D<short>(xcmp.size(), ycmp.size());
        int need = accumulate(a, a + dmax, 0);
        int xnum = 0;
        int ynum = 0;
        REP(i, 2, lmax) {
            xnum = i;
            ynum = need * 1.2 / i;
            if (xnum + ynum - 2 <= lmax) {
                ynum = lmax + 2 - xnum;
                break;
            }
        }

        amod.resize(dmax + 1);
        REP(i, 0, dmax) amod[i + 1] = a[i] * (i + 1);
        REP(i, 0, n) acc.add(xcmp.getId(x[i]), ycmp.getId(y[i]), 1);
        acc.execute();

        h = xcmp.size() - 1;
        w = ycmp.size() - 1;
        REP(i, 0, xnum + 1) xs.push_back(h * i / xnum);
        REP(j, 0, ynum + 1) ys.push_back(w * j / ynum);

        initState();
        score_ = calcScore();
    }

    vector<Line> get() {
        vector<Line> ret;
        auto&& cxs = best_xs.empty() ? xs : best_xs;
        auto&& cys = best_ys.empty() ? ys : best_ys;
        REP(i, 1, cxs.size() - 1) ret.push_back(hLine(xcmp.getObject(cxs[i])));
        REP(j, 1, cys.size() - 1) ret.push_back(vLine(ycmp.getObject(cys[j])));
        return ret;
    }

    void solve() {
        const int iterations = 5e6;
        const int limit = 2990000;
        const double tmp_start = 500;
        const double tmp_finish = 1;
        double tmp = tmp_start;
        double ratio = 0.0;

        Timer timer;
        timer.set(limit);

        init();

        int z = 0;
#if ONLY_MY_ENVIR
        while (z < iterations) {
#else
        while (z % 1024 != 0 || !timer.elapsed()) {
#endif
            ++z;
            if (z % 1024 == 0) {
#if ONLY_MY_ENVIR
                ratio = double(z) / iterations;
#else
                ratio = double(timer.getMicrosec()) / limit;
#endif
                tmp = tmp_start * std::pow(tmp_finish / tmp_start, ratio);
                if (z % 65536 == 0) {
                    //cerr << tmp << ' ' << score_ << endl;
                }
            }

            int delta = step();
            if (!isAccepted(delta, tmp)) {
                undo();
            } else {
                if (ratio > 0.9) {
                    int loss = calcLoss();
                    if (loss < mn_loss) {
                        mn_loss = loss;
                        best_xs = xs;
                        best_ys = ys;
                    }
                }
            }

            if (score_ == 0) {
                break;
            }
        }
        cerr << z << endl;
        return;
        }

private:
    bool isAccepted(double del, double tmp) {
        return del <= 0 || (del <= 8 * tmp && rnd_.rnd() < std::exp(-del / tmp) * (1ll << 32));
    }

    int mt = 0;
    int mdir = 0;
    int mi = 0;
    int mj = 0;
    int mni = 0;
    int mnj = 0;
    int mx = 0;
    int my = 0;
    int step() {
        histo.save();

        int xlines = xs.size() - 2;
        int ylines = ys.size() - 2;

        int t = rnd_.rnd(2);
        mt = t;
        if (t == 0) {
            int p = rnd_.rnd(xlines + ylines);
            int d = (rnd_.rnd(2) ? 1 : -1) * rnd_.rnd(10);

            if (p < xlines) {
                mdir = 0;
                int i = p + 1;
                mi = i;
                mx = xs[i];
                changeX(i, min(max(xs[i] + d, xs[i - 1]), xs[i + 1]));
            } else {
                mdir = 1;
                int j = p - xlines + 1;
                mj = j;
                my = ys[j];
                changeY(j, min(max(ys[j] + d, ys[j - 1]), ys[j + 1]));
            }
        } else {
            int p = rnd_.rnd(xlines + ylines);

            if (p < xlines) {
                mdir = 0;
                int i = p + 1;
                if (xs[i - 1] < xs[i] && xs[i] < xs[i + 1]) return 0;
                int nx = rnd_.rnd(h - 1) + 1;
                mi = i;
                mx = xs[i];
                eraseX(i);
                int ni = lower_bound(xs.begin(), xs.end(), nx) - xs.begin();
                mni = ni;
                insertX(ni, nx);
            } else {
                mdir = 1;
                int j = p - xlines + 1;
                if (ys[j - 1] < ys[j] && ys[j] < ys[j + 1]) return 0;
                int ny = rnd_.rnd(w - 1) + 1;
                mj = j;
                my = ys[j];
                eraseY(j);
                int nj = lower_bound(ys.begin(), ys.end(), ny) - ys.begin();
                mnj = nj;
                insertY(nj, ny);
            }
        }

        pscore_ = score_;
        score_ = calcScore();
        return score_ - pscore_;
    }

    void undo() {
        if (mt == 0) {
            if (mdir == 0) {
                xs[mi] = mx;
            } else {
                ys[mj] = my;
            }
        } else {
            if (mdir == 0) {
                eraseXSub(mni);
                insertXSub(mi, mx);
            } else {
                eraseYSub(mnj);
                insertYSub(mj, my);
            }
        }
        histo.restore();
        score_ = pscore_;
    }

    void changeX(int i, int nx) {
        int l = 0;
        int r = 0;
        int s = 0;
        int t = 0;
        REP(j, 1, ys.size()) {
            int a = acc.get(xs[i - 1], ys[j]);
            int b = acc.get(xs[i], ys[j]);
            int c = acc.get(xs[i + 1], ys[j]);
            int d = acc.get(nx, ys[j]);

            int nl = b - a;
            int nr = c - b;
            int ns = d - a;
            int nt = c - d;
            histo.add((nl - l), -(nl - l));
            histo.add((nr - r), -(nr - r));
            histo.add((ns - s), (ns - s));
            histo.add((nt - t), (nt - t));
            l = nl;
            r = nr;
            s = ns;
            t = nt;
        }
        xs[i] = nx;
    }

    void changeY(int j, int ny) {
        int l = 0;
        int r = 0;
        int s = 0;
        int t = 0;
        REP(i, 1, xs.size()) {
            int a = acc.get(xs[i], ys[j - 1]);
            int b = acc.get(xs[i], ys[j]);
            int c = acc.get(xs[i], ys[j + 1]);
            int d = acc.get(xs[i], ny);

            int nl = b - a;
            int nr = c - b;
            int ns = d - a;
            int nt = c - d;
            histo.add((nl - l), -(nl - l));
            histo.add((nr - r), -(nr - r));
            histo.add((ns - s), (ns - s));
            histo.add((nt - t), (nt - t));
            l = nl;
            r = nr;
            s = ns;
            t = nt;
        }
        ys[j] = ny;
    }

    void eraseX(int i) {
        int l = 0;
        int r = 0;
        REP(j, 1, ys.size()) {
            int a = acc.get(xs[i - 1], ys[j]);
            int b = acc.get(xs[i], ys[j]);
            int c = acc.get(xs[i + 1], ys[j]);

            int nl = b - a;
            int nr = c - b;
            histo.add((nl - l), -(nl - l));
            histo.add((nr - r), -(nr - r));
            histo.add((nl + nr) - (l + r), (nl + nr) - (l + r));
            l = nl;
            r = nr;
        }
        eraseXSub(i);
    }

    void eraseY(int j) {
        int l = 0;
        int r = 0;
        REP(i, 1, xs.size()) {
            int a = acc.get(xs[i], ys[j - 1]);
            int b = acc.get(xs[i], ys[j]);
            int c = acc.get(xs[i], ys[j + 1]);

            int nl = b - a;
            int nr = c - b;
            histo.add((nl - l), -(nl - l));
            histo.add((nr - r), -(nr - r));
            histo.add((nl + nr) - (l + r), (nl + nr) - (l + r));
            l = nl;
            r = nr;
        }
        eraseYSub(j);
    }

    void insertX(int i, int nx) {
        int l = 0;
        int r = 0;
        REP(j, 1, ys.size()) {
            int a = acc.get(xs[i - 1], ys[j]);
            int b = acc.get(nx, ys[j]);
            int c = acc.get(xs[i], ys[j]);

            int nl = b - a;
            int nr = c - b;
            histo.add((nl - l), (nl - l));
            histo.add((nr - r), (nr - r));
            histo.add((nl + nr) - (l + r), -((nl + nr) - (l + r)));
            l = nl;
            r = nr;
        }
        insertXSub(i, nx);
    }

    void insertY(int j, int ny) {
        int l = 0;
        int r = 0;
        REP(i, 1, xs.size()) {
            int a = acc.get(xs[i], ys[j - 1]);
            int b = acc.get(xs[i], ny);
            int c = acc.get(xs[i], ys[j]);

            int nl = b - a;
            int nr = c - b;
            histo.add((nl - l), (nl - l));
            histo.add((nr - r), (nr - r));
            histo.add((nl + nr) - (l + r), -((nl + nr) - (l + r)));
            l = nl;
            r = nr;
        }
        insertYSub(j, ny);
    }

    void eraseXSub(int i) {
        xs.erase(xs.begin() + i);
    }

    void eraseYSub(int j) {
        ys.erase(ys.begin() + j);
    }

    void insertXSub(int i, int nx) {
        xs.insert(xs.begin() + i, nx);
    }

    void insertYSub(int j, int ny) {
        ys.insert(ys.begin() + j, ny);
    }

    void initState() {
        REP(i, 1, xs.size()) {
            REP(j, 1, ys.size()) {
                int c = acc.get(xs[i - 1], ys[j - 1], xs[i], ys[j]);
                histo.add(c, c);
            }
        }
    }

    double calcScore() const {
        int sum = 0;
        REP(i, 1, dmax + 1) {
            int d = (amod[i] - histo.get(i)) / i;
            sum += d * d;
        }
        REP(i, dmax + 1, histo.size()) {
            int d = histo.get(i) / i;
            sum += d * d;
        }

        {
            int i = 1;
            int j = 1;
            int x = amod[i];
            int y = histo.get(j);
            while (true) {
                int mn = min(x, y);
                x -= mn;
                y -= mn;
                sum += mn * (j - i) * (j - i);
                if (x == 0) {
                    ++i;
                    if (i >= amod.size()) break;
                    x = amod[i];
                }
                if (y == 0) {
                    ++j;
                    y = histo.get(j);
                }
            }
        }
        return sum;
    }

    int calcLoss() const {
        int sum = 0;
        REP(i, 1, dmax + 1) {
            sum += std::max<int>(0, (amod[i] - histo.get(i)) / i);
        }
        return sum;
    }
};

int main() {
    input();
    comp();
    Helper helper;
    helper.solve();
    auto res = helper.get();
    output(res);
    return 0;
}

// Included Files: 
//   * Timer.h
//   * Timer.cpp
//   * Random.h
//   * Random.cpp
//   * Compressor.h
//   * Accumulator.h
//   * Main.h
//   * Main.cpp

Submission Info

Compile Error

./Main.cpp: In member function ‘void Helper::solve()’:
./Main.cpp:664:19: warning: unused variable ‘iterations’ [-Wunused-variable]
  664 |         const int iterations = 5e6;
      |                   ^~~~~~~~~~
./Main.cpp: In member function ‘double Helper::calcScore() const’:
./Main.cpp:986:27: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<int>::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
  986 |                     if (i >= amod.size()) break;
      |                         ~~^~~~~~~~~~~~~~

Judge Result