/* 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 using namespace std; using ll=long long int; //using Int=__int128; #define mask(x) ((1LL< bool chmin(T1 &a,T2 b){if(a<=b)return 0; a=b; return 1;} template bool chmax(T1 &a,T2 b){if(a>=b)return 0; a=b; return 1;} template 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; using pil=pair; using pli=pair; using pll=pair; using psi=pair; using pis=pair; using psl=pair; using pls=pair; using pss=pair; template using minimum_queue=priority_queue,greater>; using Graph=vector>; 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 inline istream &operator>>(istream &is,vector &v) { for(size_t i=0;i>v[i]; return is; } //0-indexed vector cin template inline istream &operator>>(istream &is,vector> &v) { for(size_t i=0;i>v[i]; } return is; } struct Xor32{ using u32=uint32_t; u32 x=1234567; inline u32 rnd_make(){ x^=(x<<13); x=x^(x>>17); return x=x^(x<<5); } 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つを選ぶ first 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}; } }; 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(now-st).count(); } }; struct TestTimer{ chrono::high_resolution_clock::time_point st; unordered_map sum_time; unordered_map 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(now-start_time[s]).count(); #endif } void output()const{ #ifndef ONLINE_JUDGE for(auto m:sum_time){ cerr< cnt; TestCounter(){} void count(const string &s){ #ifndef ONLINE_JUDGE cnt[s]++; #endif } void output()const{ #ifndef ONLINE_JUDGE for(auto m:cnt){ cerr< class DynamicArray{ public: array 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 inline void vsort(vector &v){ sort(v.begin(),v.end()); } //逆順ソート template inline void rvsort(vector &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 inline void Compress(vector &C){ sort(C.begin(),C.end()); C.erase(unique(C.begin(),C.end()),C.end()); } //要素数n 初期値x template inline vector vmake(size_t n,T x){ return vector(n,x); } //a,b,c,x data[a][b][c] 初期値x template auto vmake(size_t n,Args... args){ auto v=vmake(args...); return vector(n,move(v)); } //vは昇順 bool is_in(const vector &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] struct edge { int to; T cost; int id; edge()=default; edge(int to, T cost,int id) : to(to), cost(cost), id(id) {} }; template 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 &e){ return cost &e){ return cost<=e.cost; } }; template using WeightGraph=vector>>; //vector cout template inline ostream &operator<<(ostream &os,const vector &v) { bool sp=true; if(string(typeid(T).name())=="c") sp=false; for(size_t i=0;i cout template inline ostream &operator<<(ostream &os,const vector> &v) { for(size_t i=0;i inline ostream &operator<<(ostream &os,const pair &p) { os< inline ostream &operator<<(ostream &os,const map &M) { bool first=false; for(auto x:M){ if(first) os< inline ostream &operator<<(ostream &os,const set &S) { bool first=false; for(auto x:S){ if(first) os< inline istream &operator>>(istream &is,pair &p) { is>>p.first>>p.second; return is; } template void append(vector &v,const vector &vp){ for(auto p:vp){ v.push_back(p); } } //Fisher–Yatesアルゴリズム template void shuffle(vector &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 struct IntSet{ DynamicArray set_; array pos_; IntSet(){ for(int i=0;i 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 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){ 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]=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; } //上下 左右 bool operator<(Place &p){ if(p.h!=h) return h>(istream& is, Place& p){ is>>p.h>>p.w; return is; } friend ostream& operator<<(ostream& os, Place& p){ os< &ps){ int distance=MAX; Place nearest; for(auto p:ps){ if(chmin(distance,dist(p))){ nearest=p; } } return nearest; } template pair find_nearest(const vector> &ps){ int distance=MAX; pair nearest; for(auto p:ps){ if(chmin(distance,dist(p.first))){ nearest=p; } } return nearest; } void output_move(Place p){ while(dist(p)){ int now_dist=dist(p); for(int dir=0;dir<4;dir++){ move(dir); int next_dist=dist(p); if(next_dist ps; }; constexpr int num_bomb=20; auto map_input=vmake(Height,Width,'.'); vector bombs(num_bomb); void input(){ int dummy; cin>>dummy>>dummy; for(int h=0;h>map_input[h][w]; } for(int b=0;b>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 struct SetCovering{ struct Set{ Name name; Cost cost; vector elements; }; int num_element; vector sets; SetCovering(int num_element):num_element(num_element){ } void add_set(Name name,Cost cost,vector elements){ sets.push_back({name,cost,elements}); } vector> make_sets_contain(){ vector> 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+要素数の合計) vector solve_greedy(){ int num_set=sets.size(); vector is_covered(num_element,false); auto sets_contain=make_sets_contain(); vector num_uncovered(num_set); for(int s=0;s ans; Cost cost_sum=0; while(true){ //一番コスパ(num_uncovered/cost)が高いものを選ぶ int id_best=-1; double costper_best=-1; for(int i=0;i place_shops; int num_hakai=0; { int id=0; for(int h=0;h; SetCovering SC(num_hakai); for(int ph=0;ph ids; for(auto dp:bombs[b].ps){ auto np=p; np.move(dp); if(np.out_grid() or id_map[np.h][np.w]==-1){ continue; } ids.push_back(id_map[np.h][np.w]); } SC.add_set(pPi(p,b),bombs[b].cost,ids); } } } auto names=SC.solve_greedy(); Place place_now(0,0); //一番近くの店に行って爆弾を全部買う Place nearest_shop=place_now.find_nearest(place_shops); place_now.output_move(nearest_shop); for(auto name:names){ ans.push_back("2 "+to_string(name.second+1)); } //一番近くのところに行って爆弾を落とすのを繰り返す while(names.size()){ pPi name_nearest=place_now.find_nearest(names); place_now.output_move(name_nearest.first); ans.push_back("3 "+to_string(name_nearest.second+1)); for(int i=0;i>T; while(T--) solve(); }