結果
| 問題 | No.5016 Worst Mayor |
| ユーザー |
 7iz6
|
| 提出日時 | 2023-04-29 16:48:04 |
| 言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
AC
|
| 実行時間 | 1,953 ms / 2,000 ms |
| コード長 | 12,110 bytes |
| コンパイル時間 | 5,230 ms |
| コンパイル使用メモリ | 232,108 KB |
| 実行使用メモリ | 26,968 KB |
| スコア | 19,485,281,513 |
| 平均クエリ数 | 392.00 |
| 最終ジャッジ日時 | 2023-04-29 16:50:48 |
| 合計ジャッジ時間 | 107,337 ms |
|
ジャッジサーバーID （参考情報） |
judge11 / judge16 |
| 純コード判定しない問題か言語 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 1,933 ms
26,644 KB |
| testcase_01 | AC | 1,947 ms
26,592 KB |
| testcase_02 | AC | 1,934 ms
26,860 KB |
| testcase_03 | AC | 1,918 ms
26,344 KB |
| testcase_04 | AC | 1,918 ms
26,620 KB |
| testcase_05 | AC | 1,950 ms
26,516 KB |
| testcase_06 | AC | 1,924 ms
26,176 KB |
| testcase_07 | AC | 1,938 ms
26,380 KB |
| testcase_08 | AC | 1,921 ms
26,552 KB |
| testcase_09 | AC | 1,941 ms
26,060 KB |
| testcase_10 | AC | 1,926 ms
26,512 KB |
| testcase_11 | AC | 1,938 ms
26,196 KB |
| testcase_12 | AC | 1,904 ms
26,428 KB |
| testcase_13 | AC | 1,925 ms
26,772 KB |
| testcase_14 | AC | 1,925 ms
26,380 KB |
| testcase_15 | AC | 1,911 ms
26,712 KB |
| testcase_16 | AC | 1,916 ms
26,652 KB |
| testcase_17 | AC | 1,937 ms
26,476 KB |
| testcase_18 | AC | 1,923 ms
26,628 KB |
| testcase_19 | AC | 1,917 ms
26,644 KB |
| testcase_20 | AC | 1,902 ms
26,732 KB |
| testcase_21 | AC | 1,935 ms
26,828 KB |
| testcase_22 | AC | 1,948 ms
26,784 KB |
| testcase_23 | AC | 1,902 ms
26,588 KB |
| testcase_24 | AC | 1,938 ms
26,244 KB |
| testcase_25 | AC | 1,920 ms
26,296 KB |
| testcase_26 | AC | 1,952 ms
26,240 KB |
| testcase_27 | AC | 1,935 ms
26,096 KB |
| testcase_28 | AC | 1,900 ms
26,204 KB |
| testcase_29 | AC | 1,924 ms
26,232 KB |
| testcase_30 | AC | 1,916 ms
26,304 KB |
| testcase_31 | AC | 1,911 ms
26,364 KB |
| testcase_32 | AC | 1,907 ms
26,324 KB |
| testcase_33 | AC | 1,899 ms
26,356 KB |
| testcase_34 | AC | 1,910 ms
26,968 KB |
| testcase_35 | AC | 1,918 ms
26,812 KB |
| testcase_36 | AC | 1,953 ms
26,860 KB |
| testcase_37 | AC | 1,933 ms
26,384 KB |
| testcase_38 | AC | 1,928 ms
26,376 KB |
| testcase_39 | AC | 1,911 ms
26,228 KB |
| testcase_40 | AC | 1,932 ms
26,540 KB |
| testcase_41 | AC | 1,909 ms
26,920 KB |
| testcase_42 | AC | 1,927 ms
26,760 KB |
| testcase_43 | AC | 1,909 ms
26,472 KB |
| testcase_44 | AC | 1,926 ms
26,304 KB |
| testcase_45 | AC | 1,930 ms
26,156 KB |
| testcase_46 | AC | 1,927 ms
26,460 KB |
| testcase_47 | AC | 1,933 ms
26,320 KB |
| testcase_48 | AC | 1,920 ms
26,800 KB |
| testcase_49 | AC | 1,941 ms
26,660 KB |
ソースコード
#pragma GCC optimize("-O3")
#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <array>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <tuple>
#include <stack>
#include <bitset>
#include <random>
#include <algorithm>
#include <cassert>
#include <limits>
#include <utility>
#include <iomanip>
#include <iterator>
#include <cmath>
#include <numeric>
#include <chrono>
#include <sstream>
#include <cstring>
#include <cstdio>
#include <memory>
#include <optional>
struct Point {
int i, j;
};
bool operator<(const Point& lhs, const Point& rhs) {
return (lhs.i < rhs.i || lhs.j < rhs.j);
}
bool operator>(const Point& lhs, const Point& rhs) {
return (lhs.i > rhs.i || lhs.j > rhs.j);
}
struct Road {
Point u, v;
};
bool operator==(const Point& lhs, const Point& rhs) {
return (lhs.i == rhs.i && lhs.j == rhs.j);
}
// --------------------- macros ----------------------
#define pii std::pair<int,int>
#define Vec std::vector
#define rep(i, s, n) for(int i = s; i < (n); i++)
using namespace std;
using ll = long long;
// --------------------- constants ----------------------
constexpr int INF = 1e9 + 10;
constexpr ll LINF = 1LL<<60;
constexpr double EPS = 1e-6;
const double PI = std::acos(-1);
// clockwise
static const int di[4] = {0, 1, 0, -1};
static const int dj[4] = {1, 0, -1, 0};
const double TL = 2.0;
const double TL_90 = TL * 0.9;
const double TL_95 = TL * 0.95;
constexpr int N = 3000;
constexpr int TERM = 400;
constexpr int H = 14;
constexpr int W = 14;
constexpr int INIT_FUND = 1'000'000;
constexpr double TIME_ROAD = 1.0;
constexpr double TIME_HIGHWAY = 0.223;
constexpr int DONATION = 50'000;
constexpr int FEE_HIGHWAY = 60;
// --------------------- global variables ----------------------
std::random_device seed_gen;
std::mt19937 mt(seed_gen());
clock_t start_time, cur_time;
Point A[N], C[N];
// --------------------- functionss ----------------------
double get_time() {
return (double)(clock() - start_time) / CLOCKS_PER_SEC;
}
bool is_out(int i, int j, int d) {
return (i < 0 || i >= d || j < 0 || j >= d);
}
bool is_out(int i, int j, int h, int w) {
return (i < 0 || i >= h || j < 0 || j >= w);
}
template<typename T> T pow2(T a) {
return a * a;
}
bool arg_parse(int argv, char* argc[]) {
for(int i = 0; i < argv; i++) {
if(std::strcmp(argc[i], "--seed") == 0) {
if(i + 1 > argv) {
std::cerr << "no arguments." << std::endl;
return false;
}
int _seed = std::stoi(argc[i+1]);
mt = std::mt19937(_seed);
}
}
return true;
}
// --------------------- classes ----------------------
struct IOServer {
int patron = 1;
int fund = INIT_FUND;
void read_output1(int i1, int j1, int i2, int j2) {
fund -= std::floor((double)10000000 / std::sqrt(patron));
}
void read_output2() {
patron++;
}
void read_output3() {
fund += DONATION;
}
};
// ----------------------------------------------------
class Solver {
public:
int num_search = 0;
int money;
int patron;
Road p_road; // priority road
Vec<Vec<Vec<Vec<int>>>> cnt;
Vec<Vec<Vec<double>>> dist_cur;
Vec<Vec<Vec<Vec<bool>>>> is_highway;
Vec<pair<Point,Point>> highway_list;
Vec<int> num_highway_on_path;
int num_reward = 0;
int num_highway;
#ifdef LOCAL
IOServer judge;
#endif
Solver() {
} // constructor
void init() {
int buf;
std::cin >> buf >> buf;
for(int i = 0; i < N; i++) {
std::cin >> A[i].i >> A[i].j >> C[i].i >> C[i].j;
A[i].i--;
C[i].i--;
A[i].j--;
C[i].j--;
}
patron = 1;
money = INIT_FUND;
num_highway = 0;
cnt.resize(H, Vec<Vec<Vec<int>>>(W, Vec<Vec<int>>(H, Vec<int>(W, 0))));
is_highway.resize(H, Vec<Vec<Vec<bool>>>(W, Vec<Vec<bool>>(H, Vec<bool>(W, false))));
dist_cur.resize(N, Vec<Vec<double>>(H, Vec<double>(W, 1e18)));
num_highway_on_path.resize(N, 0);
// BFS
Vec<Vec<int>> dist;
for(int i = 0; i < N; i++) {
dist.clear();
dist.resize(H, Vec<int>(W, INF));
if(A[i] == C[i]) continue;
queue<pair<int, Point>> q;
dist[A[i].i][A[i].j] = 0;
q.push(std::make_pair(0, A[i]));
bool ok = false;
int ni, nj;
while(!q.empty() && !ok) {
auto[cost, p] = q.front(); q.pop();
for(int d = 0; d < 4; d++) {
ni = p.i + di[d];
nj = p.j + dj[d];
if(is_out(ni,nj,H,W)) continue;
if(dist[ni][nj] > cost+1) {
dist[ni][nj] = cost + 1;
q.push(std::make_pair(cost+1, Point{ni,nj}));
}
if(ni == C[i].i && nj == C[i].j) {
ok = true;
break;
}
}
}
// 復元
queue<pair<int,Point>> q_rev;
Vec<Vec<bool>> visited(H, Vec<bool>(W, false));
q_rev.push({dist[C[i].i][C[i].j], C[i]});
ok = false;
visited[C[i].i][C[i].j] = true;
while(!q_rev.empty() && !ok) {
auto[d, p] = q_rev.front(); q_rev.pop();
for(int dir = 0; dir < 4; dir++) {
ni = p.i + di[dir];
nj = p.j + dj[dir];
if(is_out(ni,nj,H,W)) continue;
if(dist[ni][nj] == d - 1) {
cnt[ni][nj][p.i][p.j]++;
cnt[p.i][p.j][ni][nj]++;
if(!visited[ni][nj]) {
visited[ni][nj] = true;
q_rev.push(std::make_pair(d-1, Point{ni,nj}));
}
}
}
}
}
int max_cnt = -1;
rep(i, 0, H)rep(j,0,W)rep(k,0,H)rep(l,0,W) if(cnt[i][j][k][l]>max_cnt){
max_cnt=cnt[i][j][k][l];
p_road = {Point{i,j}, Point{k,l}};
}
fprintf(stderr, "[case] N: %d, TERM: %d\n", N, TERM);
}
// main solve
void solve() {
int pre_choice = -1;
for(int t = 0; t < TERM; t++) {
int nil;
#ifndef LOCAL
std::cin >> money >> patron;
// scanf("%d %d", &money, &patron);
#endif
#ifdef LOCAL
if(t % 20 == 0) {
fprintf(stderr,
"[Info] TERM: %03d, time: %6.3f, money: %9d, patron: %2d\n", t, get_time(), money, patron
);
fprintf(stderr,
"...... Number of Highway: %2d, \n", num_highway
);
fprintf(stderr,
"...... Number of Highway on path: %3d, \n\n", num_reward
);
}
#endif
// 60日までは協力者集め
if(t < 45) {
std::cout << "2" << std::endl;
pre_choice = 2;
patron++;
} else if(t < 55) {
std::cout << "3" << std::endl;
money += DONATION;
} else if(t==55) {
auto[u,v] = p_road;
ll build_cost = this->get_cost_build_highway(patron);
std::cout << "1 " << u.i + 1 << " " << u.j + 1 << " " << v.i + 1 << " " << v.j + 1 << std::endl;
is_highway[u.i][u.j][v.i][v.j] = is_highway[v.i][v.j][u.i][u.j] = true;
money -= build_cost;
num_highway++;
update_cnt();
} else {
if(get_time() > TL_90) {
std::cout << "3" << std::endl;
get_reward();
continue;
}
auto[u,v] = p_road;
const ll exp_reward1 = cnt[u.i][u.j][v.i][v.j] * (TERM - t) * FEE_HIGHWAY;
const ll exp_reward2 = cnt[u.i][u.j][v.i][v.j] * (TERM - t - 1) * FEE_HIGHWAY;
ll build_cost1 = get_cost_build_highway(patron);
ll build_cost2 = get_cost_build_highway(patron + 1);
if(exp_reward2 - build_cost2 > exp_reward1 - build_cost1) {
std::cout << "2" << std::endl;
patron++;
} else if(exp_reward1 >= build_cost1 && money >= build_cost1) {
#ifdef LOCAL
fprintf(stderr,
"[Info] BUILDING HIGHWAY!\n"
);
fprintf(stderr,
"...... EXPECTED REWARD: %10lld, BUILD COST: %10lld\n\n", exp_reward1, build_cost1
);
#endif
std::cout << "1 " << u.i + 1 << " " << u.j + 1 << " " << v.i + 1 << " " << v.j + 1 << std::endl;
is_highway[u.i][u.j][v.i][v.j] = is_highway[v.i][v.j][u.i][u.j] = true;
money -= build_cost1;
num_highway++;
update_cnt();
} else {
std::cout << "3" << std::endl;
money += DONATION;
}
}
get_reward();
}
} // solve
void update_cnt() {
cnt.clear();
cnt.resize(H, Vec<Vec<Vec<int>>>(W, Vec<Vec<int>>(H, Vec<int>(W, 0))));
// dijkstra
Vec<Vec<double>> dist;
for(int i = 0; i < N; i++) {
dist.clear();
dist.resize(H, Vec<double>(W, 1e19));
if(A[i] == C[i]) continue;
std::priority_queue<pair<double, Point>, vector<pair<double, Point>>, greater<pair<double,Point>> > pq;
dist[A[i].i][A[i].j] = 0.0;
pq.push({0.0, A[i]});
int ni, nj;
double len;
while(!pq.empty()) {
auto[cost, p] = pq.top(); pq.pop();
if(cost - dist[p.i][p.j] > EPS || cost > dist[C[i].i][C[i].j] + EPS) continue;
for(int d = 0; d < 4; d++) {
ni = p.i + di[d];
nj = p.j + dj[d];
if(is_out(ni,nj,H,W)) continue;
len = is_highway[p.i][p.j][ni][nj] ? TIME_HIGHWAY : 1.0;
if(dist[ni][nj] > cost+len+EPS) {
dist[ni][nj] = cost + len;
pq.push(std::make_pair(cost+len, Point{ni,nj}));
}
}
} // while
dist_cur[i] = dist;
Vec<Vec<bool>> visited(H, Vec<bool>(W, false));
bool ok = false;
int num_hw = 0;
auto dfs=[&](auto dfs, const Point& u, const Point& v) -> void {
if(visited[u.i][u.j] || ok) return;
visited[u.i][u.j] = true;
if(u==v) {
ok = true;
return;
}
for(int d = 0; d < 4; d++) {
ni = u.i + di[d];
nj = u.j + dj[d];
if(is_out(ni,nj,H,W)) continue;
double len = is_highway[ni][nj][u.i][u.j] ? TIME_HIGHWAY : 1.0;
if(abs((dist[u.i][u.j]-len)-dist[ni][nj]) < EPS) {
if(is_highway[ni][nj][u.i][u.j]) num_hw++;
if(!ok) dfs(dfs, Point{ni,nj}, v);
}
}
};
dfs(dfs, C[i], A[i]);
num_highway_on_path[i] = num_hw;
// 復元
queue<pair<double,Point>> q_rev;
q_rev.push({dist[C[i].i][C[i].j], C[i]});
visited.clear();
visited.resize(H, Vec<bool>(W, false));
visited[C[i].i][C[i].j] = true;
while(!q_rev.empty()) {
auto[d, p] = q_rev.front(); q_rev.pop();
for(int dir = 0; dir < 4; dir++) {
ni = p.i + di[dir];
nj = p.j + dj[dir];
if(is_out(ni,nj,H,W)) continue;
len = is_highway[p.i][p.j][ni][nj] ? TIME_HIGHWAY : 1.0;
if(std::abs(dist[ni][nj] - (d - len)) < EPS) {
cnt[ni][nj][p.i][p.j]++;
cnt[p.i][p.j][ni][nj]++;
if(!visited[ni][nj]) {
visited[ni][nj] = true;
q_rev.push(std::make_pair(d-len, Point{ni,nj}));
}
}
}
}
}
int max_cnt = -1;
rep(i, 0, H)rep(j,0,W)rep(k,0,H)rep(l,0,W) if(cnt[i][j][k][l]>max_cnt&&!is_highway[i][j][k][l]){
max_cnt=cnt[i][j][k][l];
p_road = {Point{i,j}, Point{k,l}};
}
}
void get_reward() {
num_reward = 0;
for(int i = 0; i < N; i++) {
money += num_highway_on_path[i] * FEE_HIGHWAY;
num_reward += num_highway_on_path[i];
}
}
ll get_cost_build_highway(int _patron) {
constexpr double BASE = 1e7;
return (ll)std::floor( BASE / std::sqrt(_patron) );
}
// return summaries of solve
void summary() {
std::cerr << "\n##### SUMMARY #######################\n";
fprintf(stderr, "ELAPSED TIME : %6.4f s\n", get_time());
fprintf(stderr, "NUMBER OF SEARCH : \n", this->num_search);
std::cerr << "######################################\n";
}
private:
};
int main(int argv, char* argc[]) {
start_time = clock();
Solver solver;
#ifdef _OPTUNA
bool ok = arg_parse(int argv, char* argc[])
#endif
solver.init();
solver.solve();
solver.summary();
return 0;
}