結果

問題 No.5016 Worst Mayor
ユーザー shibh308shibh308
提出日時 2023-04-29 16:02:55
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 1,432 ms / 2,000 ms
コード長 10,484 bytes
コンパイル時間 3,687 ms
コンパイル使用メモリ 249,940 KB
実行使用メモリ 24,408 KB
スコア 16,805,743,752
平均クエリ数 400.00
最終ジャッジ日時 2023-04-29 16:04:17
合計ジャッジ時間 77,955 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge12
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1,415 ms
24,192 KB
testcase_01 AC 1,378 ms
23,304 KB
testcase_02 AC 1,383 ms
24,252 KB
testcase_03 AC 1,385 ms
24,096 KB
testcase_04 AC 1,388 ms
23,928 KB
testcase_05 AC 1,389 ms
23,940 KB
testcase_06 AC 1,391 ms
23,304 KB
testcase_07 AC 1,387 ms
24,276 KB
testcase_08 AC 1,363 ms
23,592 KB
testcase_09 AC 1,382 ms
23,556 KB
testcase_10 AC 1,371 ms
23,904 KB
testcase_11 AC 1,409 ms
23,460 KB
testcase_12 AC 1,383 ms
23,472 KB
testcase_13 AC 1,410 ms
23,700 KB
testcase_14 AC 1,376 ms
23,292 KB
testcase_15 AC 1,379 ms
23,340 KB
testcase_16 AC 1,384 ms
23,472 KB
testcase_17 AC 1,385 ms
23,892 KB
testcase_18 AC 1,419 ms
23,556 KB
testcase_19 AC 1,402 ms
23,448 KB
testcase_20 AC 1,391 ms
23,952 KB
testcase_21 AC 1,374 ms
23,688 KB
testcase_22 AC 1,363 ms
24,120 KB
testcase_23 AC 1,378 ms
24,180 KB
testcase_24 AC 1,379 ms
23,604 KB
testcase_25 AC 1,356 ms
23,292 KB
testcase_26 AC 1,395 ms
24,276 KB
testcase_27 AC 1,376 ms
24,408 KB
testcase_28 AC 1,408 ms
24,108 KB
testcase_29 AC 1,381 ms
23,448 KB
testcase_30 AC 1,432 ms
23,604 KB
testcase_31 AC 1,386 ms
23,448 KB
testcase_32 AC 1,381 ms
23,688 KB
testcase_33 AC 1,388 ms
24,408 KB
testcase_34 AC 1,377 ms
23,292 KB
testcase_35 AC 1,395 ms
24,180 KB
testcase_36 AC 1,405 ms
23,448 KB
testcase_37 AC 1,383 ms
23,940 KB
testcase_38 AC 1,372 ms
23,592 KB
testcase_39 AC 1,377 ms
24,180 KB
testcase_40 AC 1,368 ms
23,748 KB
testcase_41 AC 1,377 ms
23,568 KB
testcase_42 AC 1,386 ms
24,252 KB
testcase_43 AC 1,392 ms
23,448 KB
testcase_44 AC 1,401 ms
23,712 KB
testcase_45 AC 1,376 ms
23,556 KB
testcase_46 AC 1,371 ms
23,568 KB
testcase_47 AC 1,375 ms
24,096 KB
testcase_48 AC 1,364 ms
23,568 KB
testcase_49 AC 1,365 ms
24,264 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
// #include "atcoder/all"

using namespace std;

using i64 = long long;

const i64 MOD = 1e9 + 7;
const i64 INF = i64(1e18);

template <typename T>
bool chmin(T& x, T y){
    if(x > y){
        x = y;
        return true;
    }
    return false;
}

template <typename T>
bool chmax(T& x, T y){
    if(x < y){
        x = y;
        return true;
    }
    return false;
}



namespace Rnd{
    // doc: https://shibh308.github.io/library/library/lib/functions/xorshift.cpp.html
    uint64_t x = 0xdeadbeef0110dead;
    uint64_t rnd(){
        x ^= x << 7;
        x ^= x >> 9;
        return x;
    }
    uint64_t rnd(int n){
        return rnd() % n;
    }
    double rnd_double(){
        return 1.0 * rnd() / numeric_limits<uint64_t>::max();
    }
    vector<int> rnd_perm(int n){
        vector<int> v(n);
        iota(v.begin(), v.end(), 0);
        for(int i = n - 1; i >= 1; --i){
            int j = rnd(i + 1);
            swap(v[i], v[j]);
        }
        return v;
    }
    template<typename T>
    void shuffle(vector<T>& v){
        int n = v.size();
        for(int i = n - 1; i >= 1; --i){
            int j = rnd(i + 1);
            swap(v[i], v[j]);
        }
    }
}


namespace params{
void load_params(){
    ifstream ifs("../params.txt");
    assert(ifs.is_open());
}
}


constexpr int n = 14;
constexpr int m = 3000;
constexpr int turn_max = 400;
vector<int> stx, sty, enx, eny;


void read_file(istream& ifs){
    int _1, _2;
    ifs >> _1 >> _2;
    stx.resize(m);
    sty.resize(m);
    enx.resize(m);
    eny.resize(m);
    for(int i = 0; i < m; ++i){
        ifs >> stx[i] >> sty[i] >> enx[i] >> eny[i];
        --stx[i];
        --sty[i];
        --enx[i];
        --eny[i];
    }
}

clock_t st_clock;

void solve(){
    // (x, y) -> (x+1, y)
    array<bitset<n>, n-1> x_flag;
    // (x, y) -> (x, y+1)
    array<bitset<n-1>, n> y_flag;

    i64 person, money;

    vector<int> dx{0, 1, 0, -1};
    vector<int> dy{1, 0, -1, 0};

    vector<vector<pair<int, int>>> dist;
    auto calc_dist = [&](){
        dist.assign(196, vector<pair<int, int>>(196, {MOD, MOD}));
        for(int i = 0; i < 196; ++i){
            priority_queue<tuple<double, pair<int,int>, int>, vector<tuple<double, pair<int,int>, int>>, greater<>> que;
            dist[i][i] = make_pair(0, 0);
            que.emplace(0.0, make_pair(0, 0), i);
            while(!que.empty()){
                auto [dis, tup, pos] = que.top();
                que.pop();
                if(dist[i][pos] != tup){
                    continue;
                }
                int x = pos / n;
                int y = pos % n;
                for(int d = 0; d < 4; ++d){
                    int nx = x + dx[d];
                    int ny = y + dy[d];
                    if(nx < 0 || ny < 0 || nx >= n || ny >= n){
                        continue;
                    }
                    int mx = min(x, nx);
                    int my = min(y, ny);
                    int nex = nx * n + ny;
                    bool is_x = x != nx;
                    bool is_fast = is_x ? x_flag[mx][my] : y_flag[mx][my];
                    pair<int,int> tup_nex = {tup.first + is_fast, tup.second + !is_fast};
                    double dis_pre = dist[i][nex].first * 0.223 + dist[i][nex].second * 1.000;
                    double dis_nex = tup_nex.first * 0.223 + tup_nex.second * 1.000;
                    if(dis_nex < dis_pre){
                        dist[i][nex] = tup_nex;
                        que.emplace(dis_nex, tup_nex, nex);
                    }
                }
            }
        }
    };

    auto check = [&](int x, int y, bool is_x){
        int ofs_x = 2 + x * 3;
        int ofs_y = 2 + y * 3;
        if(is_x ? x_flag[ofs_x][ofs_y] : y_flag[ofs_x][ofs_y]){
            return -INF;
        }
        i64 sum = 0;
        for(int i = 0; i < m; ++i){
            auto tup = dist[stx[i] * n + sty[i]][enx[i] * n + eny[i]];
            for(int j = 0; j < 4; ++j){
                for(int k = 0; k < 4; ++k){
                    int pos_jx = ofs_x + (is_x ? j : 0);
                    int pos_jy = ofs_y + (is_x ? 0 : j);
                    int pos_j = pos_jx * n + pos_jy;
                    int pos_kx = ofs_x + (is_x ? k + 1 : 0);
                    int pos_ky = ofs_y + (is_x ? 0 : k + 1);
                    int pos_k = pos_kx * n + pos_ky;
                    int dis = abs(j - k);
                    int d_first = dist[stx[i] * n + sty[i]][pos_j].first + dis + dist[pos_k][enx[i] * n + eny[i]].first;
                    int d_second = dist[stx[i] * n + sty[i]][pos_j].second + dist[pos_k][enx[i] * n + eny[i]].second;
                    double bef_dist = tup.first * 0.223 + tup.second;
                    double nex_dist = d_first * 0.223 + d_second;
                    if(nex_dist < bef_dist){
                        tup = make_pair(d_first, d_second);
                    }
                }
            }
            sum += tup.first;
        }
        return sum;
    };

    vector<tuple<int,int,bool>> v;
    for(int _ = 0; _ < 24; ++_){
        calc_dist();
        tuple<i64,int,int,bool> sc(-INF, 0, 0, false);
        for(int i = 0; i < 3; ++i){
            for(int j = 0; j < 4; ++j){
                chmax(sc, make_tuple(check(i, j, true), i, j, true));
            }
        }
        for(int i = 0; i < 4; ++i){
            for(int j = 0; j < 3; ++j){
                chmax(sc, make_tuple(check(i, j, false), i, j, false));
            }
        }
        auto [_1, x, y, is_x] = sc;
        int ofs_x = 2 + x * 3;
        int ofs_y = 2 + y * 3;
        for(int i = 0; i < 3; ++i){
            if(is_x){
                x_flag[ofs_x + i][ofs_y] = true;
            }
            else{
                y_flag[ofs_x][ofs_y + i] = true;
            }
        }
        v.emplace_back(x, y, is_x);
    }
    vector<vector<i64>> table(24, vector<i64>(8, 0));
    for(auto& fl : x_flag){
        fl.reset();
    }
    for(auto& fl : y_flag){
        fl.reset();
    }
    for(int i = 0; i < 24; ++i){
        auto [x, y, is_x] = v[i];
        int ofs_x = 2 + x * 3;
        int ofs_y = 2 + y * 3;

        for(int j = 0; j < (1 << 3); ++j){
            for(int k = 0; k < 3; ++k){
                if(is_x){
                    x_flag[ofs_x + k][ofs_y] = bool(j & (1 << k));
                }
                else{
                    y_flag[ofs_x][ofs_y + k] = bool(j & (1 << k));
                }
            }
            calc_dist();
            i64 adv = 0;
            for(int k = 0; k < m; ++k){
                adv += dist[stx[k] * n + sty[k]][enx[k] * n + eny[k]].first;
            }
            table[i][j] = adv * 60;
        }

        for(int j = 0; j < 3; ++j){
            if(is_x){
                x_flag[ofs_x + j][ofs_y] = true;
            }
            else{
                y_flag[ofs_x][ofs_y + j] = true;
            }
        }
    }

    // dp[turn][group][flag]
    vector<vector<vector<i64>>> dp(turn_max + 1, vector<vector<i64>>(25, vector<i64>(8, -INF)));
    vector<vector<vector<int>>> mov(turn_max + 1, vector<vector<int>>(25, vector<int>(8, -3)));
    dp[0][0][0] = 1e6;
    for(int i = 0; i < turn_max; ++i){
        if(dp[i][24][0] != -INF){
            dp[i + 1][24][0] = dp[i][24][0] + 50000;
            mov[i + 1][24][0] = -3;
        }
        for(int j = 0; j < 24; ++j){
            for(int k = 0; k < 8; ++k){
                if(dp[i][j][k] == -INF){
                    continue;
                }
                for(int fl = 0; fl < 3; ++fl){
                    if(k & (1 << fl)){
                        continue;
                    }
                    i64 human = i - (j * 3 + __builtin_popcount(k)) + 1;

                    // add human
                    if(chmax(dp[i + 1][j][k], dp[i][j][k] + table[j][k])){
                        mov[i + 1][j][k] = -2;
                    }

                    i64 cost = ceil(1e7 / sqrt(human));
                    if(dp[i][j][k] < cost){
                        continue;
                    }
                    i64 sc = dp[i][j][k] - cost + table[j][k];
                    if((k | (1 << fl)) == 7){
                        if(chmax(dp[i + 1][j + 1][0], sc)){
                            mov[i + 1][j + 1][0] = fl;
                        }
                    }
                    else{
                        if(chmax(dp[i + 1][j][k | (1 << fl)], sc)){
                            mov[i + 1][j][k | (1 << fl)] = fl;
                        }
                    }
                }
            }
        }
    }
    // cout << "end: " << double(clock() - st_clock) / CLOCKS_PER_SEC << endl;
    int j = 24, k = 0;
    vector<int> types(turn_max);
    vector<pair<pair<int,int>, pair<int,int>>> moves(turn_max);
    vector<int> moneys(turn_max);
    for(int i = turn_max; i > 0; --i){
        moneys[i - 1] = dp[i][j][k];
        if(mov[i][j][k] == -3){
            types[i - 1] = 3;
        }
        else if(mov[i][j][k] == -2){
            types[i - 1] = 2;
        }
        else{
            types[i - 1] = 1;
            int idx = mov[i][j][k];
            if(k == 0){
                --j;
                k = 7 & ~(1 << idx);
            }
            else{
                k &= ~(1 << idx);
            }

            auto [x, y, is_x] = v[j];

            int ofs_x = 2 + x * 3;
            int ofs_y = 2 + y * 3;
            if(is_x){
                auto p1 = make_pair(ofs_x + idx, ofs_y);
                auto p2 = make_pair(ofs_x + idx + 1, ofs_y);
                moves[i - 1] = make_pair(p1, p2);
            }
            else{
                auto p1 = make_pair(ofs_x, ofs_y + idx);
                auto p2 = make_pair(ofs_x, ofs_y + idx + 1);
                moves[i - 1] = make_pair(p1, p2);
            }
        }
    }
    for(int i = 0; i < turn_max; ++i){
        cin >> money >> person;
        if(types[i] == 1){
            cout << 1 << " ";
            cout << moves[i].first.first + 1 << " " << moves[i].first.second + 1 << " ";
            cout << moves[i].second.first + 1 << " " << moves[i].second.second + 1 << endl;
        }
        else{
            cout << types[i] << endl;
        }
    }
    // cout << dp.back().back()[0] << endl;
}

signed main(){

    st_clock = clock();

#ifdef OPTIMIZE
    params::load_params();
#endif

#ifndef HAND
    read_file(cin);
#else
    ifstream ifs("../contests/yukisc5/in0.txt");
    assert(ifs.is_open());
    read_file(ifs);
#endif

    solve();

}
0