結果

問題 No.475 最終日 - Writerの怠慢
ユーザー startcppstartcpp
提出日時 2016-12-30 16:04:02
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 46 ms / 2,000 ms
コード長 1,025 bytes
コンパイル時間 889 ms
コンパイル使用メモリ 67,036 KB
実行使用メモリ 4,960 KB
最終ジャッジ日時 2023-08-25 16:43:49
合計ジャッジ時間 2,394 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,380 KB
testcase_01 AC 2 ms
4,376 KB
testcase_02 AC 2 ms
4,380 KB
testcase_03 AC 6 ms
4,376 KB
testcase_04 AC 46 ms
4,780 KB
testcase_05 AC 43 ms
4,912 KB
testcase_06 AC 43 ms
4,960 KB
testcase_07 AC 43 ms
4,780 KB
testcase_08 AC 44 ms
4,924 KB
testcase_09 AC 45 ms
4,916 KB
testcase_10 AC 43 ms
4,808 KB
testcase_11 AC 44 ms
4,656 KB
testcase_12 AC 40 ms
4,784 KB
testcase_13 AC 40 ms
4,600 KB
testcase_14 AC 1 ms
4,376 KB
権限があれば一括ダウンロードができます

ソースコード

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