結果

問題 No.5016 Worst Mayor
ユーザー MMRZMMRZ
提出日時 2023-04-29 15:34:32
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 182 ms / 2,000 ms
コード長 9,673 bytes
コンパイル時間 2,908 ms
コンパイル使用メモリ 224,232 KB
実行使用メモリ 24,384 KB
スコア 1,126,589,000
平均クエリ数 400.00
最終ジャッジ日時 2023-04-29 15:34:48
合計ジャッジ時間 13,814 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge11
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 158 ms
23,400 KB
testcase_01 AC 155 ms
23,388 KB
testcase_02 AC 156 ms
23,688 KB
testcase_03 AC 155 ms
24,228 KB
testcase_04 AC 150 ms
23,628 KB
testcase_05 AC 157 ms
23,832 KB
testcase_06 AC 157 ms
23,832 KB
testcase_07 AC 155 ms
24,384 KB
testcase_08 AC 168 ms
23,844 KB
testcase_09 AC 155 ms
23,376 KB
testcase_10 AC 155 ms
24,360 KB
testcase_11 AC 152 ms
23,424 KB
testcase_12 AC 152 ms
23,616 KB
testcase_13 AC 156 ms
23,412 KB
testcase_14 AC 182 ms
23,556 KB
testcase_15 AC 156 ms
23,556 KB
testcase_16 AC 156 ms
23,544 KB
testcase_17 AC 156 ms
23,424 KB
testcase_18 AC 155 ms
24,000 KB
testcase_19 AC 157 ms
23,628 KB
testcase_20 AC 182 ms
23,676 KB
testcase_21 AC 156 ms
23,844 KB
testcase_22 AC 154 ms
23,400 KB
testcase_23 AC 155 ms
24,024 KB
testcase_24 AC 157 ms
23,832 KB
testcase_25 AC 156 ms
23,844 KB
testcase_26 AC 167 ms
23,832 KB
testcase_27 AC 151 ms
24,036 KB
testcase_28 AC 154 ms
24,000 KB
testcase_29 AC 154 ms
23,544 KB
testcase_30 AC 155 ms
23,400 KB
testcase_31 AC 156 ms
24,348 KB
testcase_32 AC 157 ms
24,024 KB
testcase_33 AC 155 ms
23,856 KB
testcase_34 AC 155 ms
23,436 KB
testcase_35 AC 156 ms
23,820 KB
testcase_36 AC 155 ms
24,012 KB
testcase_37 AC 177 ms
24,324 KB
testcase_38 AC 155 ms
24,000 KB
testcase_39 AC 156 ms
23,556 KB
testcase_40 AC 156 ms
23,388 KB
testcase_41 AC 155 ms
24,228 KB
testcase_42 AC 155 ms
24,000 KB
testcase_43 AC 155 ms
24,228 KB
testcase_44 AC 151 ms
23,544 KB
testcase_45 AC 172 ms
23,652 KB
testcase_46 AC 155 ms
24,000 KB
testcase_47 AC 156 ms
23,544 KB
testcase_48 AC 157 ms
23,556 KB
testcase_49 AC 154 ms
23,652 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

# include "bits/stdc++.h"
using namespace std;
using LL = long long;
# define all(qpqpq)           (qpqpq).begin(),(qpqpq).end()
# define UNIQUE(wpwpw)        sort(ALL((wpwpw)));(wpwpw).erase(unique(ALL((wpwpw))),(wpwpw).end())
# define rep(i,upupu)         for(int i = 0, i##_len = (upupu);(i) < (i##_len);(i)++)

#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")

#ifdef LOCAL
#  include "_debug_print.hpp"
#  define debug(...) debug_print::multi_print(#__VA_ARGS__, __VA_ARGS__)
#else
#  define debug(...) (static_cast<void>(0))
#endif

const double TIME_LIMIT = 2000.0;

class xor_shift_128 {
public:
    typedef uint32_t result_type;
    xor_shift_128(uint32_t seed = 42) {
        set_seed(seed);
    }
    void set_seed(uint32_t seed) {
        a = seed = 1812433253u * (seed ^ (seed >> 30));
        b = seed = 1812433253u * (seed ^ (seed >> 30)) + 1;
        c = seed = 1812433253u * (seed ^ (seed >> 30)) + 2;
        d = seed = 1812433253u * (seed ^ (seed >> 30)) + 3;
    }
    uint32_t operator() () {
        uint32_t t = (a ^ (a << 11));
        a = b; b = c; c = d;
        return d = (d ^ (d >> 19)) ^ (t ^ (t >> 8));
    }
    static constexpr uint32_t max() { return numeric_limits<result_type>::max(); }
    static constexpr uint32_t min() { return numeric_limits<result_type>::min(); }
private:
    uint32_t a, b, c, d;
};

xor_shift_128 gen;

//[_first, _second] の（たぶん）一様分布
#define RND(_first, _second)    uniform_int_distribution<int>(_first, _second)(gen)

struct plan {
    int order;
    int x, y, z, w;
};

struct KYOPRO_status {
    LL score = 1000000;
    const int coops = 20;
}ks;

const int n = 3000, t = 400, w = 14;
const LL require = 2236067;
int a[n], b[n], c[n], d[n];

struct KYOPRO_dist {
    int normal_cnt = 0, highway_cnt = 0;

    bool operator<( const KYOPRO_dist& right ) const {
        return double(normal_cnt) + 0.223 * highway_cnt < double(right.normal_cnt) + 0.223 * right.highway_cnt;
    }
};

vector<plan> solve(){
    vector<plan> ans(t);
    rep(i, 20)ans[i].order = 2;
    for(int i = 20;i < 45;i++){
        ans[i].order = 3;
        ks.score += 50000;
    }

    vector<vector<KYOPRO_dist>> dist(w * w, vector<KYOPRO_dist>(w * w)), buf_dist;
    rep(i, w * w)rep(j, w * w){
        dist[i][j].normal_cnt = (abs(i % w - j % w) + abs(i / w + j / w));
    }

    vector<vector<vector<bool>>> constructed(w, vector<vector<bool>>(w, vector<bool>(2, false)));

    LL cur_c_sum = 0;

    { // 45日目の橋建設。大切なので、最適解を見つける。
        ans[45].order = 1;

        int max_c = 0, max_type = -1, mi = -1, mj = -1;

        { // tate
            rep(i, 13)rep(j, 14){
                auto tmp_dist = dist;

                int s = i * w + j;
                int t = (i + 1) * w + j;

                tmp_dist[s][t] = tmp_dist[t][s] = min(tmp_dist[s][t], KYOPRO_dist{tmp_dist[s][t].normal_cnt - 1, tmp_dist[s][t].highway_cnt + 1});

                for(int k : {s, t}){
                    rep(row, w * w)rep(column, w * w){
                        tmp_dist[row][column] = min(tmp_dist[row][column], KYOPRO_dist{tmp_dist[row][k].normal_cnt + tmp_dist[k][column].normal_cnt, tmp_dist[row][k].highway_cnt + tmp_dist[k][column].highway_cnt});
                    }
                }

                LL cnt_c = 0;

                rep(x, n){
                    cnt_c += tmp_dist[a[x] * w + b[x]][c[x] * w + d[x]].highway_cnt;
                }

                if(max_c < cnt_c){
                    max_c = cnt_c;
                    max_type = 0;
                    mi = i, mj = j;
                    buf_dist = tmp_dist;
                }
            }
        }

        { // yoko
            rep(i, 14)rep(j, 13){
                auto tmp_dist = dist;

                int s = i * w + j;
                int t = i * w + j + 1;

                tmp_dist[s][t] = tmp_dist[t][s] = min(tmp_dist[s][t], KYOPRO_dist{tmp_dist[s][t].normal_cnt - 1, tmp_dist[s][t].highway_cnt + 1});

                for(int k : {s, t}){
                    rep(row, w * w)rep(column, w * w){
                        tmp_dist[row][column] = min(tmp_dist[row][column], KYOPRO_dist{tmp_dist[row][k].normal_cnt + tmp_dist[k][column].normal_cnt, tmp_dist[row][k].highway_cnt + tmp_dist[k][column].highway_cnt});
                    }
                }

                LL cnt_c = 0;

                rep(x, n){
                    cnt_c += tmp_dist[a[x] * w + b[x]][c[x] * w + d[x]].highway_cnt;
                }

                if(max_c < cnt_c){
                    max_c = cnt_c;
                    max_type = 1;
                    mi = i, mj = j;
                    buf_dist = tmp_dist;
                }
            }
        }

        if(max_c > cur_c_sum){
            ans[45].x = mi, ans[45].y = mj;
            ans[45].z = mi + (max_type == 0), ans[45].w = mj + (max_type == 1);
            ks.score -= require;

            cur_c_sum = max_c;

            dist = buf_dist;
        }else{
            ans[45].order = 3;
            ks.score += 50000;
        }
    }

    for(int day = 46;day < t;day++){
        ans[day].order = 3;
    }

    /*
    for(int day = 46;day < t;day++){ // 46日目以降。橋の検討はざっくりでよい（じゃないと間に合わん）。

        if(ks.score >= require){
            ans[day].order = 1;

            int max_c = 0, max_type = -1, mi = -1, mj = -1;

            int q = 10;

            while(q--){

                int c_type, ci, cj;

                do{
                    c_type = RND(0, 1);
                    ci = RND(0, 13 - (c_type == 0));
                    cj = RND(0, 13 - (c_type == 1));
                }while(constructed[ci][cj][c_type]);

                if(c_type == 0){ // tate
                    auto tmp_dist = dist;

                    int s = ci * w + cj;
                    int t = (ci + 1) * w + cj;

                    tmp_dist[s][t] = tmp_dist[t][s] = min(tmp_dist[s][t], KYOPRO_dist{tmp_dist[s][t].normal_cnt - 1, tmp_dist[s][t].highway_cnt + 1});

                    if(tmp_dist[s][t].normal_cnt < 0)continue;

                    for(int k : {s, t}){
                        rep(row, w * w)rep(column, w * w){
                            tmp_dist[row][column] = min(tmp_dist[row][column], KYOPRO_dist{tmp_dist[row][k].normal_cnt + tmp_dist[k][column].normal_cnt, tmp_dist[row][k].highway_cnt + tmp_dist[k][column].highway_cnt});
                        }
                    }

                    LL cnt_c = 0;

                    rep(x, n){
                        cnt_c += tmp_dist[a[x] * w + b[x]][c[x] * w + d[x]].highway_cnt;
                    }

                    if(max_c < cnt_c){
                        max_c = cnt_c;
                        max_type = 0;
                        mi = ci, mj = cj;
                        buf_dist = tmp_dist;
                    }
                }else{ // yoko
                    auto tmp_dist = dist;

                    int s = ci * w + cj;
                    int t = ci * w + cj + 1;

                    tmp_dist[s][t] = tmp_dist[t][s] = min(tmp_dist[s][t], KYOPRO_dist{tmp_dist[s][t].normal_cnt - 1, tmp_dist[s][t].highway_cnt + 1});

                    if(tmp_dist[s][t].normal_cnt < 0)continue;

                    for(int k : {s, t}){
                        rep(row, w * w)rep(column, w * w){
                            tmp_dist[row][column] = min(tmp_dist[row][column], KYOPRO_dist{tmp_dist[row][k].normal_cnt + tmp_dist[k][column].normal_cnt, tmp_dist[row][k].highway_cnt + tmp_dist[k][column].highway_cnt});
                        }
                    }

                    LL cnt_c = 0;

                    rep(x, n){
                        cnt_c += tmp_dist[a[x] * w + b[x]][c[x] * w + d[x]].highway_cnt;
                    }

                    if(max_c < cnt_c){
                        max_c = cnt_c;
                        max_type = 1;
                        mi = ci, mj = cj;
                        buf_dist = tmp_dist;
                    }
                }

            }

            if(max_c > cur_c_sum){
                ans[day].x = mi, ans[day].y = mj;
                ans[day].z = mi + (max_type == 0), ans[day].w = mj + (max_type == 1);
                constructed[mi][mj][max_type] = true;
                ks.score -= require;

                cur_c_sum = max_c;

                dist = buf_dist;
            }else{
                ans[day].order = 3;
                ks.score += 50000;
            }
        }else{
            ans[day].order = 3;
            ks.score += 50000;
        }
        ks.score += cur_c_sum * 60;
    }
    */

    return ans;
}

void input(){
    int _n, _t; cin >> _n >> _t;
    rep(i, n){
        cin >> a[i] >> b[i] >> c[i] >> d[i];
        a[i]--, b[i]--, c[i]--, d[i]--;
    }
    return;
}

void output(vector<plan> ans){
    
    LL buf;

    rep(i, t){

        //手元だとここ消してるからね！

        //if(i)cin >> buf >> buf;

        if(ans[i].order != 1){
            cout << ans[i].order << endl;
            cout.flush();
        }else{

            cout << "1 " << ans[i].x + 1 << " " << ans[i].y + 1 << " " << ans[i].z + 1 << " " << ans[i].w + 1 << endl;
            cout.flush();

            assert(1 <= ans[i].x + 1 && ans[i].x + 1 <= 14);
            assert(1 <= ans[i].y + 1 && ans[i].y + 1 <= 14);
            assert(1 <= ans[i].z + 1 && ans[i].z + 1 <= 14);
            assert(1 <= ans[i].w + 1 && ans[i].w + 1 <= 14);

            assert(abs(ans[i].x - ans[i].z) + abs(ans[i].y - ans[i].w) == 1);
        }
    }
}

int main(){
    input();
    auto f = solve();
    output(f);
}
0