結果

問題 No.173 カードゲーム（Medium）
ユーザー kotatsugamekotatsugame
提出日時 2020-03-04 13:27:05
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 1,545 ms / 3,000 ms
コード長 1,044 bytes
コンパイル時間 1,044 ms
コンパイル使用メモリ 100,676 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-10-14 00:11:17
合計ジャッジ時間 10,335 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 49 ms
5,248 KB
testcase_01 AC 159 ms
5,248 KB
testcase_02 AC 1,236 ms
5,248 KB
testcase_03 AC 1,232 ms
5,248 KB
testcase_04 AC 1,198 ms
5,248 KB
testcase_05 AC 990 ms
5,248 KB
testcase_06 AC 793 ms
5,248 KB
testcase_07 AC 692 ms
5,248 KB
testcase_08 AC 684 ms
5,248 KB
testcase_09 AC 1,545 ms
5,248 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp:9:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
    9 | main()
      | ^~~~

ソースコード

diff # 

#include<iostream>
#include<random>
#include<vector>
#include<algorithm>
#include<iomanip>
using namespace std;
int N;
int PA,PB;
main()
{
	cin>>N;
	double pa,pb;
	cin>>pa>>pb;
	PA=pa*1e6;
	PB=pb*1e6;
	vector<int>A(N),B(N);
	for(int&a:A)cin>>a;
	for(int&b:B)cin>>b;
	sort(A.begin(),A.end());
	sort(B.begin(),B.end());
	mt19937 rng(114514);
	int wc=0;
	const int TM=1e6;
	for(int c=0;c<TM;c++)
	{
		vector<int>a=A,b=B;
		int as=0,bs=0;
		for(int i=0;i<N;i++)
		{
			if(i+1==N)
			{
				if(a[0]<b[0])bs+=a[0]+b[0];
				else as+=a[0]+b[0];
			}
			else
			{
				int A,B;
				int at=rng()%TM;
				if(at<PA)
				{
					A=a[0];
					a.erase(a.begin());
				}
				else
				{
					int id=rng()%(N-i-1)+1;
					A=a[id];
					a.erase(a.begin()+id);
				}
				int bt=rng()%TM;
				if(bt<PB)
				{
					B=b[0];
					b.erase(b.begin());
				}
				else
				{
					int id=rng()%(N-i-1)+1;
					B=b[id];
					b.erase(b.begin()+id);
				}
				if(A<B)bs+=A+B;
				else as+=A+B;
			}
		}
		if(as>bs)wc++;
	}
	cout<<fixed<<setprecision(16)<<wc/(double)TM<<endl;
}
0