結果
| 問題 | No.5016 Worst Mayor |
| ユーザー |
 MMRZ
|
| 提出日時 | 2023-04-29 15:58:11 |
| 言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 9,600 bytes |
| コンパイル時間 | 3,100 ms |
| コンパイル使用メモリ | 229,428 KB |
| 実行使用メモリ | 26,172 KB |
| スコア | 0 |
| 平均クエリ数 | 8.00 |
| 最終ジャッジ日時 | 2023-04-29 15:58:23 |
| 合計ジャッジ時間 | 7,966 ms |
|
ジャッジサーバーID （参考情報） |
judge13 / judge12 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | WA | - |
| testcase_01 | TLE | - |
| testcase_02 | -- | - |
| testcase_03 | -- | - |
| testcase_04 | -- | - |
| testcase_05 | -- | - |
| testcase_06 | -- | - |
| testcase_07 | -- | - |
| testcase_08 | -- | - |
| testcase_09 | -- | - |
| testcase_10 | -- | - |
| testcase_11 | -- | - |
| testcase_12 | -- | - |
| testcase_13 | -- | - |
| testcase_14 | -- | - |
| testcase_15 | -- | - |
| testcase_16 | -- | - |
| testcase_17 | -- | - |
| testcase_18 | -- | - |
| testcase_19 | -- | - |
| testcase_20 | -- | - |
| testcase_21 | -- | - |
| testcase_22 | -- | - |
| testcase_23 | -- | - |
| testcase_24 | -- | - |
| testcase_25 | -- | - |
| testcase_26 | -- | - |
| testcase_27 | -- | - |
| testcase_28 | -- | - |
| testcase_29 | -- | - |
| testcase_30 | -- | - |
| testcase_31 | -- | - |
| testcase_32 | -- | - |
| testcase_33 | -- | - |
| testcase_34 | -- | - |
| testcase_35 | -- | - |
| testcase_36 | -- | - |
| testcase_37 | -- | - |
| testcase_38 | -- | - |
| testcase_39 | -- | - |
| testcase_40 | -- | - |
| testcase_41 | -- | - |
| testcase_42 | -- | - |
| testcase_43 | -- | - |
| testcase_44 | -- | - |
| testcase_45 | -- | - |
| testcase_46 | -- | - |
| testcase_47 | -- | - |
| testcase_48 | -- | - |
| testcase_49 | -- | - |
ソースコード
# 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 = 21;
}ks;
const int n = 3000, t = 400, w = 14;
const LL require = 2182178;
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;
int constructed_cnt = 1;
{ // 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;
debug(45, ks.score + cur_c_sum * (t - 45));
}else{
ans[45].order = 3;
ks.score += 50000;
}
}
for(int day = 46;day < t;day++){ // 46日目以降。橋の検討はざっくりでよい（じゃないと間に合わん）。
if(ks.score >= require){
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;
assert(tmp_dist[a[x] * w + b[x]][c[x] * w + d[x]].highway_cnt <= constructed_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;
assert(tmp_dist[a[x] * w + b[x]][c[x] * w + d[x]].highway_cnt <= constructed_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].order = 1;
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;
constructed_cnt++;
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();
}
}
}
int main(){
input();
auto f = solve();
output(f);
}