結果
| 問題 | No.5019 Hakai Project |
| ユーザー |
 ぴぃいいいい
|
| 提出日時 | 2023-11-23 19:49:41 |
| 言語 | C++23 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
RE
|
| 実行時間 | - |
| コード長 | 25,231 bytes |
| コンパイル時間 | 8,704 ms |
| コンパイル使用メモリ | 346,512 KB |
| 実行使用メモリ | 6,676 KB |
| スコア | 2,741,307,087 |
| 最終ジャッジ日時 | 2023-11-23 19:52:24 |
| 合計ジャッジ時間 | 161,841 ms |
|
ジャッジサーバーID （参考情報） |
judge14 / judge12 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 2,900 ms
6,676 KB |
| testcase_01 | AC | 2,902 ms
6,676 KB |
| testcase_02 | AC | 2,902 ms
6,676 KB |
| testcase_03 | AC | 2,901 ms
6,676 KB |
| testcase_04 | AC | 2,901 ms
6,676 KB |
| testcase_05 | AC | 2,901 ms
6,676 KB |
| testcase_06 | AC | 2,902 ms
6,676 KB |
| testcase_07 | AC | 2,901 ms
6,676 KB |
| testcase_08 | AC | 2,902 ms
6,676 KB |
| testcase_09 | AC | 2,901 ms
6,676 KB |
| testcase_10 | AC | 2,901 ms
6,676 KB |
| testcase_11 | AC | 2,902 ms
6,676 KB |
| testcase_12 | RE | - |
| testcase_13 | AC | 2,902 ms
6,676 KB |
| testcase_14 | AC | 2,900 ms
6,676 KB |
| testcase_15 | AC | 2,901 ms
6,676 KB |
| testcase_16 | AC | 2,902 ms
6,676 KB |
| testcase_17 | AC | 2,901 ms
6,676 KB |
| testcase_18 | AC | 2,901 ms
6,676 KB |
| testcase_19 | AC | 2,902 ms
6,676 KB |
| testcase_20 | AC | 2,901 ms
6,676 KB |
| testcase_21 | AC | 2,902 ms
6,676 KB |
| testcase_22 | AC | 2,902 ms
6,676 KB |
| testcase_23 | AC | 2,901 ms
6,676 KB |
| testcase_24 | AC | 2,901 ms
6,676 KB |
| testcase_25 | AC | 2,901 ms
6,676 KB |
| testcase_26 | AC | 2,901 ms
6,676 KB |
| testcase_27 | AC | 2,901 ms
6,676 KB |
| testcase_28 | AC | 2,901 ms
6,676 KB |
| testcase_29 | AC | 2,901 ms
6,676 KB |
| testcase_30 | AC | 2,901 ms
6,676 KB |
| testcase_31 | AC | 2,902 ms
6,676 KB |
| testcase_32 | AC | 2,901 ms
6,676 KB |
| testcase_33 | AC | 2,900 ms
6,676 KB |
| testcase_34 | AC | 2,901 ms
6,676 KB |
| testcase_35 | AC | 2,902 ms
6,676 KB |
| testcase_36 | AC | 2,902 ms
6,676 KB |
| testcase_37 | AC | 2,900 ms
6,676 KB |
| testcase_38 | AC | 2,902 ms
6,676 KB |
| testcase_39 | AC | 2,901 ms
6,676 KB |
| testcase_40 | AC | 2,901 ms
6,676 KB |
| testcase_41 | AC | 2,902 ms
6,676 KB |
| testcase_42 | AC | 2,901 ms
6,676 KB |
| testcase_43 | AC | 2,901 ms
6,676 KB |
| testcase_44 | AC | 2,901 ms
6,676 KB |
| testcase_45 | AC | 2,901 ms
6,676 KB |
| testcase_46 | AC | 2,901 ms
6,676 KB |
| testcase_47 | AC | 2,902 ms
6,676 KB |
| testcase_48 | AC | 2,902 ms
6,676 KB |
| testcase_49 | AC | 2,902 ms
6,676 KB |
コンパイルメッセージ
In file included from /home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.3.0/include/c++/12/vector:64,
from /home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.3.0/include/c++/12/functional:62,
from /home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.3.0/include/c++/12/x86_64-pc-linux-gnu/bits/stdc++.h:71,
from main.cpp:2:
In member function 'constexpr std::vector<_Tp, _Alloc>::reference std::vector<_Tp, _Alloc>::operator[](size_type) [with _Tp = int; _Alloc = std::allocator<int>]',
inlined from 'void Bombplan::greedy_all()' at main.cpp:171:50:
/home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.3.0/include/c++/12/bits/stl_vector.h:1124:32: warning: 'best_k' may be used uninitialized [-Wmaybe-uninitialized]
1124 | return *(this->_M_impl._M_start + __n);
| ~~~~~~~~~~~~~~^~~~~~~~
main.cpp: In member function 'void Bombplan::greedy_all()':
main.cpp:110:31: note: 'best_k' was declared here
110 | int best_i,best_j,best_k;
| ^~~~~~
main.cpp:171:50: warning: 'best_j' may be used uninitialized [-Wmaybe-uninitialized]
171 | int broken_y = best_j+b[best_k][x];
| ^
main.cpp:110:24: note: 'best_j' was declared here
110 | int best_i,best_j,best_k;
| ^~~~~~
main.cpp:170:50: warning: 'best_i' may be used uninitialized [-Wmaybe-uninitialized]
170 | int broken_x = best_i+a[best_k][x];
| ^
main.cpp:110:17: note: 'best_i' was declared here
110 | int best_i,best_j,best_k;
| ^~~~~~
ソースコード
#pragma GCC optimize("O3")
#include<bits/stdc++.h>
#include<atcoder/all>
using namespace std;
using namespace atcoder;
#define Yes(n) cout << ((n) ? "Yes" : "No" ) << endl
#define print(var) std::cout<<#var<<"="<<(var)<<std::endl
#define all(a) (a).begin(), (a).end()
#define vi vector<int>
#define vvi vector<vi>
#define vvvi vector<vvi>
#define ll long long
#define vll vector<ll>
#define vvll vector<vll>
#define vvvll vector<vvll>
#define vmi vector<mint>
#define vvmi vector<vmi>
#define vvvmi vector<vvmi>
#define vs vector<string>
#define pii pair<int,int>
#define vpii vector<pair<int,int>>
#define bit(x,i)(((x)>>(i))&1)
#define inf (1<<30)
#define INF (1ll<<60)
template<typename T> inline bool chmax(T &a, T b) { return ((a < b) ? (a = b, true) : (false)); }
template<typename T> inline bool chmin(T &a, T b) { return ((a > b) ? (a = b, true) : (false)); }
inline double get_time() {
using namespace std::chrono;
return duration_cast<milliseconds>(system_clock::now().time_since_epoch()).count();
}
unsigned long xor128(void){
static unsigned long x=123456789,y=362436069,z=521288629,w=88675123;
unsigned long t;
t=(x^(x<<11));x=y;y=z;z=w; return( w=(w^(w>>19))^(t^(t>>8)) );
}
long long randInt(long long a,long long b){return a+xor128()%(b-a+1);}
double randDouble(double a,double b){return a+(b-a)*xor128()/(double)ULONG_MAX;}
double start_time;
int n,m;
int c[20],l[20];
vector<int> a[20],b[20];
int center_shop_x,center_shop_y;
vpii around{{0,-1},{-1,0},{1,0},{0,1},{-1,-1},{-1,1},{1,-1},{1,1}};
bool is_valid(int x,int y){
return 0<=x && x<n && 0<=y && y<n;
}
struct Field{
char A[50][50];
int building = 0;
int shop = 0;
Field(){}
Field(char AA[50][50]){
for(int i=0;i<n;i++)for(int j=0;j<n;j++) A[i][j] = AA[i][j];
for(int i=0;i<n;i++)for(int j=0;j<n;j++){
if(A[i][j]=='.') continue;
if(A[i][j]=='@') shop++;
building++;
}
}
void use(int k,int x,int y){
for(int i=0;i<l[k];i++){
int broken_x = x+a[k][i];
int broken_y = y+b[k][i];
if(!is_valid(broken_x,broken_y)) continue;
if(A[broken_x][broken_y]=='.') continue;
if(A[broken_x][broken_y]=='@'){
shop--;
}
building--;
A[broken_x][broken_y]='.';
}
}
};
struct Bombplan{
char A[50][50];
set<tuple<int,int,int>> explodes;
int cost;
Bombplan(){}
Bombplan(char AA[50][50]){
for(int i=0;i<n;i++)for(int j=0;j<n;j++) A[i][j] = AA[i][j];
cost = 0;
}
void update_cost(){
cost = 0;
for(auto [k,x,y]:explodes){
cost += c[k];
}
}
//すべての位置の爆破方法をgreedyに決める
void greedy_all(){
int MAX_ITER = 20000;
char AA[50][50];
for(int i=0;i<n;i++)for(int j=0;j<n;j++) AA[i][j] = A[i][j];
int building = 0;
for(int i=0;i<n;i++)for(int j=0;j<n;j++){
if(AA[i][j]=='.') continue;
building++;
}
explodes.clear();
while(building>0){
int best_i,best_j,best_k;
double best = (double)INF;
if(building<3){
//建物のある位置を列挙
vector<pii> building_pos;
for(int i=0;i<n;i++)for(int j=0;j<n;j++){
if(AA[i][j]=='.') continue;
building_pos.emplace_back(make_pair(i,j));
}
for(int iter=0;iter<MAX_ITER;iter++){
int break_idx = randInt(0,building_pos.size()-1);
int break_x = building_pos[break_idx].first;
int break_y = building_pos[break_idx].second;
int k = randInt(0,m-1);
int t = randInt(0,l[k]-1);
int i = break_x - a[k][t];
int j = break_y - b[k][t];
if(!is_valid(i,j)) continue;
int broken_cnt = 0;
for(int x=0;x<l[k];x++){
int broken_x = i+a[k][x];
int broken_y = j+b[k][x];
if(is_valid(broken_x,broken_y) && AA[broken_x][broken_y]!='.'){
broken_cnt++;
}
}
if(broken_cnt==0) continue;
double tmp = (double)c[k]/(double)(broken_cnt);
if(chmin(best,tmp)){
best_i = i;
best_j = j;
best_k = k;
}
}
}
else{
for(int iter=0;iter<MAX_ITER;iter++){
int i = randInt(0,n-1);
int j = randInt(0,n-1);
int k = randInt(0,m-1);
int broken_cnt = 0;
for(int x=0;x<l[k];x++){
int broken_x = i+a[k][x];
int broken_y = j+b[k][x];
if(is_valid(broken_x,broken_y) && AA[broken_x][broken_y]!='.'){
broken_cnt++;
}
}
if(broken_cnt==0) continue;
double tmp = (double)c[k]/(double)(broken_cnt);
if(chmin(best,tmp)){
best_i = i;
best_j = j;
best_k = k;
}
}
}
explodes.insert(make_tuple(best_k,best_i,best_j));
for(int x=0;x<l[best_k];x++){
int broken_x = best_i+a[best_k][x];
int broken_y = best_j+b[best_k][x];
if(!is_valid(broken_x,broken_y)) continue;
if(AA[broken_x][broken_y]=='.') continue;
AA[broken_x][broken_y] = '.';
building--;
}
}
update_cost();
}
void output(){
cerr<<explodes.size()<<endl;
for(auto [k,x,y]:explodes){
cerr<<k<<" "<<x<<" "<<y<<endl;
}
}
void compress(){
set<tuple<int,int,int>> broken_hist[50][50];
for(auto [k,x,y]:explodes){
for(int i=0;i<l[k];i++){
int broken_x = x+a[k][i];
int broken_y = y+b[k][i];
if(!is_valid(broken_x,broken_y)) continue;
if(A[broken_x][broken_y]=='.') continue;
broken_hist[broken_x][broken_y].insert(make_tuple(k,x,y));
}
}
//bad_explodesの中から一つ選んで消せるようにする
set<tuple<int,int,int>> bad_explodes = explodes;
for(int i=0;i<n;i++)for(int j=0;j<n;j++){
if(A[i][j]=='.') continue;
if(broken_hist[i][j].size()==1){
bad_explodes.erase(*broken_hist[i][j].begin());
}
}
while(bad_explodes.size()>0){
int idx = randInt(0,bad_explodes.size()-1);
auto it = bad_explodes.begin();
for(int i=0;i<idx;i++) it++;
auto [k,x,y] = *it;
explodes.erase(make_tuple(k,x,y));
bad_explodes.erase(make_tuple(k,x,y));
cost -= c[k];
for(int t=0;t<l[k];t++){
int broken_x = x+a[k][t];
int broken_y = y+b[k][t];
if(!is_valid(broken_x,broken_y)) continue;
if(A[broken_x][broken_y]=='.') continue;
broken_hist[broken_x][broken_y].erase(make_tuple(k,x,y));
if(broken_hist[broken_x][broken_y].size()==1){
bad_explodes.erase(*broken_hist[broken_x][broken_y].begin());
}
}
}
}
pair<vector<tuple<int,int,int>>,vector<tuple<int,int,int>>> explode_list(){
vector<tuple<int,int,int>> res(all(explodes));
//真ん中の店を破壊する爆発を区別する
vector<tuple<int,int,int>> prior_plan;
vector<tuple<int,int,int>> remain_plan;
for(auto [k,x,y]:res){
bool plan_valid = true;
for(int i=0;i<l[k];i++){
int broken_x = x+a[k][i];
int broken_y = y+b[k][i];
if(broken_x==center_shop_x && broken_y==center_shop_y){
plan_valid = false;
break;
}
}
if(plan_valid){
prior_plan.emplace_back(make_tuple(k,x,y));
}
else{
remain_plan.emplace_back(make_tuple(k,x,y));
}
}
return make_pair(prior_plan,remain_plan);
}
double eval_func(double penalty){
Field field(A);
for(auto [k,x,y]:explodes){
field.use(k,x,y);
}
return (double)cost + (double)field.building * penalty;
}
void test(){
}
};
struct State{
char A[50][50];
int bomb[20];
int bomb_sum=0;
vector<pair<int,int>> hist;
int building = 0;
int shop = 0;
int cost=0;
int buy_cost=0;
int move_cost=0;
int nowx=0,nowy=0;
queue<pii> que;
State(){}
State(char AA[50][50]){
for(int i=0;i<n;i++)for(int j=0;j<n;j++) A[i][j] = AA[i][j];
vpii tmp;
for(int i=0;i<n;i++)for(int j=0;j<n;j++){
if(A[i][j]=='.') continue;
tmp.emplace_back(make_pair(i,j));
building++;
if(A[i][j]=='@'){
shop++;
}
}
sort(all(tmp),[](pii x, pii y){
int x_dist = abs(x.first-n/2)+abs(x.second-n/2);
int y_dist = abs(y.first-n/2)+abs(y.second-n/2);
if(x_dist==y_dist) return atan2(x.second-n/2,x.first-n/2) < atan2(y.second-n/2,y.first-n/2);
return x_dist>y_dist;
});
for(auto e:tmp){
que.push(e);
}
}
pair<int,vector<char>> smart_route(int sx,int sy,int gx,int gy){
char x_ope = gx>sx ? 'D' : 'U';
int dx = gx>sx ? 1 : -1;
char y_ope = gy>sy ? 'R' : 'L';
int dy = gy>sy ? 1 : -1;
vvi dp(abs(gx-sx)+1,vi(abs(gy-sy)+1,inf));
dp[0][0] = 0;
for(int i=0;i<=abs(gx-sx);i++)for(int j=0;j<=abs(gy-sy);j++){
if(i+1<=abs(gx-sx)){
chmin(dp[i+1][j],dp[i][j]+(A[sx+dx*(i+1)][sy+dy*j]!='.')+1);
}
if(j+1<=abs(gy-sy)){
chmin(dp[i][j+1],dp[i][j]+(A[sx+dx*i][sy+dy*(j+1)]!='.')+1);
}
}
//dpから最短経路を復元
vector<char> res(abs(gx-sx) + abs(gy-sy));
int i=abs(gx-sx),j=abs(gy-sy);
int index = res.size() - 1;
while(i>0 || j>0){
if(i>0 && dp[i-1][j]+(A[sx+dx*i][sy+dy*j]!='.')+1==dp[i][j]){
res[index] = x_ope;
i--;
}
else{
res[index] = y_ope;
j--;
}
index--;
}
int cost = dp[abs(gx-sx)][abs(gy-sy)];
return make_pair(cost,res);
}
//d:方向
void move(char d){
if(d=='U'){
hist.emplace_back(make_pair(1,0));
nowx--;
}
if(d=='D'){
hist.emplace_back(make_pair(1,1));
nowx++;
}
if(d=='L'){
hist.emplace_back(make_pair(1,2));
nowy--;
}
if(d=='R'){
hist.emplace_back(make_pair(1,3));
nowy++;
}
if(A[nowx][nowy]=='.'){
cost += (bomb_sum+1)*(bomb_sum+1);
move_cost += (bomb_sum+1)*(bomb_sum+1);
}
else{
cost += 2*(bomb_sum+1)*(bomb_sum+1);
move_cost += 2*(bomb_sum+1)*(bomb_sum+1);
}
}
//x,y:目的地の座標
void move(int x,int y){
pair<int, vector<char>> route_result = smart_route(nowx, nowy, x, y);
for (char direction : route_result.second) {
move(direction);
}
}
//piiに対応する座標に移動する
void move(pii p){
move(p.first,p.second);
}
//爆弾を買う
//i:爆弾の種類
void buy(int i){
assert(i>=0 && i<m);
hist.emplace_back(make_pair(2,i));
bomb[i]++;
bomb_sum++;
cost+=c[i];
buy_cost+=c[i];
}
//爆弾を使う
//i:爆弾の種類
void use(int i){
assert(i>=0 && i<m);
hist.emplace_back(make_pair(3,i));
for(int j=0;j<l[i];j++){
int broken_x = nowx+a[i][j];
int broken_y = nowy+b[i][j];
if(!is_valid(broken_x,broken_y)) continue;
if(A[broken_x][broken_y]=='.') continue;
if(A[broken_x][broken_y]=='@'){
shop--;
}
building--;
A[broken_x][broken_y]='.';
}
bomb[i]--;
bomb_sum--;
}
//爆弾を使ったときに壊れる建物の数,壊れる店の数,center_shopが壊れるかどうかを返す
tuple<int,int,bool> use_simulate(int i,int x,int y){
assert(i>=0 && i<m);
int broken_building = 0;
int broken_shop = 0;
bool broken_center_shop = false;
for(int j=0;j<l[i];j++){
int broken_x = x+a[i][j];
int broken_y = y+b[i][j];
if(!is_valid(broken_x,broken_y)) continue;
if(A[broken_x][broken_y]=='.') continue;
if(A[broken_x][broken_y]=='@'){
broken_shop++;
if(broken_x==center_shop_x && broken_y==center_shop_y){
broken_center_shop = true;
}
}
broken_building++;
}
return make_tuple(broken_building,broken_shop,broken_center_shop);
}
//最も近い店の座標を返す
pii nearest_shop(){
int min_dist=inf;
pii res;
for(int i=0;i<n;i++)for(int j=0;j<n;j++){
if(A[i][j]=='@'){
if(chmin(min_dist,abs(nowx-i)+abs(nowy-j))){
res = make_pair(i,j);
}
}
}
assert(min_dist!=inf);
return res;
}
pii nearest_shop(int x, int y){
int min_dist=inf;
pii res;
for(int i=0;i<n;i++)for(int j=0;j<n;j++){
if(A[i][j]=='@'){
if(chmin(min_dist,abs(x-i)+abs(y-j))){
res = make_pair(i,j);
}
}
}
assert(min_dist!=inf);
return res;
}
//最も近い店に移動する
void move_nearest_shop(){
pii p = nearest_shop();
move(p);
}
//一手進める
void one_step(){
double best_eval = (double)INF+1;
int best_i,best_j,best_k;
while(best_eval>=(double)INF){
for(int iter=0;iter<5000;iter++){
int i,j,k;
i = randInt(0,n-1);
j = randInt(0,n-1);
k = randInt(0,m-1);
int broken_building;
int broken_shop;
bool center_shop_broken;
tie(broken_building,broken_shop,center_shop_broken) = use_simulate(k,i,j);
if(broken_building==0) continue;
int use_cost = 0;
auto shop_pos = nearest_shop(i,j);
//shopまでの移動
use_cost += smart_route(nowx,nowy,shop_pos.first,shop_pos.second).first;
//shopでの購入
use_cost += c[k];
//shopから爆破場所までの移動
use_cost += 4*smart_route(shop_pos.first,shop_pos.second,i,j).first;
double eval = eval_func(use_cost,broken_building,broken_shop,center_shop_broken);
if(chmin(best_eval,eval)){
best_i = i;
best_j = j;
best_k = k;
}
}
}
auto shop_pos = nearest_shop(best_i,best_j);
move(shop_pos.first,shop_pos.second);
buy(best_k);
move(best_i,best_j);
use(best_k);
/* for(int i=0;i<n;i++)for(int j=0;j<n;j++){
for(int k=0;k<m;k++){
State state = *this;
state.buy(k);
state.move(i,j);
state.use(k);
int broken_building = building - state.building;
int usecost = state.cost - cost;
int eval;
if(broken_building==0) eval = inf;
else if(state.shop==0 && state.building!=0) eval = inf;
else{
eval = usecost/broken_building;
}
if(chmin(best_eval,eval)){
best_i = i;
best_j = j;
best_k = k;
}
}
}
*this = best_state; */
}
//爆破場所を決め打ちして1手進める
void one_step2(){
int i,j;
while(!que.empty()){
tie(i,j) = que.front();
que.pop();
if(A[i][j]!='.') break;
}
if(A[i][j]=='.') return;
double best_eval = (double)INF+1;
int best_k,best_t;
while(best_eval>=(double)INF){
int max_iter = 1000;
for(int iter=0;iter<max_iter;iter++){
//爆弾の種類とどの爆風で破壊するか決める
int k,t,explode_x,explode_y;
do{
k = randInt(0,m-1);
t = randInt(0,l[k]);
//爆破場所
explode_x = i-a[k][t];
explode_y = j-b[k][t];
}while(!is_valid(explode_x,explode_y));
//爆破したらどうなるか
int broken_building;
int broken_shop;
bool center_shop_broken;
tie(broken_building,broken_shop,center_shop_broken) = use_simulate(k,explode_x,explode_y);
if(broken_building==0) continue;
//コストシミュレーション
auto shop_pos = nearest_shop(explode_x,explode_y);
int use_cost = 0;
//shopまでの移動
use_cost += smart_route(nowx,nowy,shop_pos.first,shop_pos.second).first;
//shopでの購入
use_cost += c[k];
//shopから爆破場所までの移動
use_cost += 4*smart_route(shop_pos.first,shop_pos.second,explode_x,explode_y).first;
double eval = eval_func(use_cost,broken_building,broken_shop,center_shop_broken);
if(chmin(best_eval,eval)){
best_k = k;
best_t = t;
}
}
}
int best_explode_x = i-a[best_k][best_t];
int best_explode_y = j-b[best_k][best_t];
auto shop_pos = nearest_shop(best_explode_x,best_explode_y);
move(shop_pos.first,shop_pos.second);
buy(best_k);
move(best_explode_x,best_explode_y);
use(best_k);
}
//爆破場所と爆弾の種類を受け取ってその通り進める
void plan_exec(vector<tuple<int,int,int>> plan){
//planを実行
int i=0;
for(;i<(int)plan.size();i++){
auto [k,x,y] = plan[i];
auto [broken_building,broken_shop,center_shop_broken] = use_simulate(k,x,y);
if(broken_building<building && broken_shop == shop){
break;
}
auto shop_pos = nearest_shop(x,y);
move(shop_pos);
buy(k);
move(x,y);
use(k);
}
if(i<(int)plan.size()){
//残りのplanを実行
auto[k,x,y] = plan[i];
auto shop_pos = nearest_shop(x,y);
move(shop_pos);
for(int j=i;j<(int)plan.size();j++){
auto [k,x,y] = plan[j];
buy(k);
}
for(int j=i;j<(int)plan.size();j++){
auto [k,x,y] = plan[j];
move(x,y);
use(k);
}
}
}
void plan_exec(vector<tuple<int,int,int>> prior_plan, vector<tuple<int,int,int>> remain_plan){
//prior_planを実行
for(auto [k,x,y]:prior_plan){
auto shop_pos = nearest_shop(x,y);
move(shop_pos.first,shop_pos.second);
buy(k);
move(x,y);
use(k);
}
//remain_planを実行
move_nearest_shop();
for(auto [k,x,y]:remain_plan){
buy(k);
}
for(auto [k,x,y]:remain_plan){
move(x,y);
use(k);
}
}
//シミュレーション結果で評価
double eval_func(double usecost,double broken_building,double broken_shop,bool center_shop_broken){
if(broken_building==0) return (double)INF;
else if(shop==broken_shop && building>broken_building) return (double)INF;
else{
double eval = (double)usecost/(double)broken_building;
if(center_shop_broken) eval *= 10;
return eval;
}
}
//差分評価
double diff_eval(State now, State nex){
int broken_building = now.building - nex.building;
int usecost = nex.cost - now.cost;
if(broken_building==0) return (double)INF;
else if(nex.shop==0 && nex.building!=0) return (double)INF;
else{
double eval = (double)usecost/(double)broken_building;
if(nex.A[center_shop_x][center_shop_y]!='@') eval *= 10;
return eval;
}
}
//出力
void output(){
cout<<hist.size()<<endl;
for(auto p:hist){
if(p.first==1){
cout<<1<<" ";
if(p.second==0) cout<<"U";
if(p.second==1) cout<<"D";
if(p.second==2) cout<<"L";
if(p.second==3) cout<<"R";
cout<<'\n';
}
else cout<<p.first<<" "<<p.second+1<<"\n";
}
}
};
struct Solve{
char A[50][50];
Bombplan best_plan;
void IN(){
cin.tie(nullptr);
ios::sync_with_stdio(false);
cin>>n>>m;
int center_shop_dist = inf;
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
cin>>A[i][j];
//center_shop_x,center_shop_yを決める
if(A[i][j]=='@'){
if(chmin(center_shop_dist,abs(i-n/2)+abs(j-n/2))){
center_shop_x = i;
center_shop_y = j;
}
}
}
}
for(int i=0;i<m;i++){
cin>>c[i]>>l[i];
for(int j=0;j<l[i];j++){
int tmpa,tmpb;
cin>>tmpa>>tmpb;
a[i].emplace_back(tmpa);
b[i].emplace_back(tmpb);
}
}
}
void solve(){
/* Bombplan bombplan(A);
bombplan.greedy_all();
cerr<<"cost:"<<bombplan.cost<<endl; */
sa();
}
void sa(){
Bombplan bombplan(A);
bombplan.greedy_all();
auto [prior_plan,remain_plan] = bombplan.explode_list();
vector<tuple<int,int,int>> plan = prior_plan;
plan.insert(plan.end(),all(remain_plan));
int pn = prior_plan.size();
int rn = remain_plan.size();
int nn = plan.size();
State best_state;
State init_state(A);
State state = init_state;
state.plan_exec(plan);
int pre_score = state.cost;
double start_temp = 20;
double end_temp = 0.1;
int iter = 0;
int MAX_TIME = 2900;
while(get_time()-start_time<MAX_TIME){
iter++;
int i = randInt(0,nn-1);
int j = randInt(0,nn-2);
if(i<=j) j++;
swap(plan[i],plan[j]);
state = init_state;
state.plan_exec(plan);
int next_score = state.cost;
double temp = start_temp + (end_temp-start_temp)*(get_time()-start_time)/MAX_TIME;
double prob = exp((pre_score-next_score)/temp);
if(prob>randDouble(0,1)){
pre_score = next_score;
best_state = state;
#ifdef LOCAL
cerr<<"iter:"<<iter<<endl;
cerr<<"best_score:"<<pre_score<<endl;
cerr<<"time:"<<get_time()-start_time<<"ms\n";
#endif
}
else{
swap(plan[i],plan[j]);
}
}
#ifdef LOCAL
cerr<<"total_cost:"<<pre_score<<endl;
cerr<<"buy_cost:"<<best_state.buy_cost<<endl;
cerr<<"move_cost:"<<best_state.move_cost<<endl;
#endif
best_state.output();
}
};
int main(){
start_time = get_time();
Solve solve;
solve.IN();
solve.solve();
#ifdef LOCAL
cerr<<"time:"<<get_time()-start_time<<"ms\n";
#endif
}