結果

問題 No.173 カードゲーム（Medium）
コンテスト
ユーザー masa
提出日時 2015-03-27 00:15:04
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 1,618 ms / 3,000 ms
コード長 1,173 bytes
コンパイル時間 695 ms
コンパイル使用メモリ 79,784 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-06-29 01:13:40
合計ジャッジ時間 11,733 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 10
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <utility>
#include <random>
#include <cstdlib>

const int MAX_GAME = 1e6;

using namespace std;


int choice(int nn, int p) {
	if (nn == 1) {
		return 0;
	}

	if (rand() % 1000 < p) {
		return 0;
	}

	return rand() % (nn - 1) + 1;
}

int main() {
	int n, pa, pb;
	double pad, pbd;

	cin >> n >> pad >> pbd;

	pa = pad * 1000;
	pb = pbd * 1000;

	vector<int> a(n, 0), b(n, 0);
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}
	for (int i = 0; i < n; i++) {
		cin >> b[i];
	}

	sort(a.begin(), a.end());
	sort(b.begin(), b.end());

	srand(0);

	int point;
	int idx_a, idx_b, num_a, num_b;
	int win_a = 0, win_b = 0;

	for (int i = 0; i < MAX_GAME; i++) {
		auto aa = a, bb = b;
		point = 0;
		for (int j = n; j > 0; j--) {
			idx_a = choice(j, pa);
			idx_b = choice(j, pb);


			num_a = aa[idx_a];
			num_b = bb[idx_b];

			aa.erase(aa.begin() + idx_a);
			bb.erase(bb.begin() + idx_b);

			point +=  (num_a > num_b) ? num_a + num_b : -(num_a + num_b);
		}
		if (point > 0) {
			win_a++;
		} else if (point > 0) {
			win_b++;
		}
	}

	printf("%f\n", 1.0 * win_a / MAX_GAME);
	return 0;
}
0