結果
| 問題 | No.5019 Hakai Project |
| ユーザー |
 bin101
|
| 提出日時 | 2023-11-18 14:55:48 |
| 言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
AC
|
| 実行時間 | 2,602 ms / 3,000 ms |
| コード長 | 35,349 bytes |
| コンパイル時間 | 7,090 ms |
| コンパイル使用メモリ | 322,368 KB |
| 実行使用メモリ | 130,548 KB |
| スコア | 2,750,230,260 |
| 最終ジャッジ日時 | 2023-11-18 14:58:04 |
| 合計ジャッジ時間 | 134,060 ms |
|
ジャッジサーバーID （参考情報） |
judge14 / judge11 |
| 純コード判定しない問題か言語 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 2,025 ms
118,532 KB |
| testcase_01 | AC | 2,565 ms
116,380 KB |
| testcase_02 | AC | 2,561 ms
121,788 KB |
| testcase_03 | AC | 2,556 ms
108,536 KB |
| testcase_04 | AC | 2,178 ms
120,504 KB |
| testcase_05 | AC | 2,284 ms
114,068 KB |
| testcase_06 | AC | 2,511 ms
108,080 KB |
| testcase_07 | AC | 2,566 ms
121,748 KB |
| testcase_08 | AC | 2,455 ms
115,256 KB |
| testcase_09 | AC | 2,575 ms
115,888 KB |
| testcase_10 | AC | 1,730 ms
96,924 KB |
| testcase_11 | AC | 2,555 ms
112,964 KB |
| testcase_12 | AC | 2,551 ms
110,248 KB |
| testcase_13 | AC | 2,560 ms
118,516 KB |
| testcase_14 | AC | 1,990 ms
113,796 KB |
| testcase_15 | AC | 2,373 ms
106,804 KB |
| testcase_16 | AC | 2,152 ms
116,600 KB |
| testcase_17 | AC | 1,386 ms
106,688 KB |
| testcase_18 | AC | 2,578 ms
116,100 KB |
| testcase_19 | AC | 2,567 ms
112,100 KB |
| testcase_20 | AC | 2,579 ms
111,164 KB |
| testcase_21 | AC | 2,600 ms
112,184 KB |
| testcase_22 | AC | 1,965 ms
104,916 KB |
| testcase_23 | AC | 2,575 ms
109,920 KB |
| testcase_24 | AC | 2,602 ms
121,528 KB |
| testcase_25 | AC | 2,566 ms
109,300 KB |
| testcase_26 | AC | 2,573 ms
116,196 KB |
| testcase_27 | AC | 1,933 ms
119,952 KB |
| testcase_28 | AC | 2,430 ms
114,524 KB |
| testcase_29 | AC | 1,609 ms
104,972 KB |
| testcase_30 | AC | 2,571 ms
110,672 KB |
| testcase_31 | AC | 2,581 ms
106,492 KB |
| testcase_32 | AC | 2,565 ms
108,052 KB |
| testcase_33 | AC | 2,176 ms
116,444 KB |
| testcase_34 | AC | 2,561 ms
119,304 KB |
| testcase_35 | AC | 2,547 ms
107,984 KB |
| testcase_36 | AC | 2,169 ms
114,212 KB |
| testcase_37 | AC | 2,577 ms
107,456 KB |
| testcase_38 | AC | 2,584 ms
108,328 KB |
| testcase_39 | AC | 2,341 ms
130,548 KB |
| testcase_40 | AC | 2,568 ms
115,944 KB |
| testcase_41 | AC | 2,559 ms
121,024 KB |
| testcase_42 | AC | 2,350 ms
114,372 KB |
| testcase_43 | AC | 1,693 ms
117,576 KB |
| testcase_44 | AC | 2,571 ms
107,600 KB |
| testcase_45 | AC | 1,861 ms
101,240 KB |
| testcase_46 | AC | 2,585 ms
112,020 KB |
| testcase_47 | AC | 2,555 ms
118,568 KB |
| testcase_48 | AC | 2,555 ms
110,208 KB |
| testcase_49 | AC | 2,574 ms
118,024 KB |
コンパイルメッセージ
In member function 'bool Place::operator==(const Place&)',
inlined from 'void solve()' at main.cpp:1160:26:
main.cpp:612:23: warning: 'center_shop.Place::h' may be used uninitialized [-Wmaybe-uninitialized]
612 | return h==p.h and w==p.w;
| ~~~~~~~^~~~~~~~~~
main.cpp: In function 'void solve()':
main.cpp:1122:11: note: 'center_shop.Place::h' was declared here
1122 | Place center_shop;
| ^~~~~~~~~~~
In member function 'bool Place::operator==(const Place&)',
inlined from 'void solve()' at main.cpp:1160:26:
main.cpp:612:23: warning: 'center_shop.Place::w' may be used uninitialized [-Wmaybe-uninitialized]
612 | return h==p.h and w==p.w;
| ~~~~~~~^~~~~~~~~~
main.cpp: In function 'void solve()':
main.cpp:1122:11: note: 'center_shop.Place::w' was declared here
1122 | Place center_shop;
| ^~~~~~~~~~~
ソースコード
/*
TODO:
*/
//#define NDEBUG
//#define ONLINE_JUDGE
#ifndef ONLINE_JUDGE
//#define OPTUNA
#endif
#ifdef ONLINE_JUDGE
#define NDEBUG
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#endif
#include<bits/stdc++.h>
using namespace std;
using ll=long long int;
//using Int=__int128;
#define mask(x) ((1LL<<x)-1)
#define ALL(A) A.begin(),A.end()
template<typename T1,typename T2> bool chmin(T1 &a,T2 b){if(a<=b)return 0; a=b; return 1;}
template<typename T1,typename T2> bool chmax(T1 &a,T2 b){if(a>=b)return 0; a=b; return 1;}
template<typename T> int bitUP(T x,int a){return (x>>a)&1;}
enum Dir{
Right,
Down,
Left,
Up
};
//→ ↓ ← ↑
int dh[4]={0,1,0,-1}, dw[4]={1,0,-1,0};
//上から時計回り
//int dx[8]={0,1,1,1,0,-1,-1,-1}, dy[8]={1,1,0,-1,-1,-1,0,1};
long double EPS = 1e-6;
const ll INF=(1LL<<62);
const int MAX=(1<<30);
using pii=pair<int,int>;
using pil=pair<int,ll>;
using pli=pair<ll,int>;
using pll=pair<ll,ll>;
using psi=pair<string,int>;
using pis=pair<int,string>;
using psl=pair<string,ll>;
using pls=pair<ll,string>;
using pss=pair<string,string>;
template<class T>
using minimum_queue=priority_queue<T,vector<T>,greater<T>>;
using Graph=vector<vector<int>>;
using i8=int8_t;
using i16=int16_t;
using i32=int32_t;
using i64=int64_t;
using u8=uint8_t;
using u16=uint16_t;
using u32=uint32_t;
using u64=uint64_t;
void FastIO(){
ios::sync_with_stdio(false);
cin.tie(0);
cout << fixed << setprecision(20);
}
//0-indexed vector cin
template<typename T>
inline istream &operator>>(istream &is,vector<T> &v) {
for(size_t i=0;i<v.size();i++) is>>v[i];
return is;
}
//0-indexed vector cin
template<typename T>
inline istream &operator>>(istream &is,vector<vector<T>> &v) {
for(size_t i=0;i<v.size();i++){
is>>v[i];
}
return is;
}
struct Xor32{
using u32=uint32_t;
u32 x=1234567;
inline u32 rnd_make(){
x^=(x<<13);
x^=(x>>17);
x^=(x<<5);
return x;
}
inline u32 operator()(){
return rnd_make();
}
//[a,b)
inline int operator()(int a,int b){
int dis=b-a;
int add=rnd_make()%dis;
return a+add;
}
//[0,b)
inline int operator()(int b){
return rnd_make()%b;
}
//http://web.archive.org/web/20200105011004/https://topcoder.g.hatena.ne.jp/tomerun/20171216/
//[0,b)の中から異なる2つを選ぶ [0]の値<[1]の値
inline array<int,2> two(int b){
assert(b>=2);
int v1=rnd_make()%b;
int v2=rnd_make()%(b-1);
if (v2>=v1) return {v1,v2+1};
else return {v2,v1};
}
inline float random01(){
return float(rnd_make())/mask(32);
}
inline double random_double(double a,double b){
double sa=b-a;
a+=random01()*sa;
return a;
}
//確率pでtrueを返す
inline bool gen_bool(float p){
return p>random01();
}
};
struct Xor64{
u64 x=1234567;
inline u64 rnd_make(){
x ^= x << 13;
x ^= x >> 7;
x ^= x << 17;
return x;
}
inline u64 operator()(){
return rnd_make();
}
};
struct Timer{
chrono::high_resolution_clock::time_point st;
float local;
Timer(){
#ifndef ONLINE_JUDGE
local=1.0;
#endif
start();
}
void start(){
st=chrono::high_resolution_clock::now();
}
int span()const{
auto now=chrono::high_resolution_clock::now();
return chrono::duration_cast<chrono::milliseconds>(now-st).count();
}
};
struct TestTimer{
chrono::high_resolution_clock::time_point st;
unordered_map<string,ll> sum_time;
unordered_map<string,chrono::high_resolution_clock::time_point> start_time;
TestTimer(){}
void start(const string &s){
#ifndef ONLINE_JUDGE
start_time[s]=chrono::high_resolution_clock::now();
#endif
}
void end(const string &s){
#ifndef ONLINE_JUDGE
auto now=chrono::high_resolution_clock::now();
sum_time[s]+=chrono::duration_cast<chrono::nanoseconds>(now-start_time[s]).count();
#endif
}
void output()const{
#ifndef ONLINE_JUDGE
for(auto m:sum_time){
cerr<<m.first<<": "<<m.second/1e6<<"ms"<<endl;
}
#endif
}
};
struct TestCounter{
unordered_map<string,ll> cnt;
TestCounter(){}
void count(const string &s){
#ifndef ONLINE_JUDGE
cnt[s]++;
#endif
}
void output()const{
#ifndef ONLINE_JUDGE
for(auto m:cnt){
cerr<<m.first<<": "<<m.second<<endl;
}
#endif
}
};
Timer TIME;
Xor32 Rand32;
Xor64 Rand64;
TestTimer testTimer;
TestCounter testCounter;
//https://atcoder.jp/contests/asprocon9/submissions/34659956
template<class T,int CAPACITY>
class DynamicArray{
public:
array<T,CAPACITY> array_={};
int size_=0;
DynamicArray(){}
DynamicArray(int n){
resize(n);
}
void push_back(const T &e){
array_[size_++]=e;
}
void pop_back(){
size_--;
}
inline T& operator[](int index){
return array_[index];
}
inline const T& operator[](int index) const {
return array_[index];
}
inline int size()const{
return size_;
}
inline T& back(){
return array_[size_-1];
}
inline auto begin() -> decltype(array_.begin()) {
return array_.begin();
}
inline auto end() -> decltype(array_.begin()) {
return array_.begin() + size_;
}
inline auto begin() const -> decltype(array_.begin()) {
return array_.begin();
}
inline auto end() const -> decltype(array_.begin()) {
return array_.begin() + size_;
}
inline void resize(int new_size){
size_=new_size;
}
void operator=(const DynamicArray &e){
for(int i=0;i<e.size_;i++){
array_[i]=e[i];
}
size_=e.size_;
}
void clear(){
size_=0;
}
//O(1)
//末尾と入れ替える。順序が保持されないが高速
void swap_remove(int idx){
array_[idx]=array_[size_-1];
size_--;
}
//O(size)
//順序を気にしない場合、swap_removeの方がいい
void remove(int idx){
for(int i=idx;i<size_-1;i++){
array_[i]=array_[i+1];
}
size_--;
}
void fill(T x){
for(int i=0;i<size_;i++){
array_[i]=x;
}
}
};
//ソート
template<typename T>
inline void vsort(vector<T> &v){
sort(v.begin(),v.end());
}
//逆順ソート
template<typename T>
inline void rvsort(vector<T> &v){
sort(v.rbegin(),v.rend());
}
//1ビットの数を返す
inline int popcount(int x){
return __builtin_popcount(x);
}
//1ビットの数を返す
inline int popcount(ll x){
return __builtin_popcountll(x);
}
template<typename T>
inline void Compress(vector<T> &C){
sort(C.begin(),C.end());
C.erase(unique(C.begin(),C.end()),C.end());
}
//要素数n 初期値x
template<typename T>
inline vector<T> vmake(size_t n,T x){
return vector<T>(n,x);
}
//a,b,c,x data[a][b][c] 初期値x
template<typename... Args>
auto vmake(size_t n,Args... args){
auto v=vmake(args...);
return vector<decltype(v)>(n,move(v));
}
//vは昇順
bool is_in(const vector<int> &v,int x){
int n=v.size();
if(n==0) return false;
int ng=-1,ok=n-1;
while(ok-ng!=1){
int mid=(ok+ng)/2;
if(v[mid]<x) ng=mid;
else ok=mid;
}
if(v[ok]==x) return true;
return false;
}
template<typename T >
struct edge {
int to;
T cost;
int id;
edge()=default;
edge(int to, T cost,int id) : to(to), cost(cost), id(id) {}
};
template<class T >
struct Edge {
int from, to,id;
T cost;
Edge(int from,int to,T cost,int id):from(from),to(to),cost(cost),id(id){}
Edge()=default;
bool operator<(const Edge<T> &e){
return cost<e.cost;
}
bool operator<=(const Edge<T> &e){
return cost<=e.cost;
}
};
template<typename T>
using WeightGraph=vector<vector<edge<T>>>;
//vector cout
template<typename T>
inline ostream &operator<<(ostream &os,const vector<T> &v) {
bool sp=true;
if(string(typeid(T).name())=="c") sp=false;
for(size_t i=0;i<v.size();i++){
if(i and sp) os<<" ";
os<<v[i];
}
return os;
}
//vector<vector> cout
template<typename T>
inline ostream &operator<<(ostream &os,const vector<vector<T>> &v) {
for(size_t i=0;i<v.size();i++){
os<<v[i];
if(i+1!=v.size()) os<<"\n";
}
return os;
}
//pair cout
template<typename T, typename U>
inline ostream &operator<<(ostream &os,const pair<T,U> &p) {
os<<p.first<<" "<<p.second;
return os;
}
//map cout
template<typename F, typename S>
inline ostream &operator<<(ostream &os,const map<F,S> &M) {
bool first=false;
for(auto x:M){
if(first) os<<endl;
first=true;
os<<x;
}
return os;
}
//set cout
template<typename T>
inline ostream &operator<<(ostream &os,const set<T> &S) {
bool first=false;
for(auto x:S){
if(first) os<<endl;
first=true;
os<<x;
}
return os;
}
//pair cin
template<typename T, typename U>
inline istream &operator>>(istream &is,pair<T,U> &p) {
is>>p.first>>p.second;
return is;
}
template<typename T>
void append(vector<T> &v,const vector<T> &vp){
for(auto p:vp){
v.push_back(p);
}
}
//Fisher–Yatesアルゴリズム
template<typename T>
void shuffle(vector<T> &v){
int sz=v.size();
for(int i=sz-1;i>0;i--){
swap(v[Rand32()%(i+1)],v[i]);
}
}
//[0,n)の集合を管理
//値の追加・削除・存在確認: O(1)
//空間計算量: O(n)
//重複は許さない
//https://topcoder-tomerun.hatenablog.jp/entry/2021/06/12/134643
template<int CAPACITY>
struct IntSet{
DynamicArray<int,CAPACITY> set_;
array<int,CAPACITY> pos_;
IntSet(){
for(int i=0;i<CAPACITY;i++){
pos_[i]=-1;
}
set_.clear();
}
void insert(int v){
//assert(pos_[v]==-1);
if(pos_[v]!=-1) return;
pos_[v]=set_.size();
set_.push_back(v);
}
void remove(int v){
assert(pos_[v]!=-1);
int last=set_[set_.size()-1];
set_[pos_[v]]=last;
pos_[last]=pos_[v];
set_.pop_back();
pos_[v]=-1;
}
bool contains(int v)const{
return pos_[v]!=-1;
}
int size()const{
return set_.size();
}
int random()const{
assert(set_.size());
int x=set_[Rand32(set_.size())];
assert(pos_[x]!=-1);
return x;
}
int random_extract(){
int v=set_[Rand32(set_.size())];
remove(v);
return v;
}
void clear(){
while(size()){
remove(set_.back());
}
}
};
///++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
///++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
///++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
template<class T,class U>
T linear_function(U x,U start_x,U end_x,T start_value,T end_value){
if(x>=end_x) return end_value;
if(x<=start_x) return start_value;
return start_value+(end_value-start_value)*(x-start_x)/(end_x-start_x);
}
//http://gasin.hatenadiary.jp/entry/2019/09/03/162613
struct SimulatedAnnealing{
float startTemp; //差の最大値(あくまでも参考)
float endTemp; //差の最小値(あくまでも参考)
float startTime;
float endTime;
bool yama;
bool minimum;
//SimulatedAnnealing(){}
SimulatedAnnealing(float startTemp,float endTemp,float startTime,float endTime,bool yama,bool minimum):
startTemp(startTemp),endTemp(endTemp),startTime(startTime),endTime(endTime),yama(yama),minimum(minimum){
}
float calc_temp(){
return linear_function(float(TIME.span()),startTime,endTime,startTemp,endTemp); //線形
//https://atcoder.jp/contests/ahc014/submissions/35326979
/*float progress=(TIME.span()-startTime)/(endTime-startTime);
if(progress>1.0) progress=1.0;
return pow(startTemp,1.0-progress)*pow(endTemp,progress);*/
}
float calc_prob(float diff){
if(minimum) diff*=-1;
if(diff>0) return 1;
float temp=calc_temp();
return exp(diff/temp);
}
float calc_diff(float prob){
float diff=log(prob)*calc_temp();
if(minimum) diff*=-1;
return diff;
}
inline bool operator()(float diff){
testCounter.count("try_cnt");
if(minimum) diff*=-1;
if(diff>0){
testCounter.count("plus_change");
return true;
}
if(yama) return false;
float prob;
if(minimum) prob=calc_prob(diff*-1);
else prob=calc_prob(diff);
if(prob>float(Rand32()&mask(30))/mask(30)){
testCounter.count("minus_change");
return true;
}
else return false;
}
};
///++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
///++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
///++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
//https://atcoder.jp/contests/asprocon9/submissions/34659956
#ifndef OPTUNA
#define REGIST_PARAM(name, type, defaultValue) constexpr type name = defaultValue
#else
#define REGIST_PARAM(name, type, defaultValue) type name = defaultValue
#endif
namespace OP{
REGIST_PARAM(yama,bool,false);
REGIST_PARAM(startTemp,double,500000);
REGIST_PARAM(endTemp,float,0);
REGIST_PARAM(TIME_END,int,1900);
};
constexpr int Height=50;
constexpr int Width=50;
vector<string> ans;
struct Place{
int h,w;
Place(){}
Place(int h,int w):h(h),w(w){
}
Place(int idx):h(idx/Width),w(idx%Width){
}
int dist(const Place &np)const{
return abs(np.h-h)+abs(np.w-w);
}
Place pre_place(int dir){
return Place(h-dh[dir],w-dw[dir]);
}
Place next_place(int dir){
return Place(h+dh[dir],w+dw[dir]);
}
void move(int dir){
h+=dh[dir];
w+=dw[dir];
}
void remove(int dir){
h-=dh[dir];
w-=dw[dir];
}
bool ok_move(int dir){
return h+dh[dir]<Height and w+dw[dir]<Width and h+dh[dir]>=0 and w+dw[dir]>=0;
}
bool out_grid(){
return h>=Height or w>=Width or h<0 or w<0;
}
bool operator==(const Place &p){
return h==p.h and w==p.w;
}
bool operator!=(const Place &p){
return h!=p.h or w!=p.w;
}
int idx(){
return h*Width+w;
}
int id(){
return idx();
}
//上下 左右
bool operator<(Place &p){
if(p.h!=h) return h<p.h;
return w<p.w;
}
friend istream& operator>>(istream& is, Place& p){
is>>p.h>>p.w;
return is;
}
friend ostream& operator<<(ostream& os, Place& p){
os<<p.h<<" "<<p.w;
return os;
}
void move(Place p){
h+=p.h;
w+=p.w;
}
};
template<class Cost>
struct GridDistance{
using pti=pair<Cost,int>;
int Height;
int Width;
vector<vector<Cost>> cost_grid;
GridDistance(int Height,int Width):Height(Height),Width(Width){
cost_grid=vmake(Height,Width,Cost());
}
void set_cost(int h,int w,Cost cost){
cost_grid[h][w]=cost;
}
vector<Cost> dijkstra(Place start){
vector<Cost> dist(Height*Width,numeric_limits<Cost>::max());
priority_queue<pti,vector<pti>,greater<pti>> que;
dist[start.id()]=0;
que.emplace(dist[start.id()],start.id());
while(que.size()){
Place now_place;
Cost now_cost;
tie(now_cost,now_place)=que.top(); que.pop();
if(now_cost>dist[now_place.id()]) continue;
for(int dir=0;dir<4;dir++){
auto next_place=now_place.next_place(dir);
if(next_place.out_grid()) continue;
Cost next_cost=dist[now_place.id()]+cost_grid[next_place.h][next_place.w];
if(chmin(dist[next_place.id()],next_cost)){
que.emplace(next_cost,next_place.id());
}
}
}
return dist;
}
pair<Cost,vector<char>> query_path(Place start,Place goal){
auto dist=dijkstra(start);
vector<Place> path;
auto now_place=goal;
path.push_back(now_place);
while(now_place!=start){
for(int dir=0;dir<4;dir++){
auto np=now_place.next_place(dir);
if(np.out_grid()) continue;
if(dist[np.id()]+cost_grid[now_place.h][now_place.w]==dist[now_place.id()]){
now_place=np;
break;
}
}
path.push_back(now_place);
}
reverse(path.begin(),path.end());
vector<char> path_dir;
for(int i=0;i+1<path.size();i++){
auto p=path[i];
for(int dir=0;dir<4;dir++){
auto np=p.next_place(dir);
if(np==path[i+1]){
path_dir.push_back(dir);
break;
}
}
}
return {dist[goal.id()],path_dir};
}
};
GridDistance<int> Distance(Height,Width);
Place find_nearest(const Place &p,const vector<Place> &ps,bool easy=true){
int distance=MAX;
Place nearest;
for(auto np:ps){
int dist;
if(easy) dist=p.dist(np);
else dist=Distance.query_path(p,np).first;
if(chmin(distance,dist)){
nearest=np;
}
}
return nearest;
}
template<class T>
pair<Place,T> find_nearest(Place &p,vector<pair<Place,T>> &ps,bool easy=true){
int distance=MAX;
pair<Place,T> nearest;
for(auto np:ps){
int dist;
if(easy) dist=p.dist(np.first);
else dist=Distance.query_path(p,np.first).first;
if(chmin(distance,dist)){
nearest=np;
}
}
return nearest;
}
void output_move(Place &start,Place goal){
auto path_dir=Distance.query_path(start,goal).second;
start=goal;
for(int dir:path_dir){
string s="1 ";
string c="U";
if(dir==0) c="R";
if(dir==1) c="D";
if(dir==2) c="L";
s+=c;
ans.push_back(s);
}
}
struct Bomb{
int cost;
vector<Place> ps;
};
constexpr int num_bomb=20;
auto map_input=vmake(Height,Width,'.');
vector<Bomb> bombs(num_bomb);
void input(){
int dummy;
cin>>dummy>>dummy;
for(int h=0;h<Height;h++) for(int w=0;w<Width;w++){
cin>>map_input[h][w];
}
for(int b=0;b<num_bomb;b++){
cin>>bombs[b].cost;
int size;
cin>>size;
bombs[b].ps.resize(size);
cin>>bombs[b].ps;
}
}
//https://www.sciencedirect.com/science/article/pii/0305054881900174
//AlgorithmA 一番コスパが高いものを選ぶ貪欲
//TODO:https://scmopt.github.io/opt100/74scp.html を参考にしてもっと書く(weightedがついてないけど重み付きっぽい)
template<class Name,class Cost,int max_num_element>
struct SetCovering{
struct Set{
Name name;
Cost cost;
vector<int> elements;
bitset<max_num_element> bits;
Set(Name name,Cost cost,vector<int> elements):
name(name),cost(cost),elements(elements){
bits.reset();
for(int element:elements){
bits.flip(element);
}
}
};
int num_element;
vector<Set> sets;
vector<vector<int>> sets_contain;
vector<int> best_solution;
Cost best_cost;
vector<int> cnt_covered;
SetCovering(int num_element):num_element(num_element),sets_contain(num_element){
}
void add_set(Name name,Cost cost,vector<int> elements){
Set set({name,cost,elements});
sets.push_back(set);
for(int element:set.elements){
sets_contain[element].push_back(sets.size()-1);
}
}
vector<vector<int>> make_sets_contain(){
vector<vector<int>> sets_contain(num_element);
int id=0;
for(auto &set:sets){
for(int element:set.elements){
sets_contain[element].push_back(id);
}
id++;
}
return sets_contain;
}
//k(出力する解のサイズ) N(setの数)
//O(Nk+要素数の合計)
//[1,rate]倍する
pair<vector<int>,Cost> greedy(double rate=1){
int num_set=sets.size();
vector<bool> is_covered(num_element,false);
vector<int> num_uncovered(num_set);
for(int s=0;s<num_set;s++){
num_uncovered[s]=sets[s].elements.size();
}
vector<int> ans;
Cost cost_sum=0;
while(true){
//一番コスパ(num_uncovered/cost)が高いものを選ぶ
int id_best=-1;
double costper_best=-1;
for(int i=0;i<num_set;i++){
if(num_uncovered[i]==0) continue;
if(chmax(costper_best,double(num_uncovered[i])/sets[i].cost*Rand32.random_double(1,rate))){
id_best=i;
}
}
if(id_best==-1){
//すべてのelementをカバーした
break;
}
ans.push_back(id_best);
cost_sum+=sets[id_best].cost;
//num_uncoveredとis_coveredを更新
for(int element:sets[id_best].elements){
if(is_covered[element]) continue;
is_covered[element]=true;
//cerr<<sets_contain.size()<<endl;
for(int id_set:sets_contain[element]){
num_uncovered[id_set]--;
}
}
}
for(int i=0;i<num_element;i++){
if(is_covered[i]) continue;
cerr<<"uncovered: "<<i<<endl;
assert(false);
}
cerr<<"cost_sum: "<<cost_sum<<endl;
return {ans,cost_sum};
}
//loop回貪欲を行って一番良かったものを出力
void greedy_random(int loop,double rate){
tie(best_solution,best_cost)=greedy(1);
for(int i=0;i<loop-1;i++){
Cost cost;
vector<int> solution;
tie(solution,cost)=greedy(rate);
if(chmin(best_cost,cost)){
best_solution=solution;
}
}
}
//O(解のサイズの次数の合計)
bool flip1(){
for(int i=0;i<best_solution.size();i++){
bool ok=true;
int id=best_solution[i];
for(int element:sets[id].elements){
if(cnt_covered[element]==1){
ok=false;
break;
}
}
if(ok){
best_solution.erase(best_solution.begin()+i);
i--;
for(int element:sets[id].elements){
cnt_covered[element]--;
}
best_cost-=sets[id].cost;
return true;
}
}
return false;
}
bool flip2(){
for(int i=0;i<best_solution.size();i++){
int id=best_solution[i];
vector<int> need_elements;
int min_num_candidate=sets.size();
int min_element=-1;
for(int element:sets[id].elements){
if(cnt_covered[element]==1){
need_elements.push_back(element);
if(chmin(min_num_candidate,sets_contain[element].size())){
min_element=element;
}
}
}
for(int id2:sets_contain[min_element]){
if(sets[id].cost<=sets[id2].cost){
continue;
}
bool ok=true;
for(int need_element:need_elements){
if(sets[id2].bits.test(need_element)==false){
ok=false;
break;
}
}
if(ok){
best_solution[i]=id2;
best_cost+=sets[id2].cost-sets[id].cost;
return true;
}
}
}
return false;
}
bool flip3(){
for(int i=0;i<best_solution.size();i++){
for(int j=i+1;j<best_solution.size();j++){
array<int,2> id={best_solution[i],best_solution[j]};
vector<int> need_elements;
int min_num_candidate=sets.size();
int min_element=-1;
for(int s=0;s<2;s++){
for(int element:sets[id[s]].elements){
if(cnt_covered[element]==1 or (cnt_covered[element]==2 and sets[id[1-s]].bits.test(element))){
need_elements.push_back(element);
if(chmin(min_num_candidate,sets_contain[element].size())){
min_element=element;
}
}
}
}
Cost erase_cost=sets[id[0]].cost+sets[id[1]].cost;
for(int id2:sets_contain[min_element]){
if(erase_cost<=sets[id2].cost){
continue;
}
bool ok=true;
for(int need_element:need_elements){
if(sets[id2].bits.test(need_element)==false){
ok=false;
break;
}
}
if(ok){
best_solution[i]=id2;
best_solution.erase(best_solution.begin()+j);
best_cost+=sets[id2].cost-erase_cost;
return true;
}
}
}
}
return false;
}
void set_cnt_covered(){
cnt_covered.assign(num_element,0);
for(int id:best_solution){
for(int element:sets[id].elements){
cnt_covered[element]++;
}
}
}
void solve(){
greedy_random(10,1.01);
while(true){
set_cnt_covered();
bool ok=false;
ok|=flip1();
if(ok) continue;
ok|=flip2();
if(ok) continue;
ok|=flip3();
if(ok) continue;
if(not ok) break;
}
}
};
template<class Action,class Score>
struct State{
static vector<Place> place_shop;
static vector<Place> place_action;
static vector<vector<int>> bakuha_shop;
vector<pii> history_actions;
vector<bool> is_bakuha_shop;
vector<bool> is_done_action;
int score;
Place now_place;
State(int action_size,int shop_size):is_bakuha_shop(shop_size),is_done_action(action_size),score(0),now_place(0,0){
}
Score calc_score(){
return score;
}
void apply(Action action){
int min_dist=MAX;
int nearest_shop=-1;
for(int i=0;i<is_bakuha_shop.size();i++){
if(is_bakuha_shop[i]) continue;
int dist=now_place.dist(place_shop[i])+place_shop[i].dist(place_action[action])*2;
if(chmin(min_dist,dist)){
nearest_shop=i;
}
}
score+=min_dist;
history_actions.emplace_back(action,nearest_shop);
is_done_action[action]=true;
//shopを爆破
for(int shop:bakuha_shop[action]){
is_bakuha_shop[shop]=true;
}
//移動
now_place=place_action[action];
}
vector<Action> find_next_actions(){
vector<int> candidate;
int size_action=is_done_action.size();
for(int i=0;i<size_action;i++){
if(is_done_action[i]) continue;
candidate.push_back(i);
}
sort(candidate.begin(),candidate.end(),
[&](int i,int j){
return now_place.dist(place_action[i])<now_place.dist(place_action[j]);
}
);
if(candidate.size()>4){
candidate.resize(4);
}
return candidate;
}
bool operator<(State &s){
return calc_score()<s.calc_score();
}
};
template<typename T1, typename T2>
vector<Place> State<T1, T2>::place_shop;
template<typename T1, typename T2>
vector<Place> State<T1, T2>::place_action;
template<typename T1, typename T2>
vector<vector<int>> State<T1, T2>::bakuha_shop;
template<class Action,class Score,class State>
vector<pii> beam_search(State init_state,int width_beam,int max_depth){
vector<State> states={init_state};
vector<State> next_states;
for(int depth=0;depth<max_depth;depth++){
next_states.clear();
if(TIME.span()>2500){
width_beam=1;
}
for(int i=0;i<min<int>(width_beam,states.size());i++){
vector<Action> next_actions=states[i].find_next_actions();
for(Action action:next_actions){
State state=states[i];
state.apply(action);
next_states.push_back(state);
}
}
if(next_states.size()>width_beam){
nth_element(next_states.begin(),next_states.begin()+width_beam,next_states.end());
}
states=move(next_states);
}
sort(states.begin(),states.end());
cerr<<"score: "<<states[0].calc_score()<<endl;
return states[0].history_actions;
}
/*
店は最後に爆破する
*/
void solve(){
input();
//set coveringのインスタンスを作る
auto id_map=vmake(Height,Width,-1);
vector<Place> place_shops;
int num_hakai=0;
Place center_shop;
{
int min_center_dist=10000;
int id=0;
for(int h=0;h<Height;h++) for(int w=0;w<Width;w++){
if(map_input[h][w]=='.'){
Distance.set_cost(h,w,1);
}else{
Distance.set_cost(h,w,2);
}
if(map_input[h][w]=='@'){
if(chmin(min_center_dist,Place(25,25).dist(Place(h,w)))){
center_shop=Place(h,w);
}
place_shops.emplace_back(h,w);
}
if(map_input[h][w]!='#') continue;
id_map[h][w]=id++;
}
// for(auto shop:place_shops){
// if(shop==center_shop) continue;
// id_map[shop.h][shop.w]=id++;
// }
num_hakai=id;
}
using pPi=pair<Place,int>;
SetCovering<pPi,int,2500> SC(num_hakai);
for(int ph=0;ph<Height;ph++){
for(int pw=0;pw<Width;pw++){
Place p(ph,pw);
auto nearest_shop=find_nearest(p,place_shops,true);
int dist=p.dist(nearest_shop);
for(int b=0;b<num_bomb;b++){
vector<int> ids;
bool ok=true;
for(auto dp:bombs[b].ps){
auto np=p;
np.move(dp);
if(np==center_shop){
ok=false;
}
if(np.out_grid() or id_map[np.h][np.w]==-1){
continue;
}
ids.push_back(id_map[np.h][np.w]);
}
if(not ok) continue;
SC.add_set(pPi(p,b),bombs[b].cost+4*dist*2,ids);
}
}
}
SC.solve();
using pPi=pair<Place,int>;
vector<pPi> names;
for(int id:SC.best_solution){
names.push_back(SC.sets[id].name);
}
Place place_now(0,0);
//ビームサーチ
// template<>
// vector<Place> State<int, int>::place_shop;
// template<>
// vector<Place> State<int, int>::place_action;
// template<>
// vector<int> State<int, int>::bakuha_shop;
using State=State<int,int>;
State state(names.size(),place_shops.size());
state.place_shop=place_shops;
for(auto name:names){
state.place_action.push_back(name.first);
}
state.bakuha_shop.resize(names.size());
for(int a=0;a<names.size();a++){
for(int i=0;i<place_shops.size();i++){
auto shop=place_shops[i];
bool hakai=false;
for(auto dp:bombs[names[a].second].ps){
auto np=names[a].first;
np.move(dp);
if(shop==np) hakai=true;
}
if(hakai){
state.bakuha_shop[a].push_back(i);
}
}
}
auto actions_beam=beam_search<int,int,State>(state,10000,names.size());
for(int i=0;i<actions_beam.size();i++){
//次のターゲット
pPi name_nearest=names[actions_beam[i].first];
//一番近くの店に行って必要な爆弾を買う
Place nearest_shop=state.place_shop[actions_beam[i].second];
output_move(place_now,nearest_shop);
ans.push_back("2 "+to_string(name_nearest.second+1));
//ターゲットのところに行って爆弾を落とす
output_move(place_now,name_nearest.first);
ans.push_back("3 "+to_string(name_nearest.second+1));
//ターゲットを消す
// for(int i=0;i<names.size();i++){
// if(name_nearest.first==names[i].first and name_nearest.second==names[i].second){
// names.erase(names.begin()+i);
// break;
// }
// }
vector<Place> next_place_shops;
for(auto shop:place_shops){
bool hakai=false;
for(auto dp:bombs[name_nearest.second].ps){
auto np=place_now;
np.move(dp);
if(shop==np) hakai=true;
}
if(not hakai) next_place_shops.push_back(shop);
}
for(auto dp:bombs[name_nearest.second].ps){
auto np=place_now;
np.move(dp);
if(np.out_grid()) continue;
if(Distance.cost_grid[np.h][np.w]==2){
Distance.set_cost(np.h,np.w,1);
}
}
place_shops=next_place_shops;
}
cerr<<-1<<endl;
//一番安い爆弾の特定
int cheapest_bomb=-1;
int cheapest_cost=MAX;
for(int i=0;i<num_bomb;i++){
if(chmin(cheapest_cost,bombs[i].cost)){
cheapest_bomb=i;
}
}
while(place_shops.size()){
//一番近い店に行って一番安い爆弾を使う
Place nearest_shop=find_nearest(place_now,place_shops);
output_move(place_now,nearest_shop);
ans.push_back("2 "+to_string(cheapest_bomb+1));
ans.push_back("3 "+to_string(cheapest_bomb+1));
vector<Place> next_place_shops;
for(auto shop:place_shops){
bool hakai=false;
for(auto dp:bombs[cheapest_bomb].ps){
auto np=nearest_shop;
np.move(dp);
if(shop==np) hakai=true;
}
if(not hakai) next_place_shops.push_back(shop);
}
place_shops=next_place_shops;
}
cout<<ans.size()<<endl;
for(auto s:ans){
cout<<s<<endl;
}
#ifndef ONLINE_JUDGE
testTimer.output();
testCounter.output();
cerr<<TIME.span()<<"ms"<<endl;
//cerr<<"score: "<<simulate(best_grid,true)<<endl;
#endif
}
int main(const int argc,const char** argv){
#ifndef OPTUNA
if(argc!=1){
}
#endif
FastIO();
int T=1;
//cin>>T;
while(T--) solve();
}