Submission #18807


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){
				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;
	
	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 0
Code Size 2784 Byte
Status WA
Exec Time 526 ms
Memory 4076 KB

Judge Result

Set Name all
Score / Max Score 0 / 100
Status
AC × 57
WA × 7
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 42 ms 2684 KB
00_mini_02.txt AC 39 ms 2684 KB
00_mini_03.txt AC 38 ms 2688 KB
00_mini_04.txt AC 37 ms 2768 KB
00_mini_05.txt WA 42 ms 2684 KB
00_sample_01.txt AC 37 ms 2676 KB
00_sample_02.txt AC 38 ms 2684 KB
01_rnd_01.txt AC 317 ms 3712 KB
01_rnd_02.txt AC 104 ms 3580 KB
01_rnd_03.txt AC 47 ms 2944 KB
01_rnd_04.txt AC 77 ms 3076 KB
01_rnd_05.txt AC 47 ms 2884 KB
01_rnd_06.txt AC 41 ms 2820 KB
01_rnd_07.txt AC 49 ms 3588 KB
01_rnd_08.txt AC 137 ms 3712 KB
01_rnd_09.txt AC 176 ms 3720 KB
01_rnd_10.txt AC 218 ms 3704 KB
01_rnd_11.txt AC 136 ms 3332 KB
01_rnd_12.txt AC 108 ms 3200 KB
01_rnd_13.txt AC 56 ms 2904 KB
01_rnd_14.txt AC 293 ms 3576 KB
01_rnd_15.txt AC 156 ms 3200 KB
01_rnd_16.txt AC 51 ms 3068 KB
01_rnd_17.txt WA 151 ms 3328 KB
01_rnd_18.txt WA 41 ms 2820 KB
01_rnd_19.txt WA 48 ms 3412 KB
01_rnd_20.txt WA 43 ms 3664 KB
02_maxrnd_01.txt AC 168 ms 4076 KB
02_maxrnd_02.txt AC 156 ms 3968 KB
02_maxrnd_03.txt AC 201 ms 3968 KB
02_maxrnd_04.txt AC 285 ms 4044 KB
02_maxrnd_05.txt AC 193 ms 4072 KB
02_maxrnd_06.txt AC 483 ms 3968 KB
02_maxrnd_07.txt AC 134 ms 4024 KB
02_maxrnd_08.txt AC 174 ms 4044 KB
02_maxrnd_09.txt AC 526 ms 3972 KB
02_maxrnd_10.txt AC 152 ms 4032 KB
02_maxrnd_11.txt AC 485 ms 4036 KB
02_maxrnd_12.txt AC 283 ms 4068 KB
02_maxrnd_13.txt AC 352 ms 3964 KB
02_maxrnd_14.txt AC 395 ms 4004 KB
02_maxrnd_15.txt AC 135 ms 3964 KB
02_maxrnd_16.txt AC 320 ms 3964 KB
02_maxrnd_17.txt AC 257 ms 3968 KB
02_maxrnd_18.txt WA 102 ms 3972 KB
02_maxrnd_19.txt WA 95 ms 3968 KB
03_hard_01.txt AC 331 ms 4052 KB
03_hard_02.txt AC 326 ms 3968 KB
03_hard_03.txt AC 94 ms 4060 KB
03_hard_04.txt AC 99 ms 3968 KB
03_hard_05.txt AC 345 ms 4048 KB
03_hard_06.txt AC 349 ms 3968 KB
03_hard_07.txt AC 95 ms 4044 KB
03_hard_08.txt AC 101 ms 4036 KB
04_open_01.txt AC 349 ms 4044 KB
04_open_02.txt AC 356 ms 4032 KB
05_minihard_01.txt AC 40 ms 2816 KB
05_minihard_02.txt AC 39 ms 2816 KB
05_minihard_03.txt AC 40 ms 2808 KB
05_minihard_04.txt AC 41 ms 2808 KB
05_minihard_05.txt AC 39 ms 2764 KB
05_minihard_06.txt AC 40 ms 2904 KB
05_minihard_07.txt AC 43 ms 2884 KB
05_minihard_08.txt AC 39 ms 2904 KB