結果
| 問題 | No.5019 Hakai Project |
| ユーザー |
 ぴぃいいいい
|
| 提出日時 | 2023-11-18 00:42:11 |
| 言語 | C++17(clang) (17.0.6 + boost 1.83.0) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 5,932 bytes |
| コンパイル時間 | 2,895 ms |
| コンパイル使用メモリ | 163,660 KB |
| 実行使用メモリ | 16,680 KB |
| スコア | 0 |
| 最終ジャッジ日時 | 2023-11-18 00:42:24 |
| 合計ジャッジ時間 | 11,122 ms |
|
ジャッジサーバーID （参考情報） |
judge11 / judge13 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | TLE | - |
| testcase_01 | -- | - |
| 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;
#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)); }
int n,m;
vector<int> c(20),l(20);
vector<vector<int>> a(20),b(20);
bool is_valid(int x,int y){
return 0<=x && x<n && 0<=y && y<n;
}
struct State{
vector<vector<char>> A;
vector<int> bomb;
int bomb_sum=0;
vector<pair<int,int>> hist;
ll building = 0;
ll shop = 0;
ll cost=0;
int nowx=0,nowy=0;
State(){}
State(vector<vector<char>> AA):A(AA){
bomb.resize(m);
for(int i=0;i<n;i++)for(int j=0;j<n;j++){
if(A[i][j]=='#' || A[i][j]=='@') building++;
if(A[i][j]=='@') shop++;
}
}
//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);
else cost += 2*(bomb_sum+1)*(bomb_sum+1);
}
//x,y:目的地の座標
void move(int x,int y){
while(nowx!=x){
if(nowx<x){
move('D');
}else{
move('U');
}
}
while(nowy!=y){
if(nowy<y){
move('R');
}else{
move('L');
}
}
}
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];
}
//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--;
}
//最も近い店の座標を返す
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;
}
//最も近い店に移動する
void move_nearest_shop(){
pii p = nearest_shop();
move(p);
}
//一手進める
void one_step(){
move_nearest_shop();
assert(A[nowx][nowy]=='@');
int best_eval = inf+1;
int best_i = -1;
int best_j = -1;
int best_k = -1;
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;
}
}
}
buy(best_k);
move(best_i,best_j);
use(best_k);
}
//出力
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<<"\n";
}
}
};
struct Solve{
vector<vector<char>> A;
void IN(){
cin.tie(nullptr);
ios::sync_with_stdio(false);
cin>>n>>m;
A.resize(n);
for(int i=0;i<n;i++){
A[i].resize(n);
for(int j=0;j<n;j++){
cin>>A[i][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(){
State state(A);
while(state.building>0){
state.one_step();
cerr<<state.building<<" "<<state.shop<<" "<<state.cost<<endl;
}
state.output();
}
};
int main(){
Solve solve;
solve.IN();
solve.solve();
}