Submission #2550088


Source Code Expand

#include <bits/stdc++.h>
#define REP(i,n) for (long long i=0;i<(n);i++)
#define FOR(i,a,b) for (long long i=(a);i<(b);i++)
#define RREP(i,n) for(long long i=n;i>=0;i--)
#define RFOR(i,a,b) for(long long i=(a);i>(b);i--)
#define dump1d_arr(array) REP(i,array.size()) cerr << #array << "[" << (i) << "] ==> " << (array[i]) << endl;
#define dump2d_arr(array) REP(i,array.size()) REP(j,array[i].size()) cerr << #array << "[" << (i) << "]" << "[" << (j) << "] ==> " << (array[i][j]) << endl;
#define dump(x)  cerr << #x << " => " << (x) << endl;
#define dumpP(p) cerr << "( " << p.first << " , " << p.second << " )" << ends;
#define CLR(vec) { REP(i,vec.size()) vec[i] = 0; } 
#define SORT(c) sort((c).begin(),(c).end())
#define MIN(vec) *min_element(vec.begin(), vec.end());
#define MAX(vec) *max_element(vec.begin(), vec.end());
#define UNIQ(vec) vec.erase(unique(vec.begin(), vec.end()),vec.end());
#define IN(n,m)  (!(m.find(n) == m.end()))
#define ENUM(m) for (auto itr = m.begin(); itr != m.end(); ++itr)
#define dump_MAP(m) for(auto itr = m.begin(); itr != m.end(); ++itr) { cerr << itr->first << " --> "  << itr->second << endl; }
#define FINDL(vec,x) (lower_bound(vec.begin(),vec.end(),x) - vec.begin())
#define FINDU(vec,x) (upper_bound(vec.begin(),vec.end(),x) - vec.begin())
#define ROUND(N) setprecision(N)
#define ROUND_PRINT(N,val) cout << fixed;cout << setprecision(N) << val << endl
using namespace std;
constexpr int dx[4] = {0,1,-1,0};
constexpr int dy[4] = {1,0,0,-1};
constexpr long double pi = M_PI;
constexpr double eps = 1e-10;
constexpr long mod = 1000000007;
constexpr short shINF = 32767;
constexpr long loINF = 2147483647;
constexpr long long llINF = 9223372036854775807;
typedef long long LL;
typedef vector<double> VD;
typedef vector<VD> VVD;
typedef vector<LL> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<LL,LL> pr;
typedef tuple<LL,LL,LL> tp;
typedef vector<pr> VP;
typedef map<tp,LL> mp;
struct Order {
	bool operator() (pr const& a,pr const& b) const {
		return a.first > b.first || ((a.first == b.first) && (a.second > b.second));
	}
};


template <typename T>
class Integer {
private:
	bool primeflg;
	bool factorialflg;
	vector<T> prime_list;
	vector<T> factorial;
	vector<long> prime_num;
	vector<bool> prime_table;

	void factorialModInit(T maxval) {
		factorialflg = true;
		factorial = vector<T>(maxval+1); 
		factorial[0] = factorial[1] = 1;
		for (T i = 2;i < (maxval+1);i++) {
			factorial[i] = (factorial[i-1]*i)%mod;
		}
	}

public:
	Integer()  : primeflg(false),factorialflg(false) {}

	//素数関連
	void Eratosthenes(T n) { // n以下の数でエラトステネスのふるいを作る。 
		primeflg = true;
		prime_table = vector<bool>(n+1,true);
		prime_num = vector<long>(n+1,0);
		T maxiter = sqrt(n);
		for(T i = 2;i < maxiter+1;i++){
			if (prime_table[i]) {
				for (T j = (i + i);j <= n;j += i){
					prime_table[j] = false;
				}
			}
		}
		T prnum = 0;
		for(T i = 2;i < n+1;i++){
			if (prime_table[i]) {
				prnum++;
				prime_list.push_back(i);
			}
			prime_num[i] = prnum;
		}
	}

	bool isPrimeNum(T n) { //素数かどうか判定
		if (!primeflg) Eratosthenes(max(n,(T)100)); 
		return prime_table[n];
	}

	vector<T>* getPrimeList(T n = 100){ //n以下の素数リスト
		if (!primeflg) Eratosthenes(n); 
		return (&prime_list);
	}

	long getPrimeNumUnder_N(T n) { //n以下の素数の個数。
		if (!primeflg) Eratosthenes(max(n,(T)100));
		return prime_num[n];
	}

	long getPrimeNum_NM(T k,T m){  //k以上m以下の素数の個数。(kはN以下ならok)
		if (!primeflg) Eratosthenes(max(m,(T)100)); 
		return prime_num[m] - prime_num[k];
	}

	//約数倍数関連
	map<T,long>* getFactoringMap(T n) { // 素因数分解 key->因数 val->因数の数
		map<T,long> factoring;
		T copy_n = n;
		T maxiter = sqrt(n);
		for (T i = 2;i < maxiter+1;i ++) {
			if (copy_n == 1) break;
			while (!(copy_n % i)) {
				factoring[i]++;
				copy_n /= i;
			}
		}
		if (copy_n != 1) factoring[copy_n]++;
		return (&factoring);
	}

	vector<long> getFactoringElement(T n) {
		vector<long> factoring;
		map<T,long>* m = getFactoringMap(n);
		for (auto itr = m.begin();itr != m.end();++itr) {
			factoring.push_back(itr->first);
		}
	} 

	// gcd(num ≤ N,K) = p を満たすnumの和
	T gcdSum(T N,T K,T p) {
		T n = n / p;
		T k = K / p;
		long long ret = (n*(n+1))/2;
		map<T,long> m = getFactoring(k);
		long l = m.size();
		long long maxbit = (1 << l);
		long long mul;
		long long s;
		for (auto itr = m.begin();itr != m.end();++itr) {
			FOR(bit,1,maxbit) {
				mul = 1;
				REP(j,l) if ((bit >> j) & 1) mul *= m[j];
				s = n/mul;
				if (__builtin_parityll(bit)) ret -= ((s*(s+1)/2)*mul);
				else ret += (((s*(s+1)/2))*mul);
			}
		}
		return (s*ret);
	}


	T gcd(T a,T b) {
 		 return b != 0 ? gcd(b, a % b) : a;
	}

	T lcm(T a,T b) {
  		return (a / gcd(a, b))*b;
	}

	long getFactorial(T n) { // nの階乗の値を求める。
		if (!factorialflg) factorialModInit(n);
		return factorial[n];
	}

	long long square_pow(long long a,long x){ // (a^x) % mod (繰り返し二乗)
		T p = a;
		T q = 1LL;
		while (x != 0){
			if (x & 1) q = (q * p) % mod;
			p = (p * p) % mod;
			x >>= 1;
		}	
		return q;
	}

	long long mod_inv(long long a) { // aの逆元 % mod
		return square_pow(a,mod-2);
	}

	long long nCr(T n,T r) {
		r = min(r,n-r);
		long long retval = 1;
		for (long i = 1;i < r+1;i ++){
			retval *= n - r + i;
			retval /= i;
		}
		return retval;
	}

	long long nCrMod(T n,T r) { // nCr 使用前に初期化必要
		if (!factorialflg) factorialModInit(n);
		return (((factorial[n]%mod * mod_inv(factorial[r]))%mod) * mod_inv(factorial[n-r]))%mod;
	}

	long long nPrMod(T n,T r) {
		if (!factorialflg) factorialModInit(n);
		return ((factorial[n]%mod) * mod_inv(factorial[n-r]))%mod;
	}
};


int main(void) {
	Integer<LL> it;
	LL N,D,X,Y,X_r,Y_r,ud;
	long double pat = 0.0;
	cin >> N >> D;
	cin >> X >> Y;
	if (X % D || Y % D){
		cout << "0.0" << endl;
		exit(0);
	}
	X = abs(X) / D;
	Y = abs(Y) / D;
	FOR(lr,X,N+1) {
		ud = (N - lr);
		if (ud < Y) break;
		if (((lr - X) % 2) || ((ud - Y) % 2)) continue;
		// 同じ位置に戻る移動を1セットに
		X_r = (lr - X)/2;
		Y_r = (ud - Y)/2;
		pat += (it.nCr(N,lr)*it.nCr(lr,X_r)*it.nCr(ud,Y_r));
	}
	REP(i,N) pat *= 0.25;
	//dump(pat)
	cout << ROUND(15) << pat << endl;
}

Submission Info

Submission Time
Task D - 大ジャンプ
User banboooo044
Language C++14 (GCC 5.4.1)
Score 100
Code Size 6561 Byte
Status WA
Exec Time 8 ms
Memory 256 KB

Judge Result

Set Name part1 part2 All
Score / Max Score 90 / 90 10 / 10 0 / 1
Status
AC × 23
AC × 36
AC × 62
WA × 9
Set Name Test Cases
part1 test_1_151403858_0_0AB.txt, test_1_1_0_1AB.txt, test_1_1_2_0AB.txt, test_1_200416616_-430405070_-79858930AB.txt, test_1_320861287_0_0AB.txt, test_1_445441131_0_0AB.txt, test_2_91743015_0_183486030AB.txt, test_3_165357536_496072608_0AB.txt, test_3_357154050_-106436394_768502001AB.txt, test_3_721501125_-568833455_353553641AB.txt, test_3_893846474_0_0AB.txt, test_4_291388018_-291388018_0AB.txt, test_5_318547875_955643625_-637095750AB.txt, test_5_704387671_-704387671_0AB.txt, test_5_82323965_639854915_-688317394AB.txt, test_6_187422602_374845204_-374845204AB.txt, test_6_346164451_0_0AB.txt, test_6_99058019_194123640_-837769837AB.txt, test_7_166330212_166330212_-332660424AB.txt, test_7_89698746_448493730_-179397492AB.txt, test_8_10000000_-40000000_-40000000AB.txt, test_8_10000000_0_80000000AB.txt, test_8_10000000_80000000_0AB.txt
part2 test_10_227248639_454497278_0B.txt, test_11_692637325_-181424149_-938839075B.txt, test_13_260236679_-780710037_-520473358B.txt, test_13_269280357_807841071_269280357B.txt, test_13_96859935_0_-581159610B.txt, test_16_40374395_-40374395_-565241530B.txt, test_1_151403858_0_0AB.txt, test_1_1_0_1AB.txt, test_1_1_2_0AB.txt, test_1_200416616_-430405070_-79858930AB.txt, test_1_320861287_0_0AB.txt, test_1_445441131_0_0AB.txt, test_21_304856339_609712678_914569017B.txt, test_26_214390232_-857560928_428780464B.txt, test_2_91743015_0_183486030AB.txt, test_30_10000000_-300000000_0B.txt, test_30_10000000_0_300000000B.txt, test_30_10000000_150000000_-150000000B.txt, test_30_54228128_0_813421920B.txt, test_3_165357536_496072608_0AB.txt, test_3_357154050_-106436394_768502001AB.txt, test_3_721501125_-568833455_353553641AB.txt, test_3_893846474_0_0AB.txt, test_4_291388018_-291388018_0AB.txt, test_5_318547875_955643625_-637095750AB.txt, test_5_704387671_-704387671_0AB.txt, test_5_82323965_639854915_-688317394AB.txt, test_6_187422602_374845204_-374845204AB.txt, test_6_346164451_0_0AB.txt, test_6_99058019_194123640_-837769837AB.txt, test_7_166330212_166330212_-332660424AB.txt, test_7_89698746_448493730_-179397492AB.txt, test_8_10000000_-40000000_-40000000AB.txt, test_8_10000000_0_80000000AB.txt, test_8_10000000_80000000_0AB.txt, test_9_283198156_849594468_849594468B.txt
All sample_01.txt, sample_02.txt, sample_03.txt, test_1000_1000000_-500000000_500000000.txt, test_1000_1000000_0_-1000000000.txt, test_1000_1000000_1000000000_0.txt, test_1000_150305_97998860_-32315575.txt, test_1000_1_0_0.txt, test_1000_1_2_0.txt, test_1000_1_2_2.txt, test_1000_3308678_-800700076_-350719868.txt, test_1000_3608549_811923525_689232859.txt, test_1000_3728577_-145414503_-969430020.txt, test_1000_537976_11297496_224335992.txt, test_10_227248639_454497278_0B.txt, test_11_692637325_-181424149_-938839075B.txt, test_130_95365311_-667557177_-286095933.txt, test_131_18204705_-145637640_0.txt, test_13_260236679_-780710037_-520473358B.txt, test_13_269280357_807841071_269280357B.txt, test_13_96859935_0_-581159610B.txt, test_16_40374395_-40374395_-565241530B.txt, test_1_151403858_0_0AB.txt, test_1_1_0_1AB.txt, test_1_1_2_0AB.txt, test_1_200416616_-430405070_-79858930AB.txt, test_1_320861287_0_0AB.txt, test_1_445441131_0_0AB.txt, test_210_28974130_0_260767170.txt, test_217_321156_24407856_22480920.txt, test_21_304856339_609712678_914569017B.txt, test_26_214390232_-857560928_428780464B.txt, test_289_421462830_-487186374_-417635361.txt, test_2_91743015_0_183486030AB.txt, test_30_10000000_-300000000_0B.txt, test_30_10000000_0_300000000B.txt, test_30_10000000_150000000_-150000000B.txt, test_30_54228128_0_813421920B.txt, test_339_4475128_957677392_281933064.txt, test_3_165357536_496072608_0AB.txt, test_3_357154050_-106436394_768502001AB.txt, test_3_721501125_-568833455_353553641AB.txt, test_3_893846474_0_0AB.txt, test_480_402960_-131767920_-34654560.txt, test_4_291388018_-291388018_0AB.txt, test_507_3516183_-879045750_-253165176.txt, test_515_8606048_-25818144_8606048.txt, test_522_2286376_-230923976_-18291008.txt, test_5_318547875_955643625_-637095750AB.txt, test_5_704387671_-704387671_0AB.txt, test_5_82323965_639854915_-688317394AB.txt, test_676_198114948_0_792459792.txt, test_688_151937211_-286341114_10198771.txt, test_6_187422602_374845204_-374845204AB.txt, test_6_346164451_0_0AB.txt, test_6_99058019_194123640_-837769837AB.txt, test_71_367604060_367604060_0.txt, test_752_120973200_0_-725839200.txt, test_772_881340073_0_0.txt, test_777_125719576_-499451637_822057459.txt, test_7_166330212_166330212_-332660424AB.txt, test_7_89698746_448493730_-179397492AB.txt, test_839_166155061_0_-332310122.txt, test_839_923157_923157_564972084.txt, test_849_415705_290993500_0.txt, test_873_418406_2928842_322172620.txt, test_8_10000000_-40000000_-40000000AB.txt, test_8_10000000_0_80000000AB.txt, test_8_10000000_80000000_0AB.txt, test_981_159373724_-637494896_-159373724.txt, test_9_283198156_849594468_849594468B.txt
Case Name Status Exec Time Memory
sample_01.txt AC 1 ms 256 KB
sample_02.txt AC 1 ms 256 KB
sample_03.txt AC 1 ms 256 KB
test_1000_1000000_-500000000_500000000.txt AC 1 ms 256 KB
test_1000_1000000_0_-1000000000.txt AC 1 ms 256 KB
test_1000_1000000_1000000000_0.txt AC 1 ms 256 KB
test_1000_150305_97998860_-32315575.txt AC 1 ms 256 KB
test_1000_1_0_0.txt WA 8 ms 256 KB
test_1000_1_2_0.txt WA 8 ms 256 KB
test_1000_1_2_2.txt WA 8 ms 256 KB
test_1000_3308678_-800700076_-350719868.txt AC 5 ms 256 KB
test_1000_3608549_811923525_689232859.txt AC 5 ms 256 KB
test_1000_3728577_-145414503_-969430020.txt AC 1 ms 256 KB
test_1000_537976_11297496_224335992.txt AC 4 ms 256 KB
test_10_227248639_454497278_0B.txt AC 1 ms 256 KB
test_11_692637325_-181424149_-938839075B.txt AC 1 ms 256 KB
test_130_95365311_-667557177_-286095933.txt WA 1 ms 256 KB
test_131_18204705_-145637640_0.txt AC 1 ms 256 KB
test_13_260236679_-780710037_-520473358B.txt AC 1 ms 256 KB
test_13_269280357_807841071_269280357B.txt AC 1 ms 256 KB
test_13_96859935_0_-581159610B.txt AC 1 ms 256 KB
test_16_40374395_-40374395_-565241530B.txt AC 1 ms 256 KB
test_1_151403858_0_0AB.txt AC 1 ms 256 KB
test_1_1_0_1AB.txt AC 1 ms 256 KB
test_1_1_2_0AB.txt AC 1 ms 256 KB
test_1_200416616_-430405070_-79858930AB.txt AC 1 ms 256 KB
test_1_320861287_0_0AB.txt AC 1 ms 256 KB
test_1_445441131_0_0AB.txt AC 1 ms 256 KB
test_210_28974130_0_260767170.txt AC 1 ms 256 KB
test_217_321156_24407856_22480920.txt AC 1 ms 256 KB
test_21_304856339_609712678_914569017B.txt AC 1 ms 256 KB
test_26_214390232_-857560928_428780464B.txt AC 1 ms 256 KB
test_289_421462830_-487186374_-417635361.txt AC 1 ms 256 KB
test_2_91743015_0_183486030AB.txt AC 1 ms 256 KB
test_30_10000000_-300000000_0B.txt AC 1 ms 256 KB
test_30_10000000_0_300000000B.txt AC 1 ms 256 KB
test_30_10000000_150000000_-150000000B.txt AC 1 ms 256 KB
test_30_54228128_0_813421920B.txt AC 1 ms 256 KB
test_339_4475128_957677392_281933064.txt AC 1 ms 256 KB
test_3_165357536_496072608_0AB.txt AC 1 ms 256 KB
test_3_357154050_-106436394_768502001AB.txt AC 1 ms 256 KB
test_3_721501125_-568833455_353553641AB.txt AC 1 ms 256 KB
test_3_893846474_0_0AB.txt AC 1 ms 256 KB
test_480_402960_-131767920_-34654560.txt AC 1 ms 256 KB
test_4_291388018_-291388018_0AB.txt AC 1 ms 256 KB
test_507_3516183_-879045750_-253165176.txt AC 1 ms 256 KB
test_515_8606048_-25818144_8606048.txt AC 1 ms 256 KB
test_522_2286376_-230923976_-18291008.txt AC 1 ms 256 KB
test_5_318547875_955643625_-637095750AB.txt AC 1 ms 256 KB
test_5_704387671_-704387671_0AB.txt AC 1 ms 256 KB
test_5_82323965_639854915_-688317394AB.txt AC 1 ms 256 KB
test_676_198114948_0_792459792.txt WA 4 ms 256 KB
test_688_151937211_-286341114_10198771.txt AC 1 ms 256 KB
test_6_187422602_374845204_-374845204AB.txt AC 1 ms 256 KB
test_6_346164451_0_0AB.txt AC 1 ms 256 KB
test_6_99058019_194123640_-837769837AB.txt AC 1 ms 256 KB
test_71_367604060_367604060_0.txt WA 1 ms 256 KB
test_752_120973200_0_-725839200.txt WA 5 ms 256 KB
test_772_881340073_0_0.txt WA 5 ms 256 KB
test_777_125719576_-499451637_822057459.txt AC 1 ms 256 KB
test_7_166330212_166330212_-332660424AB.txt AC 1 ms 256 KB
test_7_89698746_448493730_-179397492AB.txt AC 1 ms 256 KB
test_839_166155061_0_-332310122.txt AC 1 ms 256 KB
test_839_923157_923157_564972084.txt AC 2 ms 256 KB
test_849_415705_290993500_0.txt AC 1 ms 256 KB
test_873_418406_2928842_322172620.txt AC 1 ms 256 KB
test_8_10000000_-40000000_-40000000AB.txt AC 1 ms 256 KB
test_8_10000000_0_80000000AB.txt AC 1 ms 256 KB
test_8_10000000_80000000_0AB.txt AC 1 ms 256 KB
test_981_159373724_-637494896_-159373724.txt WA 8 ms 256 KB
test_9_283198156_849594468_849594468B.txt AC 1 ms 256 KB