結果

問題 No.173 カードゲーム（Medium）
ユーザー motimoti
提出日時 2015-04-03 10:57:38
言語 C++11
(gcc 11.4.0)
結果
WA  
実行時間 -
コード長 905 bytes
コンパイル時間 1,068 ms
コンパイル使用メモリ 150,244 KB
実行使用メモリ 4,384 KB
最終ジャッジ日時 2023-09-17 03:59:22
合計ジャッジ時間 6,252 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 30 ms
4,380 KB
testcase_01 WA -
testcase_02 WA -
testcase_03 WA -
testcase_04 WA -
testcase_05 WA -
testcase_06 WA -
testcase_07 WA -
testcase_08 WA -
testcase_09 AC 563 ms
4,376 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>

using namespace std;

#define REP(i,a,b) for(int i=a;i<(int)b;i++)
#define rep(i,n) REP(i,0,n)

int N, T;
double pa, pb;
int A[22], B[22];
int awins, sum;

default_random_engine gene;
uniform_real_distribution<double> dist(0,1);

vector<int> getrandvec(double p) {
	int x;
	vector<int> v,r;
	rep(i, N) v.push_back(i);

	rep(i, N-1) {
		double d = dist(gene);
		if(d < p) x = 0;
		else x = 1+(N-1-i)*(d-p) / (1-p);
		r.push_back(v[x]);
		v.erase(v.begin()+x);
	}
	r.push_back(v[0]);
	return r;
}

int main() {

	cin >> N;
	rep(i, N) cin >> A[i];	sort(A, A+N);
	rep(i, N) cin >> B[i];	sort(B, B+N);

	rep(_, 300000) {
		sum++;
		vector<int> va(getrandvec(pa)), vb(getrandvec(pb));
		int ascore = 0;
		rep(i, N) {
			if(A[va[i]] <= B[vb[i]]) { continue; }
			ascore += A[va[i]] + B[vb[i]];
		}
		if(ascore > T/2) { awins++; }
	}

	printf("%.10f\n", (double)awins/sum);

	return 0;
}
0