結果
| 問題 |
No.5016 Worst Mayor
|
| コンテスト | |
| ユーザー |
 shibh308
|
| 提出日時 | 2023-04-29 16:23:45 |
| 言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 10,353 bytes |
| コンパイル時間 | 3,585 ms |
| コンパイル使用メモリ | 250,044 KB |
| 実行使用メモリ | 24,456 KB |
| スコア | 0 |
| 平均クエリ数 | 401.00 |
| 最終ジャッジ日時 | 2023-04-29 16:26:26 |
| 合計ジャッジ時間 | 73,855 ms |
|
ジャッジサーバーID （参考情報） |
judge16 / judge11 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | WA * 50 |
ソースコード
#include <bits/stdc++.h>
// #include "atcoder/all"
using namespace std;
using i64 = long long;
const i64 MOD = 1e9 + 7;
const i64 INF = i64(1e18);
template <typename T>
bool chmin(T& x, T y){
if(x > y){
x = y;
return true;
}
return false;
}
template <typename T>
bool chmax(T& x, T y){
if(x < y){
x = y;
return true;
}
return false;
}
namespace Rnd{
// doc: https://shibh308.github.io/library/library/lib/functions/xorshift.cpp.html
uint64_t x = 0xdeadbeef0110dead;
uint64_t rnd(){
x ^= x << 7;
x ^= x >> 9;
return x;
}
uint64_t rnd(int n){
return rnd() % n;
}
double rnd_double(){
return 1.0 * rnd() / numeric_limits<uint64_t>::max();
}
vector<int> rnd_perm(int n){
vector<int> v(n);
iota(v.begin(), v.end(), 0);
for(int i = n - 1; i >= 1; --i){
int j = rnd(i + 1);
swap(v[i], v[j]);
}
return v;
}
template<typename T>
void shuffle(vector<T>& v){
int n = v.size();
for(int i = n - 1; i >= 1; --i){
int j = rnd(i + 1);
swap(v[i], v[j]);
}
}
}
namespace params{
void load_params(){
ifstream ifs("../params.txt");
assert(ifs.is_open());
}
}
constexpr int n = 14;
constexpr int m = 3000;
constexpr int turn_max = 400;
vector<int> stx, sty, enx, eny;
void read_file(istream& ifs){
int _1, _2;
ifs >> _1 >> _2;
stx.resize(m);
sty.resize(m);
enx.resize(m);
eny.resize(m);
for(int i = 0; i < m; ++i){
ifs >> stx[i] >> sty[i] >> enx[i] >> eny[i];
--stx[i];
--sty[i];
--enx[i];
--eny[i];
}
}
clock_t st_clock;
void solve(){
// (x, y) -> (x+1, y)
array<bitset<n>, n-1> x_flag;
// (x, y) -> (x, y+1)
array<bitset<n-1>, n> y_flag;
i64 person, money;
vector<int> dx{0, 1, 0, -1};
vector<int> dy{1, 0, -1, 0};
vector<vector<pair<int, int>>> dist;
auto calc_dist = [&](){
dist.assign(196, vector<pair<int, int>>(196, {MOD, MOD}));
for(int i = 0; i < 196; ++i){
priority_queue<tuple<double, pair<int,int>, int>, vector<tuple<double, pair<int,int>, int>>, greater<>> que;
dist[i][i] = make_pair(0, 0);
que.emplace(0.0, make_pair(0, 0), i);
while(!que.empty()){
auto [dis, tup, pos] = que.top();
que.pop();
if(dist[i][pos] != tup){
continue;
}
int x = pos / n;
int y = pos % n;
for(int d = 0; d < 4; ++d){
int nx = x + dx[d];
int ny = y + dy[d];
if(nx < 0 || ny < 0 || nx >= n || ny >= n){
continue;
}
int mx = min(x, nx);
int my = min(y, ny);
int nex = nx * n + ny;
bool is_x = x != nx;
bool is_fast = is_x ? x_flag[mx][my] : y_flag[mx][my];
pair<int,int> tup_nex = {tup.first + is_fast, tup.second + !is_fast};
double dis_pre = dist[i][nex].first * 0.223 + dist[i][nex].second * 1.000;
double dis_nex = tup_nex.first * 0.223 + tup_nex.second * 1.000;
if(dis_nex < dis_pre){
dist[i][nex] = tup_nex;
que.emplace(dis_nex, tup_nex, nex);
}
}
}
}
};
auto check = [&](int x, int y, bool is_x){
int ofs_x = 2 + x * 3;
int ofs_y = 2 + y * 3;
if(is_x ? x_flag[ofs_x][ofs_y] : y_flag[ofs_x][ofs_y]){
return -INF;
}
i64 sum = 0;
for(int i = 0; i < m; ++i){
auto tup = dist[stx[i] * n + sty[i]][enx[i] * n + eny[i]];
for(int j = 0; j < 4; ++j){
for(int k = 0; k < 4; ++k){
int pos_jx = ofs_x + (is_x ? j : 0);
int pos_jy = ofs_y + (is_x ? 0 : j);
int pos_j = pos_jx * n + pos_jy;
int pos_kx = ofs_x + (is_x ? k : 0);
int pos_ky = ofs_y + (is_x ? 0 : k);
int pos_k = pos_kx * n + pos_ky;
int dis = abs(j - k);
int d_first = dist[stx[i] * n + sty[i]][pos_j].first + dis + dist[pos_k][enx[i] * n + eny[i]].first;
int d_second = dist[stx[i] * n + sty[i]][pos_j].second + dist[pos_k][enx[i] * n + eny[i]].second;
double bef_dist = tup.first * 0.223 + tup.second;
double nex_dist = d_first * 0.223 + d_second;
if(nex_dist < bef_dist){
tup = make_pair(d_first, d_second);
}
}
}
sum += tup.first;
}
return sum;
};
vector<tuple<int,int,bool>> v;
for(int _ = 0; _ < 24; ++_){
calc_dist();
tuple<i64,int,int,bool> sc(-INF, 0, 0, false);
for(int i = 0; i < 3; ++i){
for(int j = 0; j < 4; ++j){
chmax(sc, make_tuple(check(i, j, true), i, j, true));
}
}
for(int i = 0; i < 4; ++i){
for(int j = 0; j < 3; ++j){
chmax(sc, make_tuple(check(i, j, false), i, j, false));
}
}
auto [_1, x, y, is_x] = sc;
int ofs_x = 2 + x * 3;
int ofs_y = 2 + y * 3;
for(int i = 0; i < 3; ++i){
if(is_x){
x_flag[ofs_x + i][ofs_y] = true;
}
else{
y_flag[ofs_x][ofs_y + i] = true;
}
}
v.emplace_back(x, y, is_x);
}
vector<vector<i64>> table(24, vector<i64>(8, 0));
for(auto& fl : x_flag){
fl.reset();
}
for(auto& fl : y_flag){
fl.reset();
}
for(int i = 0; i < 24; ++i){
auto [x, y, is_x] = v[i];
int ofs_x = 2 + x * 3;
int ofs_y = 2 + y * 3;
for(int j = 0; j < (1 << 3); ++j){
for(int k = 0; k < 3; ++k){
if(is_x){
x_flag[ofs_x + k][ofs_y] = bool(j & (1 << k));
}
else{
y_flag[ofs_x][ofs_y + k] = bool(j & (1 << k));
}
}
calc_dist();
i64 adv = 0;
for(int k = 0; k < m; ++k){
adv += dist[stx[k] * n + sty[k]][enx[k] * n + eny[k]].first;
}
table[i][j] = adv * 60;
}
for(int j = 0; j < 3; ++j){
if(is_x){
x_flag[ofs_x + j][ofs_y] = true;
}
else{
y_flag[ofs_x][ofs_y + j] = true;
}
}
}
// dp[turn][group][flag]
vector<vector<vector<i64>>> dp(turn_max + 1, vector<vector<i64>>(25, vector<i64>(8, -INF)));
vector<vector<vector<int>>> mov(turn_max + 1, vector<vector<int>>(25, vector<int>(8, -3)));
dp[0][0][0] = 1e6;
for(int i = 0; i < turn_max; ++i){
if(dp[i][24][0] != -INF){
dp[i + 1][24][0] = dp[i][24][0] + 50000;
mov[i + 1][24][0] = -3;
}
for(int j = 0; j < 24; ++j){
for(int k = 0; k < 8; ++k){
if(dp[i][j][k] == -INF){
continue;
}
for(int fl = 0; fl < 3; ++fl){
if(k & (1 << fl)){
continue;
}
i64 human = i - (j * 3 + __builtin_popcount(k)) + 1;
// add human
if(chmax(dp[i + 1][j][k], dp[i][j][k] + table[j][k])){
mov[i + 1][j][k] = -2;
}
i64 cost = ceil(1e7 / sqrt(human));
if(dp[i][j][k] < cost){
continue;
}
i64 sc = dp[i][j][k] - cost + table[j][k];
if((k | (1 << fl)) == 7){
if(chmax(dp[i + 1][j + 1][0], sc)){
mov[i + 1][j + 1][0] = fl;
}
}
else{
if(chmax(dp[i + 1][j][k | (1 << fl)], sc)){
mov[i + 1][j][k | (1 << fl)] = fl;
}
}
}
}
}
}
// cout << "end: " << double(clock() - st_clock) / CLOCKS_PER_SEC << endl;
int j = 24, k = 0;
vector<int> types(turn_max);
vector<pair<pair<int,int>, pair<int,int>>> moves(turn_max);
vector<int> moneys(turn_max);
for(int i = turn_max; i > 0; --i){
moneys[i - 1] = dp[i][j][k];
if(mov[i][j][k] == -3){
types[i - 1] = 3;
}
else if(mov[i][j][k] == -2){
types[i - 1] = 2;
}
else{
types[i - 1] = 1;
int idx = mov[i][j][k];
if(k == 0){
--j;
k = 7 & ~(1 << idx);
}
else{
k &= ~(1 << idx);
}
auto [x, y, is_x] = v[j];
int ofs_x = 2 + x * 3;
int ofs_y = 2 + y * 3;
if(is_x){
auto p1 = make_pair(ofs_x + idx, ofs_y);
auto p2 = make_pair(ofs_x + idx + 1, ofs_y);
moves[i - 1] = make_pair(p1, p2);
}
else{
auto p1 = make_pair(ofs_x, ofs_y + idx);
auto p2 = make_pair(ofs_x, ofs_y + idx + 1);
moves[i - 1] = make_pair(p1, p2);
}
}
}
cout << dp.back().back()[0] << endl;
for(int i = 0; i < turn_max; ++i){
cin >> money >> person;
if(types[i] == 1){
cout << 1 << " ";
cout << moves[i].first.first + 1 << " " << moves[i].first.second + 1 << " ";
cout << moves[i].second.first + 1 << " " << moves[i].second.second + 1 << endl;
}
else{
cout << types[i] << endl;
}
}
}
signed main(){
st_clock = clock();
#ifdef OPTIMIZE
params::load_params();
#endif
#ifndef HAND
read_file(cin);
#else
ifstream ifs("../contests/yukisc5/in0.txt");
assert(ifs.is_open());
read_file(ifs);
#endif
solve();
}