Submission #18882


Source Code Expand

Copy
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
#include <cstring>
#include <numeric>
#include <cassert>
using namespace std;
static const double EPS = 1e-10;
typedef long long ll;
#define rep(i,n) for(int i=0;i<n;i++)
#define rev(i,n) for(int i=n-1;i>=0;i--)
#define all(a) a.begin(),a.end()
#define mp(a,b) make_pair(a,b)
#define pb(a) push_back(a)
#define SS stringstream
#define DBG1(a) rep(_X,sz(a)){printf("%d ",a[_X]);}puts("");
#define DBG2(a) rep(_X,sz(a)){rep(_Y,sz(a[_X]))printf("%d ",a[_X][_Y]);puts("");}
#define bitcount(b) __builtin_popcount(b)
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)

#define delete(a,n) a.erase(remove(all(a),n),a.end())
template<typename T, typename S> vector<T>& operator<<(vector<T>& a, S b) { a.push_back(b); return a; }
template<typename T> void operator>>(vector<T>& a, int b) {while(b--)if(!a.empty())a.pop_back();}
bool isprime(int n){ if(n<2)return false; for(int i=2;i*i<=n;i++)if(n%i==0)return false; return true;}
ll b_pow(ll x,ll n){return n ? b_pow(x*x,n/2)*(n%2?x:1) : 1ll;}
string itos(int n){stringstream ss;ss << n;return ss.str();}

#define INF (1<<29)

int X,Y;
string board[510];
double power[250010];

queue <int> q;
int dist[510][510];
int dx[] = {1,-1,0,0}, dy[] = {0,0,1,-1};

bool check(double c){
	for(int i = 0 ; i < X ; i++) for(int j = 0 ; j < Y ; j++) dist[i][j] = INF;
	
	for(int i = 0 ; i < X ; i++) for(int j = 0 ; j < Y ; j++) if( board[i][j] == 's' ){
		dist[i][j] = 0;
		q.push(i); q.push(j);
	}
	
	while(!q.empty()){
		int x = q.front(); q.pop(); int y = q.front(); q.pop();
		for(int i = 0 ; i < 4 ; i++){
			int x2 = x + dx[i], y2 = y + dy[i];
			if( x2 >= 0 && x2 < X && y2 >= 0 && y2 < Y && board[x2][y2] != '#' ){
				int d2 = dist[x][y] + 1;
				if( d2 < dist[x2][y2] && (board[x2][y2] == 'g' || (board[x2][y2] - '0') * power[d2] > c) ){
					dist[x2][y2] = d2;
					q.push(x2); q.push(y2);
				}
			}
		}
	}
	
	for(int i = 0 ; i < X ; i++) for(int j = 0 ; j < Y ; j++) if( board[i][j] == 'g' && dist[i][j] != INF ) return true;
	return false;
}

int main(){
	ios_base::sync_with_stdio(false);
	
	cin >> X >> Y;
	for(int i = 0 ; i < X ; i++) cin >> board[i];
	
	power[0] = 1.0;
	for(int i = 1 ; i < 250010 ; i++) power[i] = power[i-1] * 0.99;
	
	if(!check(0.0)){
		printf("-1.0\n");
		return 0;
	}
	
	double low = 0.0, high = 10.0;
	for(int i = 0 ; i < 40 ; i++){
		double mid = (high + low) / 2.0;
		if(check(mid)) low = mid; else high = mid;
	}
	
	printf("%.12f\n",low);
}

Submission Info

Submission Time
Task C - 暗闇帰り道
User kyulidenamida
Language C++ (G++ 4.6.4)
Score 100
Code Size 2870 Byte
Status AC
Exec Time 575 ms
Memory 3972 KB

Judge Result

Set Name all
Score / Max Score 100 / 100
Status
AC × 64
Set Name Test Cases
all 00_mini_01.txt, 00_mini_02.txt, 00_mini_03.txt, 00_mini_04.txt, 00_mini_05.txt, 00_sample_01.txt, 00_sample_02.txt, 01_rnd_01.txt, 01_rnd_02.txt, 01_rnd_03.txt, 01_rnd_04.txt, 01_rnd_05.txt, 01_rnd_06.txt, 01_rnd_07.txt, 01_rnd_08.txt, 01_rnd_09.txt, 01_rnd_10.txt, 01_rnd_11.txt, 01_rnd_12.txt, 01_rnd_13.txt, 01_rnd_14.txt, 01_rnd_15.txt, 01_rnd_16.txt, 01_rnd_17.txt, 01_rnd_18.txt, 01_rnd_19.txt, 01_rnd_20.txt, 02_maxrnd_01.txt, 02_maxrnd_02.txt, 02_maxrnd_03.txt, 02_maxrnd_04.txt, 02_maxrnd_05.txt, 02_maxrnd_06.txt, 02_maxrnd_07.txt, 02_maxrnd_08.txt, 02_maxrnd_09.txt, 02_maxrnd_10.txt, 02_maxrnd_11.txt, 02_maxrnd_12.txt, 02_maxrnd_13.txt, 02_maxrnd_14.txt, 02_maxrnd_15.txt, 02_maxrnd_16.txt, 02_maxrnd_17.txt, 02_maxrnd_18.txt, 02_maxrnd_19.txt, 03_hard_01.txt, 03_hard_02.txt, 03_hard_03.txt, 03_hard_04.txt, 03_hard_05.txt, 03_hard_06.txt, 03_hard_07.txt, 03_hard_08.txt, 04_open_01.txt, 04_open_02.txt, 05_minihard_01.txt, 05_minihard_02.txt, 05_minihard_03.txt, 05_minihard_04.txt, 05_minihard_05.txt, 05_minihard_06.txt, 05_minihard_07.txt, 05_minihard_08.txt
Case Name Status Exec Time Memory
00_mini_01.txt AC 40 ms 2680 KB
00_mini_02.txt AC 39 ms 2680 KB
00_mini_03.txt AC 38 ms 2676 KB
00_mini_04.txt AC 39 ms 2692 KB
00_mini_05.txt AC 39 ms 2672 KB
00_sample_01.txt AC 38 ms 2692 KB
00_sample_02.txt AC 38 ms 2680 KB
01_rnd_01.txt AC 399 ms 3708 KB
01_rnd_02.txt AC 125 ms 3480 KB
01_rnd_03.txt AC 50 ms 2936 KB
01_rnd_04.txt AC 87 ms 3060 KB
01_rnd_05.txt AC 46 ms 2808 KB
01_rnd_06.txt AC 42 ms 2804 KB
01_rnd_07.txt AC 51 ms 3588 KB
01_rnd_08.txt AC 164 ms 3716 KB
01_rnd_09.txt AC 211 ms 3712 KB
01_rnd_10.txt AC 257 ms 3724 KB
01_rnd_11.txt AC 156 ms 3316 KB
01_rnd_12.txt AC 118 ms 3200 KB
01_rnd_13.txt AC 56 ms 2808 KB
01_rnd_14.txt AC 336 ms 3572 KB
01_rnd_15.txt AC 179 ms 3200 KB
01_rnd_16.txt AC 54 ms 3068 KB
01_rnd_17.txt AC 43 ms 3312 KB
01_rnd_18.txt AC 39 ms 2820 KB
01_rnd_19.txt AC 39 ms 3444 KB
01_rnd_20.txt AC 40 ms 3584 KB
02_maxrnd_01.txt AC 203 ms 3960 KB
02_maxrnd_02.txt AC 189 ms 3972 KB
02_maxrnd_03.txt AC 225 ms 3964 KB
02_maxrnd_04.txt AC 353 ms 3968 KB
02_maxrnd_05.txt AC 238 ms 3964 KB
02_maxrnd_06.txt AC 543 ms 3960 KB
02_maxrnd_07.txt AC 148 ms 3968 KB
02_maxrnd_08.txt AC 119 ms 3964 KB
02_maxrnd_09.txt AC 575 ms 3956 KB
02_maxrnd_10.txt AC 175 ms 3968 KB
02_maxrnd_11.txt AC 558 ms 3972 KB
02_maxrnd_12.txt AC 326 ms 3968 KB
02_maxrnd_13.txt AC 405 ms 3960 KB
02_maxrnd_14.txt AC 448 ms 3964 KB
02_maxrnd_15.txt AC 151 ms 3968 KB
02_maxrnd_16.txt AC 360 ms 3956 KB
02_maxrnd_17.txt AC 274 ms 3960 KB
02_maxrnd_18.txt AC 43 ms 3964 KB
02_maxrnd_19.txt AC 43 ms 3968 KB
03_hard_01.txt AC 404 ms 3956 KB
03_hard_02.txt AC 416 ms 3960 KB
03_hard_03.txt AC 107 ms 3964 KB
03_hard_04.txt AC 109 ms 3964 KB
03_hard_05.txt AC 406 ms 3956 KB
03_hard_06.txt AC 415 ms 3960 KB
03_hard_07.txt AC 107 ms 3972 KB
03_hard_08.txt AC 108 ms 3968 KB
04_open_01.txt AC 449 ms 3960 KB
04_open_02.txt AC 430 ms 3960 KB
05_minihard_01.txt AC 40 ms 2796 KB
05_minihard_02.txt AC 40 ms 2808 KB
05_minihard_03.txt AC 40 ms 2812 KB
05_minihard_04.txt AC 40 ms 2812 KB
05_minihard_05.txt AC 40 ms 2812 KB
05_minihard_06.txt AC 40 ms 2812 KB
05_minihard_07.txt AC 39 ms 2820 KB
05_minihard_08.txt AC 40 ms 2820 KB