結果

問題 No.5016 Worst Mayor
コンテスト
ユーザー Fu_L
提出日時 2023-04-29 16:23:47
言語 C++17(gcc12)
(gcc 12.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 4,144 bytes
コンパイル時間 5,291 ms
コンパイル使用メモリ 267,320 KB
実行使用メモリ 25,552 KB
スコア 0
最終ジャッジ日時 2023-04-29 16:25:12
合計ジャッジ時間 12,046 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge16
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other TLE * 1 -- * 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) {
        ll u, v;
        cin >> u >> v;
        assert(u == money);
        if(day <= 23) {
            ty[day] = 2;
            cout << ty[day] << endl;
            money += 60ll * cnt;
            continue;
        }
        if(money < ll(2e6)) {
            ty[day] = 3;
            cout << ty[day] << endl;
            money += ll(5e4);
            money += 60ll * cnt;
            continue;
        }
        if(curx == -1 and cury == -1) {
            curx = rng(0, 13), cury = rng(0, 13);
        }
        ll ma = 0;
        int mx = -1, my = -1, mz = -1, mw = -1;
        vector<vector<int>> mdist;
        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]);
                }
            }
            ll 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 - 223 * j) % 1000 == 0) {
                        sum += j;
                        break;
                    }
                }
            }
            if(sum > ma) {
                ma = sum;
                mx = nx;
                my = ny;
                mz = nz;
                mw = nw;
                mdist = ndist;
            }
        }
        // cout << ma << " " << cnt << endl;
        if(60ll * (ma - cnt) * (t - day) >= ll(2e6)) {
            ty[day] = 1;
            x[day] = mx;
            y[day] = my;
            z[day] = mz;
            w[day] = mw;
            cout << ty[day] << ' ' << x[day] + 1 << ' ' << y[day] + 1 << ' ' << z[day] + 1 << ' ' << w[day] + 1 << endl;
            curx = z[day];
            cury = w[day];
            dist = mdist;
            cnt = ma;
            money -= ll(2e6);
            money += 60ll * cnt;
        } else {
            curx = -1;
            cury = -1;
            ty[day] = 3;
            cout << ty[day] << endl;
            money += ll(5e4);
            money += 60ll * cnt;
        }
        // cout << day << " " << cnt << " " << money << endl;
    }
}
0