結果
| 問題 |
No.5016 Worst Mayor
|
| コンテスト | |
| ユーザー |
 square1001
|
| 提出日時 | 2023-04-29 15:01:22 |
| 言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 1,537 ms / 2,000 ms |
| コード長 | 6,172 bytes |
| コンパイル時間 | 1,742 ms |
| コンパイル使用メモリ | 97,692 KB |
| 実行使用メモリ | 24,348 KB |
| スコア | 21,509,124,964 |
| 平均クエリ数 | 384.00 |
| 最終ジャッジ日時 | 2023-04-29 15:02:42 |
| 合計ジャッジ時間 | 69,714 ms |
|
ジャッジサーバーID （参考情報） |
judge12 / judge14 |
| 純コード判定しない問題か言語 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 50 |
ソースコード
#include <array>
#include <cmath>
#include <string>
#include <vector>
#include <cassert>
#include <iostream>
#include <algorithm>
using namespace std;
class action {
public:
static constexpr int D = 14;
static constexpr int ACTION_BUILD = 1;
static constexpr int ACTION_LEVEL = 2;
static constexpr int ACTION_MONEY = 3;
int tp, id;
action() : tp(-1), id(-1) {}
action(int tp_) : tp(tp_), id(-1) {
assert(tp == 2 || tp == 3);
}
action(int tp_, int id_) : tp(tp_), id(id_) {
assert(tp == 1 && 0 <= id && id < D * (D - 1) * 2);
}
string to_string() const {
assert(tp != -1);
if (tp == 2 || tp == 3) {
return std::to_string(tp);
}
int xa, ya, xb, yb;
if (id < D * (D - 1)) {
xa = id / D;
ya = id % D;
xb = xa + 1;
yb = ya;
}
else {
xa = (id - D * (D - 1)) / (D - 1);
ya = (id - D * (D - 1)) % (D - 1);
xb = xa;
yb = ya + 1;
}
// output in 1-indexed
return std::to_string(tp) + " " + std::to_string(xa + 1) + " " + std::to_string(ya + 1) + " " + std::to_string(xb + 1) + " " + std::to_string(yb + 1);
}
};
uint64_t seed = 123456789;
uint64_t xorshift64() {
seed ^= seed << 13;
seed ^= seed >> 7;
seed ^= seed << 17;
return seed;
}
int main() {
// step #1. initial input
const int INF = 1012345678;
const int D = action::D;
int N, T;
cin >> N >> T;
vector<int> X(N), Y(N);
for (int i = 0; i < N; i++) {
int a, b, c, d;
cin >> a >> b >> c >> d;
X[i] = (a - 1) * D + (b - 1);
Y[i] = (c - 1) * D + (d - 1);
}
// step #2. make graph-like list of citizens
vector<int> deg(D * D);
for (int i = 0; i < N; i++) {
deg[X[i]] += 1;
deg[Y[i]] += 1;
}
vector<vector<int> > G(D * D);
for (int i = 0; i < N; i++) {
if (deg[X[i]] > deg[Y[i]] || (deg[X[i]] == deg[Y[i]] && X[i] < Y[i])) {
G[X[i]].push_back(Y[i]);
}
else {
G[Y[i]].push_back(X[i]);
}
}
// step #3. function to calculate score
auto calc = [&](const vector<int>& road) {
int answer = 0;
vector<int> q1(D * D), q2(D * D);
for (int i = 0; i < D * D; i++) {
if (G[i].empty()) {
continue;
}
vector<int> dist(D * D, INF);
dist[i] = 0;
int ql1 = 0, qr1 = 1;
int ql2 = 0, qr2 = 0;
q1[0] = i;
while (ql1 != qr1 || ql2 != qr2) {
int c1 = (ql1 != qr1 ? q1[ql1] : INF);
int c2 = (ql2 != qr2 ? q2[ql2] : INF);
int pos = -1, curdist = 0;
if (c1 <= c2) {
curdist = (c1 >> 12);
pos = (c1 & ((1 << 12) - 1));
ql1 += 1;
}
else {
curdist = (c2 >> 12);
pos = (c2 & ((1 << 12) - 1));
ql2 += 1;
}
int px = pos / D, py = pos % D;
// direction 1: down
if (px != D - 1 && road[px * D + py] == 0) {
if (dist[pos + D] > curdist + 1000) {
dist[pos + D] = curdist + 1000;
q1[qr1++] = (dist[pos + D] << 12) | (pos + D);
}
}
if (px != D - 1 && road[px * D + py] == 1) {
if (dist[pos + D] > curdist + 223) {
dist[pos + D] = curdist + 223;
q2[qr2++] = (dist[pos + D] << 12) | (pos + D);
}
}
// direction 2: up
if (px != 0 && road[(px - 1) * D + py] == 0) {
if (dist[pos - D] > curdist + 1000) {
dist[pos - D] = curdist + 1000;
q1[qr1++] = (dist[pos - D] << 12) | (pos - D);
}
}
if (px != 0 && road[(px - 1) * D + py] == 1) {
if (dist[pos - D] > curdist + 223) {
dist[pos - D] = curdist + 223;
q2[qr2++] = (dist[pos - D] << 12) | (pos - D);
}
}
// direction 3: right
if (py != D - 1 && road[D * (D - 1) + px * (D - 1) + py] == 0) {
if (dist[pos + 1] > curdist + 1000) {
dist[pos + 1] = curdist + 1000;
q1[qr1++] = (dist[pos + 1] << 12) | (pos + 1);
}
}
if (py != D - 1 && road[D * (D - 1) + px * (D - 1) + py] == 1) {
if (dist[pos + 1] > curdist + 223) {
dist[pos + 1] = curdist + 223;
q2[qr2++] = (dist[pos + 1] << 12) | (pos + 1);
}
}
// direction 4: left
if (py != 0 && road[D * (D - 1) + px * (D - 1) + py - 1] == 0) {
if (dist[pos - 1] > curdist + 1000) {
dist[pos - 1] = curdist + 1000;
q1[qr1++] = (dist[pos - 1] << 12) | (pos - 1);
}
}
if (py != 0 && road[D * (D - 1) + px * (D - 1) + py - 1] == 1) {
if (dist[pos - 1] > curdist + 223) {
dist[pos - 1] = curdist + 223;
q2[qr2++] = (dist[pos - 1] << 12) | (pos - 1);
}
}
}
for (int j : G[i]) {
answer += (dist[j] * 287) % 1000;
}
}
return answer;
};
// step #4. process queries
int current_money = 1000000;
int current_level = 1;
int current_score = 0;
int used_roads = 0;
bool flag = false;
vector<int> road(D * (D - 1) * 2, 0);
for (int i = 0; i < T; i++) {
int tmp1, tmp2;
cin >> tmp1 >> tmp2;
// decide action
int required_money = int(10000000 / sqrt(current_level));
action a;
if (i < 35) {
a = action(action::ACTION_LEVEL);
}
else if (used_roads == 0 && current_money < required_money) {
a = action(action::ACTION_MONEY);
}
else if (!flag) {
if (current_money >= required_money) {
int opt_choice = -1;
int opt_score = -INF;
for (int j = 0; j < D * (D - 1) * 2; j++) {
if (road[j] == 0 && xorshift64() % 11 == 0) {
road[j] = 1;
int subscore = calc(road);
if (opt_score < subscore) {
opt_score = subscore;
opt_choice = j;
}
road[j] = 0;
}
}
if ((current_score * 60 + 50000) * (400 - i) > ((opt_score + 150) * 60 + 50000) * (400 - i - 1) - required_money) {
flag = true;
}
else {
a = action(action::ACTION_BUILD, opt_choice);
used_roads += 1;
}
}
else {
a = action(action::ACTION_LEVEL);
}
}
if (flag) {
a = action(action::ACTION_MONEY);
}
// process action
if (a.tp == action::ACTION_BUILD) {
road[a.id] = 1;
used_roads += 1;
current_money -= required_money;
current_score = calc(road);
}
if (a.tp == action::ACTION_LEVEL) {
current_level += 1;
}
if (a.tp == action::ACTION_MONEY) {
current_money += 50000;
}
current_money += current_score * 60;
cout << a.to_string() << endl;
cerr << "! " << i << ": level = " << current_level << ", money = " << current_money << ", score = " << current_score << endl;
}
return 0;
}