結果

問題 No.5016 Worst Mayor
コンテスト
ユーザー Fu_L
提出日時 2023-04-29 16:59:55
言語 C++17(gcc12)
(gcc 12.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 3,863 bytes
コンパイル時間 3,257 ms
コンパイル使用メモリ 203,188 KB
実行使用メモリ 24,492 KB
スコア 11,304,285,920
平均クエリ数 365.62
最終ジャッジ日時 2023-04-29 17:03:54
合計ジャッジ時間 17,483 ms
ジャッジサーバーID
（参考情報） 		judge16 / judge15
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 41 WA * 9
権限があれば一括ダウンロードができます

ソースコード

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 == -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<< endl;
    }
}
0