結果

問題 No.5016 Worst Mayor
ユーザー Fu_LFu_L
提出日時 2023-04-29 16:59:55
言語 C++17
(gcc 12.3.0 + boost 1.83.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
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 235 ms
24,324 KB
testcase_01 AC 235 ms
23,472 KB
testcase_02 AC 243 ms
24,312 KB
testcase_03 WA -
testcase_04 AC 232 ms
23,676 KB
testcase_05 AC 281 ms
23,628 KB
testcase_06 WA -
testcase_07 AC 253 ms
23,652 KB
testcase_08 AC 245 ms
23,652 KB
testcase_09 WA -
testcase_10 AC 244 ms
24,372 KB
testcase_11 AC 225 ms
23,460 KB
testcase_12 AC 263 ms
23,820 KB
testcase_13 AC 244 ms
23,628 KB
testcase_14 AC 230 ms
24,072 KB
testcase_15 AC 222 ms
24,324 KB
testcase_16 AC 226 ms
24,036 KB
testcase_17 AC 238 ms
23,460 KB
testcase_18 AC 213 ms
23,592 KB
testcase_19 WA -
testcase_20 AC 258 ms
24,048 KB
testcase_21 AC 230 ms
24,324 KB
testcase_22 AC 239 ms
23,388 KB
testcase_23 AC 231 ms
23,352 KB
testcase_24 AC 232 ms
24,348 KB
testcase_25 AC 251 ms
23,808 KB
testcase_26 AC 234 ms
23,436 KB
testcase_27 WA -
testcase_28 AC 235 ms
23,580 KB
testcase_29 AC 242 ms
23,400 KB
testcase_30 AC 236 ms
24,312 KB
testcase_31 AC 247 ms
24,384 KB
testcase_32 AC 244 ms
23,688 KB
testcase_33 AC 232 ms
23,364 KB
testcase_34 AC 233 ms
23,424 KB
testcase_35 AC 231 ms
23,640 KB
testcase_36 AC 229 ms
23,388 KB
testcase_37 WA -
testcase_38 AC 236 ms
23,460 KB
testcase_39 WA -
testcase_40 AC 238 ms
23,424 KB
testcase_41 AC 219 ms
24,024 KB
testcase_42 AC 241 ms
23,880 KB
testcase_43 AC 243 ms
23,364 KB
testcase_44 AC 238 ms
24,024 KB
testcase_45 WA -
testcase_46 AC 225 ms
24,168 KB
testcase_47 AC 252 ms
23,460 KB
testcase_48 WA -
testcase_49 AC 214 ms
23,424 KB
権限があれば一括ダウンロードができます

ソースコード

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