結果

問題 No.5016 Worst Mayor
ユーザー Fu_LFu_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 -- -
権限があれば一括ダウンロードができます

ソースコード

diff #

#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;
        }
    }
}
0