結果

問題 No.5016 Worst Mayor
ユーザー MMRZMMRZ
提出日時 2023-04-29 14:28:50
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 4,057 bytes
コンパイル時間 2,886 ms
コンパイル使用メモリ 214,544 KB
実行使用メモリ 24,276 KB
スコア 0
平均クエリ数 400.00
最終ジャッジ日時 2023-04-29 14:29:06
合計ジャッジ時間 15,702 ms
ジャッジサーバーID
（参考情報） 		judge15 / 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;
# 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")

const double TIME_LIMIT = 15000.0;

struct KYOPRO_city_status {
    int coops = 1;
    LL money = 1000000;
} kcs;

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

const int n = 3000, t = 400, w = 14;
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;

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

    int day = 45;
    {
        ans[day].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(r, w * w)rep(c, w * w){
                        tmp_dist[r][c] = min(tmp_dist[r][c], KYOPRO_dist{tmp_dist[r][k].normal_cnt + tmp_dist[k][c].normal_cnt, tmp_dist[r][k].highway_cnt + tmp_dist[k][c].highway_cnt});
                    }
                }

                int cnt_c = 0;

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

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

        { // 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(r, w * w)rep(c, w * w){
                        tmp_dist[r][c] = min(tmp_dist[r][c], KYOPRO_dist{tmp_dist[r][k].normal_cnt + tmp_dist[k][c].normal_cnt, tmp_dist[r][k].highway_cnt + tmp_dist[k][c].highway_cnt});
                    }
                }

                int cnt_c = 0;

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

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

        ans[day].x = mi, ans[day].y = mj;
        ans[day].z = mi + (max_type == 0), ans[day].w = mj + (max_type == 1);

    }

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

    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;

        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();
        }
    }
}

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