結果
| 問題 |
No.5016 Worst Mayor
|
| コンテスト | |
| ユーザー |
 mai
|
| 提出日時 | 2023-04-29 18:28:41 |
| 言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
| 結果 |
RE
|
| 実行時間 | - |
| コード長 | 22,330 bytes |
| コンパイル時間 | 4,390 ms |
| コンパイル使用メモリ | 256,228 KB |
| 実行使用メモリ | 24,468 KB |
| スコア | 0 |
| 平均クエリ数 | 101.00 |
| 最終ジャッジ日時 | 2023-04-29 18:29:18 |
| 合計ジャッジ時間 | 34,999 ms |
|
ジャッジサーバーID （参考情報） |
judge14 / judge13 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | RE * 50 |
ソースコード
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
// clang-format off
using namespace std;
using ll = long long int;
#define all(v) (v).begin(),(v).end()
#define repeat(cnt,l) for(typename remove_const<typename remove_reference<decltype(l)>::type>::type cnt={};(cnt)<(l);++(cnt))
#define rrepeat(cnt,l) for(auto cnt=(l)-1;0<=(cnt);--(cnt))
#define iterate(cnt,b,e) for(auto cnt=(b);(cnt)!=(e);++(cnt))
#define upto(cnt,b,e,step) for(auto cnt=(b);(cnt)<=(e);(cnt)+=(step))
#define downto(cnt,b,e,step) for(auto cnt=(b);(e)<=(cnt);(cnt)-=(step))
const long long MD = 998244353; const long double PI = 3.1415926535897932384626433832795L;
template<typename T1, typename T2> inline ostream& operator <<(ostream &o, const pair<T1, T2> p) { o << '(' << p.first << ':' << p.second << ')'; return o; }
template<typename T> inline T& chmax(T& to, const T& val) { return to = max(to, val); }
template<typename T> inline T& chmin(T& to, const T& val) { return to = min(to, val); }
void bye(string s, int code = 0) { cout << s << endl; exit(code); }
mt19937_64 randdev(8901016);
template<typename T, typename Random = decltype(randdev), typename enable_if<is_integral<T>::value>::type* = nullptr>
inline T rand(T l, T h, Random& rand = randdev) { return uniform_int_distribution<T>(l, h)(rand); }
template<typename T, typename Random = decltype(randdev), typename enable_if<is_floating_point<T>::value>::type* = nullptr>
inline T rand(T l, T h, Random& rand = randdev) { return uniform_real_distribution<T>(l, h)(rand); }template<typename T>
static ostream& operator<<(ostream& o, const std::vector<T>& v) {
o << "[ "; for(const auto& e : v) o<<e<<' '; return o << ']';
}
template <typename I> struct MyRangeFormat{ I b,e; MyRangeFormat(I _b, I _e):b(_b),e(_e){} };
template<typename I> static ostream& operator<<(ostream& o, const MyRangeFormat<I>& f) {
o << "[ "; iterate(i,f.b,f.e) o<<*i<<' '; return o << ']';
}
template <typename I> struct MyMatrixFormat{
const I& p; long long n, m;
MyMatrixFormat(const I& _p, long long _n, long long _m):p(_p),n(_n),m(_m){}
};
template<typename I> static ostream& operator<<(ostream& o, const MyMatrixFormat<I>& f) {
o<<'\n'; repeat(i,(f.n)) { repeat(j,f.m) o<<f.p[i][j]<<' '; o<<'\n'; }
return o;
}
struct LOG_t { ~LOG_t() { clog << endl; } };
#define LOG (LOG_t(),clog<<'L'<<__LINE__<<": ")
#define FMTA(m,w) (MyRangeFormat<decltype(m+0)>(m,m+w))
#define FMTR(b,e) (MyRangeFormat<decltype(e)>(b,e))
#define FMTV(v) FMTR(v.begin(),v.end())
#define FMTM(m,h,w) (MyMatrixFormat<decltype(m+0)>(m,h,w))
#if defined(_WIN32) || defined(_WIN64)
#define getc_x _getc_nolock
#define putc_x _putc_nolock
#elif defined(__GNUC__)
#define getc_x getc_unlocked
#define putc_x putc_unlocked
#else
#define getc_x getc
#define putc_x putc
#endif
class MaiScanner {
FILE* fp_;
constexpr bool isvisiblechar(char c) noexcept { return (0x21<=(c)&&(c)<=0x7E); }
public:
inline MaiScanner(FILE* fp):fp_(fp){}
template<typename T> void input_integer(T& var) noexcept {
var = 0; T sign = 1;
int cc = getc_x(fp_);
for (; cc < '0' || '9' < cc; cc = getc_x(fp_))
if (cc == '-') sign = -1;
for (; '0' <= cc && cc <= '9'; cc = getc_x(fp_))
var = (var << 3) + (var << 1) + cc - '0';
var = var * sign;
}
inline int c() noexcept { return getc_x(fp_); }
template<typename T, typename enable_if<is_integral<T>::value, nullptr_t>::type = nullptr>
inline MaiScanner& operator>>(T& var) noexcept { input_integer<T>(var); return *this; }
inline MaiScanner& operator>>(string& var) {
int cc = getc_x(fp_);
for (; !isvisiblechar(cc); cc = getc_x(fp_));
for (; isvisiblechar(cc); cc = getc_x(fp_))
var.push_back(cc);
return *this;
}
template<typename IT> inline void in(IT begin, IT end) { for (auto it = begin; it != end; ++it) *this >> *it; }
};
class MaiPrinter {
FILE* fp_;
public:
inline MaiPrinter(FILE* fp):fp_(fp){}
template<typename T>
void output_integer(T var) noexcept {
if (var == 0) { putc_x('0', fp_); return; }
if (var < 0)
putc_x('-', fp_),
var = -var;
char stack[32]; int stack_p = 0;
while (var)
stack[stack_p++] = '0' + (var % 10),
var /= 10;
while (stack_p)
putc_x(stack[--stack_p], fp_);
}
inline MaiPrinter& operator<<(char c) noexcept { putc_x(c, fp_); return *this; }
template<typename T, typename enable_if<is_integral<T>::value, nullptr_t>::type = nullptr>
inline MaiPrinter& operator<<(T var) noexcept { output_integer<T>(var); return *this; }
inline MaiPrinter& operator<<(const char* str_p) noexcept { while (*str_p) putc_x(*(str_p++), fp_); return *this; }
inline MaiPrinter& operator<<(const string& str) {
const char* p = str.c_str();
const char* l = p + str.size();
while (p < l) putc_x(*p++, fp_);
return *this;
}
template<typename IT> void join(IT begin, IT end, char sep = ' ') { for (bool b = 0; begin != end; ++begin, b = 1) b ? *this << sep << *begin : *this << *begin; }
};
MaiScanner scanner(stdin);
MaiPrinter printer(stdout);
// clang-format on
template <typename C = std::chrono::milliseconds> class Timer {
std::chrono::system_clock::time_point tp_;
public:
static inline auto now() { return std::chrono::system_clock::now(); }
inline void tic() { tp_ = now(); }
inline auto toc() const {
return std::chrono::duration_cast<C>(now() - tp_).count();
}
inline Timer() : tp_(now()) {}
};
inline std::ostream &operator<<(std::ostream &o, const Timer<> &t) {
return o << (long long)t.toc();
}
struct P {
using T = int;
T y, x;
inline explicit P(T _y, T _x) : y(_y), x(_x) {}
inline P() : y(0), x(0) {}
inline bool operator==(P p) const { return y == p.y && x == p.x; }
inline bool operator<(P p) const { return y == p.y ? x < p.x : y < p.y; }
inline P operator+(P p) const { return P(y + p.y, x + p.x); }
inline P operator-(P p) const { return P(y - p.y, x - p.x); }
inline P &operator+=(P p) {
y += p.y;
x += p.x;
return *this;
}
inline P &operator-=(P p) {
y -= p.y;
x -= p.x;
return *this;
}
inline P &operator*=(T m) {
y *= m;
x *= m;
return *this;
}
inline T distM(P p) const { return abs(y - p.y) + abs(x - p.x); }
inline T distC(P p) const { return max(abs(y - p.y), abs(x - p.x)); }
template <typename ITR> ITR nearestM(ITR begin, ITR end) const {
if (begin == end)
return end;
T best = distM(*begin);
ITR besti = begin;
for (ITR it = begin; ++it, it != end;) {
T m = distM(*it);
if (best < m) {
best = m;
besti = it;
}
}
return besti;
}
};
inline ostream &operator<<(ostream &os, P p) {
os << '(' << p.y << ',' << p.x << ')';
return os;
}
const P FourMoving[] = {P(-1, 0), P(0, 1), P(1, 0), P(0, -1)};
const P FiveMoving[] = {P(-1, 0), P(0, 1), P(1, 0), P(0, -1), P(0, 0)};
const P EightMoving[] = {P(-1, 0), P(0, 1), P(1, 0), P(0, -1),
P(-1, -1), P(-1, 1), P(1, -1), P(1, 1)};
inline P operator*(P::T m, P p) noexcept { return P(m * p.y, m * p.x); }
template <typename T>
// using T = int;
struct F {
int height, width;
vector<T> data;
explicit F(int h, int w) : height(h), width(w), data(h * w) {}
F() : F(1, 1) {}
inline bool safe(int y, int x) const {
return 0 <= y && y < height && 0 <= x && x < width;
}
inline bool safe(P p) const {
return 0 <= p.y && p.y < height && 0 <= p.x && p.x < width;
}
#if 1
void assert_safe(int y, int x) const {
if (!safe(y, x)) {
clog << "assertion failed: field=" << height << "x" << width
<< ": try=" << y << "," << x << endl;
assert(safe(y, x));
}
}
inline T &operator()(int y, int x) {
assert_safe(y, x);
return data[x + y * width];
}
inline T &operator()(P p) {
assert_safe(p.y, p. x);
return data[p.x + p.y * width];
}
inline T operator()(int y, int x) const {
assert_safe(y, x);
return data[x + y * width];
}
inline T operator()(P p) const {
assert_safe(p.y, p.x);
return data[p.x + p.y * width];
}
#else
inline T &operator()(int y, int x) { return data[x + y * width]; }
inline T &operator()(P p) { return data[p.x + p.y * width]; }
inline T operator()(int y, int x) const { return data[x + y * width]; }
inline T operator()(P p) const { return data[p.x + p.y * width]; }
#endif
inline T getA(int i) const { return data[i]; }
inline T &getAmut(int i) { return data[i]; }
inline void fill(T e) { std::fill(data.begin(), data.end(), e); }
inline void resize(int h, int w) {
height = h;
width = w;
data.resize(h * w);
}
void print(ostream &os, int setw_arg = 4) {
for (int y = 0; y < height; ++y) {
for (int x = 0; x < width; ++x)
os << setw(setw_arg) << operator()(y, x) << ' ';
os << '\n';
}
}
};
class Graph2d {
public:
using W_T = int;
int n;
vector<W_T> matrix;
explicit Graph2d(int size) : n(size), matrix(size * size){};
inline int size() const { return n; }
void resize(int s) {
n = s;
matrix.resize(n * n);
}
void resize(int s, W_T val) {
n = s;
matrix.resize(n * n, val);
}
inline W_T& at(int y, int x) { return matrix[y * n + x]; }
inline W_T& operator()(int y, int x) { return matrix[y * n + x]; }
inline W_T at(int y, int x) const { return matrix[y * n + x]; }
inline W_T operator()(int y, int x) const { return matrix[y * n + x]; }
inline void connect(int u, int v, W_T dist = 1) { at(u, v) = at(v, u) = dist; }
inline void connect_d(int from, int to, W_T dist = 1) { // directedEdge u->v
at(from, to) = dist;
}
};
void warshall_floyd(Graph2d& g) {
int i, j, k;
for (i = 0; i < g.n; i++) {
for (j = 0; j < g.n; j++) {
for (k = 0; k < g.n; k++) {
g(j, k) = std::min(g(j, k), g(j, i) + g(i, k));
}
}
}
}
class CommandChain {
public:
using Direction = int; // 2bit
struct Node {
Node() : value(0), len(0) {}
void push(Direction dir) {
value |= (uint64_t)(dir & 3) << (uint64_t)len;
len += 2;
}
bool full() const { return len >= 64; }
void dump(vector<int>& out) const {
for (uint64_t p = 0; p < uint64_t(len); p += 2)
out.push_back((value >> p) & 3);
}
int last() const { return (value >> uint64_t(len - 2)) & 3; }
uint64_t value;
int len = 0;
};
static shared_ptr<CommandChain> createEmpty() { return make_shared<CommandChain>(root()); }
static shared_ptr<CommandChain> pushed(shared_ptr<CommandChain>& me, Direction cmd) {
// assert(me.get());
if (me->node_.full()) {
auto new_chain = make_shared<CommandChain>(me);
new_chain->node_.push(cmd);
return new_chain;
} else {
auto copied_chain = make_shared<CommandChain>(*me);
copied_chain->node_.push(cmd);
return copied_chain;
}
}
int last() const { return node_.last(); }
void dumpTo(vector<int>& out) const {
if (prev_.get()) {
prev_->dumpTo(out);
// root does not have value
node_.dump(out);
}
}
vector<int> dump() const {
vector<int> out;
dumpTo(out);
return out;
}
// TODO: make private...
CommandChain(shared_ptr<CommandChain>& prev) : prev_(prev), node_() {}
private:
// friend shared_ptr<CommandChain>;
static shared_ptr<CommandChain>& root() {
static shared_ptr<CommandChain> e(new CommandChain());
return e;
};
shared_ptr<CommandChain> prev_;
Node node_;
CommandChain() : prev_(), node_() {}
};
//
constexpr int N = 14; // N^4 = 38416
constexpr int M = 3000;
constexpr int T = 400;
inline P idx2p(int i) { return P{i / N, i % N}; }
inline int p2idx(P p) { return p.y * N + p.x; }
Timer<> g_timer;
/*
考察
- 愚直に最短距離を計算する場合、warshall-floyd O(N^6) = 7529536 DEKKKA
- ダイクストラ？|V| = N^2, |E| ~= 2|V| = 2N^2,
- 最短経路は、経路上では遠回りになっている可能性がある。1.0 > 0.223*3
- 厳密に計算するならズルできません
- 最適な高速道路を追加する順番が存在する。NPかどうかは知らない
- これを予め計算してFIXすると、コマンドは3つだけになる。
- 平均 0，標準偏差 1 に従う乱数 e p,q
なにこれ？正規分布？
*/
struct Problem {
vector<pair<P, P>> routes_;
void input() {
int m, t;
scanner >> m >> t;
assert(M == m);
assert(T == t);
repeat(i, M) {
int y1, x1, y2, x2;
scanner >> y1 >> x1 >> y2 >> x2;
--y1;
--x1;
--y2;
--x2;
routes_.emplace_back(P{y1, x1}, P{y2, x2});
}
}
void inputGenerated() {
routes_.reserve(N * N * N * N);
repeat(a, N) {
repeat(b, N) {
repeat(c, N) {
repeat(d, N) { routes_.emplace_back(P{a, b}, P{c, d}); }
}
}
}
shuffle(all(routes_), randdev);
routes_.resize(M);
routes_.shrink_to_fit();
}
Graph2d calcDistanceWF(const F<int> &field) const {
Graph2d dist(N * N);
fill(all(dist.matrix), MD);
repeat(pi, N * N) {
const P p = idx2p(pi);
dist(pi, pi) = 0;
if (p.y < N - 1) {
const int c = field(p.y, p.x) & 1 ? 223 : 1000;
dist(pi, pi + N) = c;
dist(pi + N, pi) = c;
}
if (p.x < N - 1) {
const int c = field(p.y, p.x) & 2 ? 223 : 1000;
dist(pi, pi + 1) = c;
dist(pi + 1, pi) = c;
}
}
warshall_floyd(dist);
return dist;
}
vector<int> calcDistance(const F<int> &field, P start) const {
vector<int> dist(N * N, MD);
priority_queue<pair<int, int>> que;
const int starti = p2idx(start);
que.emplace(0, starti);
dist[starti] = 0;
while (!que.empty()) {
const int d = -que.top().first;
const int pi = que.top().second;
que.pop();
if (dist[pi] < d)
continue;
const P p = idx2p(pi);
// 事故りそう
if (p.y > 0) {
int cost = field(p.y - 1, p.x) & 1 ? 223 : 1000;
int d2 = d + cost;
if (dist[pi - N] > d2) {
dist[pi - N] = d2;
que.emplace(-d2, pi - N);
}
}
if (p.x > 0) {
int cost = field(p.y, p.x - 1) & 2 ? 223 : 1000;
int d2 = d + cost;
if (dist[pi - 1] > d2) {
dist[pi - 1] = d2;
que.emplace(-d2, pi - 1);
}
}
if (p.y < N - 1) {
int cost = field(p.y, p.x) & 1 ? 223 : 1000;
int d2 = d + cost;
if (dist[pi + N] > d2) {
dist[pi + N] = d2;
que.emplace(-d2, pi + N);
}
}
if (p.x < N - 1) {
int cost = field(p.y, p.x) & 2 ? 223 : 1000;
int d2 = d + cost;
if (dist[pi + 1] > d2) {
dist[pi + 1] = d2;
que.emplace(-d2, pi + 1);
}
}
}
return dist;
}
};
// 距離から高速道路の使用数を特定する
vector<int> createTableFromDist2Num() {
constexpr int h = N * 2 * 1000;
vector<int> d2n(h, MD);
d2n[0] = 0;
repeat(d, h - 223) {
if (d2n[d] == MD)
continue;
if (d + 1000 < h)
d2n[d + 1000] = d2n[d];
d2n[d + 223] = d2n[d] + 1;
}
return d2n;
}
int dist2NumEdge(int dist) {
static vector<int> table = createTableFromDist2Num();
int n = table[dist];
assert(n < N * N);
return n;
}
struct CommandBuildHighway {
int income;
P pos;
bool horizontal;
};
struct BeamState {
ll heuristic_ = numeric_limits<ll>::min();
ll money_ = 0;
ll income_ = 0;
int turn_ = 0;
int highway_ = 0;
int man_power_ = 1;
// int score_ = numeric_limits<int>::min();
shared_ptr<CommandChain> commands_;
BeamState() : commands_(CommandChain::createEmpty()) {}
bool operator<(const BeamState &another) const {
return heuristic_ < another.heuristic_;
}
void updateHeuristic() {
// TODO:
heuristic_ = income_; // floor(sqrt(man_power_));
}
static BeamState initialState() {
BeamState next;
next.money_ = 1000000;
next.income_ = 0;
next.turn_ = 0;
next.highway_ = 0;
next.man_power_ = 1;
return next;
}
optional<BeamState>
nextStateHighway(const vector<CommandBuildHighway> &command_bh) {
// TODO: check next.highway_ < command_bh.size
if (highway_ + 1 >= command_bh.size())
return optional<BeamState>();
ll cost =
ceil(10000000.0 / sqrt(man_power_)); // floor らしいけど怖いのでceil
if (money_ < cost)
return optional<BeamState>();
BeamState next;
next.money_ = money_;
next.income_ = income_;
next.turn_ = turn_ + 1;
next.highway_ = highway_;
next.man_power_ = man_power_;
// Do
next.money_ -= cost;
next.commands_ = CommandChain::pushed(commands_, 1);
next.highway_ += 1;
next.income_ = ll(command_bh[next.highway_].income) * 60;
// receive income
next.money_ = money_ + next.income_;
next.updateHeuristic();
return optional<BeamState>(next);
}
BeamState nextStateAddManPower() {
// TODO: check next.highway_ < command_bh.size
BeamState next;
next.money_ = money_;
next.income_ = income_;
next.turn_ = turn_ + 1;
next.highway_ = highway_;
next.man_power_ = man_power_;
// Do
next.commands_ = CommandChain::pushed(commands_, 2);
next.man_power_ += 1;
// receive income
next.money_ = money_ + next.income_;
next.updateHeuristic();
return next;
}
BeamState nextStateAddMoney() {
// TODO: check next.highway_ < command_bh.size
BeamState next;
next.money_ = money_;
next.income_ = income_;
next.turn_ = turn_ + 1;
next.highway_ = highway_;
next.man_power_ = man_power_;
// Do
next.commands_ = CommandChain::pushed(commands_, 3);
next.money_ += 50000;
// receive income
next.money_ = money_ + next.income_;
next.updateHeuristic();
return next;
}
};
void discardInput() {
int u = -5, v = -5;
cin >> u >> v;
if (u == -1)
exit(1);
}
void solve(const Problem &problem) {
F<vector<P>> problem_routes_mat{N, N};
for (auto &p : problem.routes_) {
problem_routes_mat(p.first).push_back(p.second);
}
// 高速道路を追加する順番を FIX する
vector<CommandBuildHighway> command_bh;
command_bh.push_back(
CommandBuildHighway{.income = 0, .pos = P{0, 0}, .horizontal = false});
// よくわからないのでとりあえず中央から選んでいくことにする
F<int> done{N, N};
queue<P> que;
que.emplace(N / 2, N / 2);
done(N / 2, N / 2) = true;
F<int> highway{N, N};
repeat(i, T / 6) {
P p = que.front();
que.pop();
done(p) = true;
// 次の候補
for (P v : FourMoving) {
P p2 = p + v;
if (done(p2))
continue;
done(p2) = true;
que.emplace(p2);
}
highway(p) |= 1;
int income = 0;
repeat(y, N) {
repeat(x, N) {
auto dist = problem.calcDistance(highway, P{y, x});
for (P to : problem_routes_mat(y, x)) {
income += dist2NumEdge(dist[p2idx(to)]);
}
//
}
}
command_bh.push_back(
CommandBuildHighway{.income = income, .pos = p, .horizontal = false});
highway(p) |= 2;
income = 0;
repeat(y, N) {
repeat(x, N) {
auto dist = problem.calcDistance(highway, P{y, x});
for (P to : problem_routes_mat(y, x)) {
income += dist2NumEdge(dist[p2idx(to)]);
}
}
}
command_bh.push_back(
CommandBuildHighway{.income = income, .pos = p, .horizontal = true});
}
// コマンドを決める
BeamState best_state = BeamState::initialState();
ll best_score = best_state.money_ + T * 50000;
#if 1
BeamState state = best_state;
repeat(turn, T) {
BeamState next_state;
{
auto may_next_state = state.nextStateHighway(command_bh);
if (may_next_state.has_value()) {
next_state = move(*may_next_state);
} else {
next_state = state.nextStateAddManPower();
}
}
{
ll score =
next_state.money_ + (T - turn - 1) * (50000 + next_state.income_);
if (best_score < score)
{
best_state = next_state;
best_score = score;
}
}
LOG << "next: mon=" << next_state.money_ << " pow=" << next_state.man_power_;
state = move(next_state);
}
#else
vector<priority_queue<BeamState>> beam_states(T + 1); // keep buffer
beam_states[0].push(best_state);
while (g_timer.toc() < 1500) {
repeat(turn, T) {
if (beam_states[turn].empty())
continue;
BeamState top_state = beam_states[turn].top();
beam_states[turn].pop();
{
ll score = top_state.money_ + (T - turn) * (50000 + top_state.income_);
if (best_score < score) {
best_state = top_state;
best_score = score;
}
}
auto may_next_state1 = top_state.nextStateHighway(command_bh);
if (may_next_state1.has_value())
beam_states[turn + 1].push(move(*may_next_state1));
BeamState next_state2 = top_state.nextStateAddManPower();
beam_states[turn + 1].push(move(next_state2));
BeamState next_state3 = top_state.nextStateAddMoney();
beam_states[turn + 1].push(move(next_state3));
}
while (!beam_states[T].empty()) {
auto state = beam_states[T].top();
beam_states[T].pop();
if (best_score < state.money_) {
best_state = state;
best_score = state.money_;
}
}
}
#endif
discardInput();
{
auto commands = best_state.commands_->dump();
int turn = 0;
int cnt_highway = 0;
for (int cmd : commands) {
if (cmd == 1) {
cnt_highway += 1;
auto c = command_bh[cnt_highway];
if (c.horizontal) {
cout << "1 " << c.pos.y << " " << c.pos.x << " " << c.pos.y << " "
<< c.pos.x + 1 << endl;
} else {
cout << "1 " << c.pos.y << " " << c.pos.x << " " << c.pos.y + 1 << " "
<< c.pos.x << endl;
}
discardInput();
} else {
cout << cmd << endl;
discardInput();
}
turn += 1;
}
while (turn < T) {
cout << "3" << endl;
discardInput();
turn += 1;
}
}
}
//
int main(int argc, char **argv) {
Problem problem;
// problem.inputGenerated();
problem.input();
solve(problem);
return 0;
}