結果

問題 No.475 最終日 - Writerの怠慢
コンテスト
ユーザー startcpp
提出日時 2016-12-30 16:04:02
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 54 ms / 2,000 ms
コード長 1,025 bytes
コンパイル時間 820 ms
コンパイル使用メモリ 65,736 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-12-24 01:41:12
合計ジャッジ時間 2,248 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 15
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <algorithm>
#include <vector>
#include <cstdio>
#define int long long
using namespace std;

int n, s, writer_id;
int a[77777];
vector<int> nums;

int score(int id, int rank) {
	return a[id] + 50 * s + 50 * s / (0.8 + 0.2 * rank);
}

signed main() {
	int i;
	
	cin >> n >> s >> writer_id;
	for (i = 0; i < n; i++) {
		cin >> a[i];
		if (i == writer_id) { a[i] += 100 * s; }
	}
	
	for (i = 0; i < n; i++) {
		if (i == writer_id) continue;
		int st = 0, ed = n, mid;	//(st, ed], xxxooo
		while (ed - st >= 2) {
			mid = (st + ed) / 2;
			if (score(i, mid) > a[writer_id]) st = mid;
			else ed = mid;
		}
		//最上位を1位としたとき、人iはed位～n - 1位にする。下から何人にいるか？を考える。
		nums.push_back(n - ed);
	}
	sort(nums.begin(), nums.end());
	
	double ans = 1;
	for (i = 0; i < n - 1; i++) {
		int ok_num = max(0LL, nums[i] - i);
		int all_num = n - 1 - i;
		double prob = (double)ok_num / all_num;
		ans *= prob;
	}
	
	printf("%.14f\n", ans);
	return 0;
}
0