結果

問題 No.5019 Hakai Project
ユーザー ぴぃいいいい
提出日時 2023-11-23 22:39:50
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 2,903 ms / 3,000 ms
コード長 16,701 bytes
コンパイル時間 8,811 ms
コンパイル使用メモリ 345,452 KB
実行使用メモリ 6,676 KB
スコア 2,816,704,769
最終ジャッジ日時 2023-11-23 22:42:33
合計ジャッジ時間 162,586 ms
ジャッジサーバーID
(参考情報)
judge11 / judge13
純コード判定しない問題か言語
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
other AC * 50
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In member function 'void Bombplan::greedy_all()':
main.cpp:188:38: warning: 'best_k' may be used uninitialized [-Wmaybe-uninitialized]
  188 |             is_broken |= explode_wind(best_k,best_i,best_j);
      |                          ~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
main.cpp:144:31: note: 'best_k' was declared here
  144 |             int best_i,best_j,best_k;
      |                               ^~~~~~
main.cpp:188:38: warning: 'best_j' may be used uninitialized [-Wmaybe-uninitialized]
  188 |             is_broken |= explode_wind(best_k,best_i,best_j);
      |                          ~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
main.cpp:144:24: note: 'best_j' was declared here
  144 |             int best_i,best_j,best_k;
      |                        ^~~~~~
main.cpp:188:38: warning: 'best_i' may be used uninitialized [-Wmaybe-uninitialized]
  188 |             is_broken |= explode_wind(best_k,best_i,best_j);
      |                          ~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
main.cpp:144:17: note: 'best_i' was declared here
  144 |             int best_i,best_j,best_k;
      |                 ^~~~~~

ソースコード

diff #
プレゼンテーションモードにする

#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;
char init_A[50][50];
int c[20],l[20];
bitset<2500> explode_range[20];
bitset<2500> mask_bit_x[50];
bitset<2500> mask_bit_y[50];
bitset<2500> init_broken;
bitset<2500> init_shop;
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;
}
bitset<2500> explode_wind(int k, int x, int y){
int diff_bit = n*(x-20) + (y-20);
bitset<2500> tmpran = (diff_bit>0) ? (explode_range[k]<<diff_bit) : (explode_range[k]>>(-diff_bit));
tmpran &= mask_bit_x[x] & mask_bit_y[y];
return tmpran;
}
struct Field{
bitset<2500> is_broken;
bitset<2500> is_shop;
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++){
if(AA[i][j]=='.'){
is_broken[i*n+j] = 1;
is_shop[i*n+j] = 0;
}
if(AA[i][j]=='#'){
is_broken[i*n+j] = 0;
is_shop[i*n+j] = 0;
}
if(AA[i][j]=='@'){
is_broken[i*n+j] = 0;
is_shop[i*n+j] = 1;
}
}
building = 2500 - is_broken.count();
shop = is_shop.count();
}
void use(int k,int x,int y){
is_broken |= explode_wind(k,x,y);
is_shop &= ~is_broken;
}
};
struct Bombplan{
bitset<2500> is_broken;
bitset<2500> is_shop;
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++){
if(AA[i][j]=='.'){
is_broken[i*n+j] = 1;
is_shop[i*n+j] = 0;
}
if(AA[i][j]=='#'){
is_broken[i*n+j] = 0;
is_shop[i*n+j] = 0;
}
if(AA[i][j]=='@'){
is_broken[i*n+j] = 0;
is_shop[i*n+j] = 1;
}
}
cost = 0;
#ifdef LOG_DEBUG
cerr<<"bombplan construct"<<endl;
#endif
}
void update_cost(){
cost = 0;
for(auto [k,x,y]:explodes){
cost += c[k];
}
}
//greedy
void greedy_all(){
int MAX_ITER = 40000;
is_broken = init_broken;
is_shop = init_shop;
int building = 2500-init_broken.count();
explodes.clear();
#ifdef LOG_DEBUG
cerr<<"greedy_all() header end"<<endl;
#endif
while(building>0){
#ifdef LOG_DEBUG
cerr<<"simulation building is "<<building<<endl;
#endif
int best_i,best_j,best_k;
double best = (double)INF;
//
#ifdef LOG_DEBUG
int skip_zero = 0;
#endif
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);
// -> broken_cnt
int diff_bit = n*(i-20) + (j-20);
int broken_cnt = (explode_wind(k,i,j) & (~is_broken)).count();
if(broken_cnt==0){
#ifdef LOG_DEBUG
skip_zero++;
#endif
continue;
}
double tmp = (double)c[k]/(double)(broken_cnt);
if(chmin(best,tmp)){
best_i = i;
best_j = j;
best_k = k;
#ifdef LOG_DEBUG
cerr<<"update broken_cnt is "<<broken_cnt<<endl;
#endif
}
}
#ifdef LOG_DEBUG
cerr<<"skip_zero is "<<skip_zero<<endl;
#endif
//best
explodes.insert(make_tuple(best_k,best_i,best_j));
#ifdef LOG_DEBUG
cerr<<"accepted is "<<(tmpran & (~is_broken)).count()<<endl;
#endif
is_broken |= explode_wind(best_k,best_i,best_j);
is_shop &= ~is_broken;
building = 2500 - is_broken.count();
}
#ifdef LOG_DEBUG
cerr<<"simulation end"<<endl;
cerr<<"greedy_all() end"<<endl;
#endif
update_cost();
}
void output(){
cerr<<explodes.size()<<endl;
for(auto [k,x,y]:explodes){
cerr<<k<<" "<<x<<" "<<y<<endl;
}
}
vector<tuple<int,int,int>> explode_list(){
vector<tuple<int,int,int>> res(all(explodes));
return res;
}
};
struct State{
bitset<2500> is_broken, is_shop;
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;
State(){}
State(char AA[50][50]){
for(int i=0;i<n;i++)for(int j=0;j<n;j++){
if(AA[i][j]=='.'){
is_broken[i*n+j] = 1;
is_shop[i*n+j] = 0;
}
if(AA[i][j]=='#'){
is_broken[i*n+j] = 0;
is_shop[i*n+j] = 0;
}
if(AA[i][j]=='@'){
is_broken[i*n+j] = 0;
is_shop[i*n+j] = 1;
}
}
building = 2500 - is_broken.count();
shop = is_shop.count();
}
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]+(!is_broken[(sx+dx*(i+1))*n + (sy+dy*j)])+1);
}
if(j+1<=abs(gy-sy)){
chmin(dp[i][j+1],dp[i][j]+(!is_broken[(sx+dx*i)*n + (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]+(!is_broken[(sx+dx*i)*n + (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(is_broken[nowx*n+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(is_shop[nowx*n+nowy]);
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));
is_broken |= explode_wind(i,nowx,nowy);
is_shop &= ~is_broken;
building = 2500 - is_broken.count();
shop = is_shop.count();
bomb[i]--;
bomb_sum--;
}
//使,,center_shop
pair<int,int> use_simulate(int i,int x,int y){
assert(i>=0 && i<m);
int diff_bit = n*(x*20) + (y-20);
bitset<2500> tmpran = explode_wind(i,x,y);
int broken_building = (tmpran & (~is_broken)).count();
int broken_shop = (tmpran & is_shop).count();
return make_pair(broken_building,broken_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(is_shop[i*n+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(is_shop[i*n+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 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] = 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);
}
}
}
//
double eval_func(double usecost,double broken_building,double broken_shop){
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;
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];
if(A[i][j]=='.'){
init_broken[i*n+j] = 1;
init_shop[i*n+j] = 0;
}
if(A[i][j]=='#'){
init_broken[i*n+j] = 0;
init_shop[i*n+j] = 0;
}
if(A[i][j]=='@'){
init_broken[i*n+j] = 0;
init_shop[i*n+j] = 1;
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<n;i++)for(int j=0;j<n;j++) init_A[i][j] = A[i][j];
for(int i=0;i<m;i++){ //i
cin>>c[i]>>l[i];
for(int j=0;j<l[i];j++){ //j
int tmpa,tmpb;
cin>>tmpa>>tmpb;
tmpa+=20,tmpb+=20;
explode_range[i][tmpa*n + tmpb] = 1;
}
}
//mask-bit
bitset<2500> tate(0),yoko(0);
for(int i=0;i<50;i++){
tate[n*i] = 1;
yoko[i] = 1;
}
for(int i=0;i<50;i++){
mask_bit_x[i].reset();
mask_bit_y[i].reset();
for(int j=max(0,i-20);j<=min(49,i+20);j++){
mask_bit_x[i] |= yoko<<(n*j);
mask_bit_y[i] |= tate<<(j);
}
}
}
void solve(){
/* cerr<<"start"<<endl;
Bombplan bombplan(A);
bombplan.greedy_all();
cerr<<"cost:"<<bombplan.cost<<endl; */
sa();
}
void sa(){
Bombplan bombplan(A);
bombplan.greedy_all();
vector<tuple<int,int,int>> plan = bombplan.explode_list();
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 = 30;
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
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0