結果
| 問題 | No.5016 Worst Mayor |
| ユーザー |
 Fu_L
|
| 提出日時 | 2023-04-29 15:56:13 |
| 言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 5,828 bytes |
| コンパイル時間 | 4,949 ms |
| コンパイル使用メモリ | 263,728 KB |
| 実行使用メモリ | 37,700 KB |
| スコア | 0 |
| 最終ジャッジ日時 | 2023-04-29 15:56:40 |
| 合計ジャッジ時間 | 11,716 ms |
|
ジャッジサーバーID （参考情報） |
judge15 / judge11 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | TLE | - |
| testcase_01 | -- | - |
| testcase_02 | -- | - |
| testcase_03 | -- | - |
| testcase_04 | -- | - |
| testcase_05 | -- | - |
| testcase_06 | -- | - |
| testcase_07 | -- | - |
| testcase_08 | -- | - |
| testcase_09 | -- | - |
| testcase_10 | -- | - |
| testcase_11 | -- | - |
| testcase_12 | -- | - |
| testcase_13 | -- | - |
| testcase_14 | -- | - |
| testcase_15 | -- | - |
| testcase_16 | -- | - |
| testcase_17 | -- | - |
| testcase_18 | -- | - |
| testcase_19 | -- | - |
| testcase_20 | -- | - |
| testcase_21 | -- | - |
| testcase_22 | -- | - |
| testcase_23 | -- | - |
| testcase_24 | -- | - |
| testcase_25 | -- | - |
| testcase_26 | -- | - |
| testcase_27 | -- | - |
| testcase_28 | -- | - |
| testcase_29 | -- | - |
| testcase_30 | -- | - |
| testcase_31 | -- | - |
| testcase_32 | -- | - |
| testcase_33 | -- | - |
| testcase_34 | -- | - |
| testcase_35 | -- | - |
| testcase_36 | -- | - |
| testcase_37 | -- | - |
| testcase_38 | -- | - |
| testcase_39 | -- | - |
| testcase_40 | -- | - |
| testcase_41 | -- | - |
| testcase_42 | -- | - |
| testcase_43 | -- | - |
| testcase_44 | -- | - |
| testcase_45 | -- | - |
| testcase_46 | -- | - |
| testcase_47 | -- | - |
| testcase_48 | -- | - |
| testcase_49 | -- | - |
ソースコード
#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using namespace atcoder;
using ll = long long;
using P = pair<ll, ll>;
using mint = modint998244353;
#define rep(i, a, b) for(ll i = a; i < b; i++)
#define rrep(i, a, b) for(ll i = a; i >= b; i--)
constexpr ll inf = 4e18;
struct RandomNumberGenerator {
mt19937_64 mt;
RandomNumberGenerator()
: mt(chrono::steady_clock::now().time_since_epoch().count()) {}
ll operator()(ll l, ll r) {
uniform_int_distribution<ll> dist(l, r);
return dist(mt);
}
} rng;
int main(void) {
cin.tie(0);
ios::sync_with_stdio(0);
const vector<int> dx = {1, 0, -1, 0};
const vector<int> dy = {0, 1, 0, -1};
constexpr int m = 14;
int n, t;
cin >> n >> t;
vector<int> a(n), b(n), c(n), d(n);
rep(i, 0, n) {
cin >> a[i] >> b[i] >> c[i] >> d[i];
a[i]--;
b[i]--;
c[i]--;
d[i]--;
}
vector<vector<int>> dist(m * m, vector<int>(m * m, 1e9));
rep(i, 0, m * m) {
rep(j, 0, m * m) {
if(i == j) {
dist[i][j] = 0;
} else if(abs(i - j) == 1 or abs(i - j) == m) {
dist[i][j] = 1000;
}
}
}
rep(k, 0, m * m) {
rep(i, 0, m * m) {
rep(j, 0, m * m) {
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
}
}
}
vector<int> ty(t), x(t), y(t), z(t), w(t);
int curx = -1, cury = -1;
ll cnt = 0;
ll money = 1e6;
rep(day, 0, t) {
if(day <= 23) {
ty[day] = 2;
money += 60ll * cnt;
continue;
}
if(money < ll(2e6)) {
ty[day] = 3;
money += ll(5e4);
money += 60ll * cnt;
continue;
}
if(curx == -1 and cury == -1) {
int ma = 0;
int mx = -1, my = -1, mz = -1, mw = -1;
rep(i, 0, m) {
rep(j, 0, m) {
rep(dir, 0, 4) {
int nx = i, ny = j, nz = i + dx[dir], nw = j + dy[dir];
if(nz < 0 or m <= nz or nw < 0 or m <= nw) continue;
vector<vector<int>> ndist = dist;
ndist[nx * m + ny][nz * m + nw] = 223;
ndist[nz * m + nw][nx * m + ny] = 223;
rep(i, 0, m * m) {
rep(j, 0, m * m) {
ndist[i][j] = min(ndist[i][j], ndist[i][nx * m + ny] + ndist[nx * m + ny][nz * m + nw] + ndist[nz * m + nw][j]);
ndist[i][j] = min(ndist[i][j], ndist[i][nz * m + nw] + ndist[nz * m + nw][nx * m + ny] + ndist[nx * m + ny][j]);
}
}
int sum = 0;
rep(i, 0, n) {
int ti = ndist[a[i] * m + b[i]][c[i] * m + d[i]];
rep(j, 0, 1000) {
if((ti - 233 * j) % 1000 == 0) {
sum += j;
break;
}
}
}
if(sum > ma) {
ma = sum;
mx = nx;
my = ny;
mz = nz;
mw = nw;
}
}
}
}
ty[day] = 1;
x[day] = mx;
y[day] = my;
z[day] = mz;
w[day] = mw;
cnt = ma;
money -= ll(2e6);
money += 60ll * cnt;
} else {
int ma = 0;
int mx = -1, my = -1, mz = -1, mw = -1;
rep(dir, 0, 4) {
int nx = curx, ny = cury, nz = nx + dx[dir], nw = ny + dy[dir];
if(nz < 0 or m <= nz or nw < 0 or m <= nw) continue;
vector<vector<int>> ndist = dist;
ndist[nx * m + ny][nz * m + nw] = 223;
ndist[nz * m + nw][nx * m + ny] = 223;
rep(i, 0, m * m) {
rep(j, 0, m * m) {
ndist[i][j] = min(ndist[i][j], ndist[i][nx * m + ny] + ndist[nx * m + ny][nz * m + nw] + ndist[nz * m + nw][j]);
ndist[i][j] = min(ndist[i][j], ndist[i][nz * m + nw] + ndist[nz * m + nw][nx * m + ny] + ndist[nx * m + ny][j]);
}
}
int sum = 0;
rep(i, 0, n) {
int ti = ndist[a[i] * m + b[i]][c[i] * m + d[i]];
rep(j, 0, 1000) {
if((ti - 233 * j) % 1000 == 0) {
sum += j;
break;
}
}
}
if(sum > ma) {
ma = sum;
mx = nx;
my = ny;
mz = nz;
mw = nw;
}
}
if(60ll * (ma - cnt) * (t - day) >= ll(2e6)) {
ty[day] = 1;
x[day] = mx;
y[day] = my;
z[day] = mz;
w[day] = mw;
cnt = ma;
money -= ll(2e6);
money += 60ll * cnt;
} else {
ty[day] = 3;
money += ll(5e4);
money += 60ll * cnt;
}
}
}
rep(i, 0, t) {
if(ty[i] == 1) {
cout << ty[i] << ' ' << x[i] + 1 << ' ' << y[i] + 1 << ' ' << z[i] + 1 << ' ' << w[i] + 1 << endl;
} else {
cout << ty[i] << endl;
}
}
}