結果

問題 No.5016 Worst Mayor
ユーザー Fu_LFu_L
提出日時 2023-04-29 16:54:41
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 3,947 bytes
コンパイル時間 2,258 ms
コンパイル使用メモリ 203,512 KB
実行使用メモリ 24,372 KB
スコア 0
平均クエリ数 619.24
最終ジャッジ日時 2023-04-29 16:56:40
合計ジャッジ時間 18,383 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge11
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 WA -
testcase_01 WA -
testcase_02 WA -
testcase_03 WA -
testcase_04 WA -
testcase_05 WA -
testcase_06 WA -
testcase_07 WA -
testcase_08 WA -
testcase_09 WA -
testcase_10 WA -
testcase_11 WA -
testcase_12 WA -
testcase_13 WA -
testcase_14 WA -
testcase_15 WA -
testcase_16 WA -
testcase_17 WA -
testcase_18 WA -
testcase_19 WA -
testcase_20 WA -
testcase_21 WA -
testcase_22 WA -
testcase_23 WA -
testcase_24 WA -
testcase_25 WA -
testcase_26 WA -
testcase_27 WA -
testcase_28 WA -
testcase_29 WA -
testcase_30 WA -
testcase_31 WA -
testcase_32 WA -
testcase_33 WA -
testcase_34 WA -
testcase_35 WA -
testcase_36 WA -
testcase_37 WA -
testcase_38 WA -
testcase_39 WA -
testcase_40 WA -
testcase_41 WA -
testcase_42 WA -
testcase_43 WA -
testcase_44 WA -
testcase_45 WA -
testcase_46 WA -
testcase_47 WA -
testcase_48 WA -
testcase_49 WA -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<ll, ll>;
#define rep(i, a, b) for(ll i = a; i < b; i++)
#define rrep(i, a, b) for(ll i = a; i >= b; i--)
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
int m = 14;
int n, t;
int a[3000], b[3000], c[3000], d[3000];
int dist[200][200];
int ndist[200][200];
int mdist[200][200];
int curx = -1, cury = -1;
ll cnt = 0;
ll money = 1000000;
int main(void) {
    cin.tie(0);
    ios::sync_with_stdio(0);
    cin >> n >> t;
    rep(i, 0, n) {
        cin >> a[i] >> b[i] >> c[i] >> d[i];
        a[i]--;
        b[i]--;
        c[i]--;
        d[i]--;
    }
    rep(i, 0, m * m) {
        rep(j, 0, m * m) {
            dist[i][j] = 100000000;
        }
    }
    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]);
            }
        }
    }
    rep(day, 0, t) {
        // ll u, v;
        // cin >> u >> v;
        // if(u != money) {
        //     return 0;
        // }
        // if(u == -1 and v == -1) {
        //     return 0;
        // }
        if(day <= 23) {
            cout << 2 << endl;
            money += 60 * cnt;
            continue;
        }
        if(money < 2000000) {
            cout << 3 << endl;
            money += 50000;
            money += 60 * cnt;
            continue;
        }
        if(curx == -1 and cury == -1) {
            curx = rand() % m, cury = rand() % m;
        }
        ll 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;
            rep(i, 0, m * m) {
                rep(j, 0, m * m) {
                    ndist[i][j] = dist[i][j];
                }
            }
            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;
                rep(i, 0, m * m) {
                    rep(j, 0, m * m) {
                        mdist[i][j] = ndist[i][j];
                    }
                }
            }
        }
        // cout << ma << " " << cnt << endl;
        if(60ll * (ma - cnt) * (t - day) >= 2000000) {
            cout << 1 << ' ' << mx + 1 << ' ' << my + 1 << ' ' << mz + 1 << ' ' << mw + 1 << endl;
            curx = mz;
            cury = mw;
            rep(i, 0, m * m) {
                rep(j, 0, m * m) {
                    dist[i][j] = mdist[i][j];
                }
            }
            cnt = ma;
            money -= 2000000;
            money += 60 * cnt;
        } else {
            curx = -1;
            cury = -1;
            cout << 3 << endl;
            money += 50000;
            money += 60 * cnt;
        }
        cout << day << " " << cnt << " " << money * 50 << endl;
    }
}
0