#142166 (C++11) No.475 最終日 - Writerの怠慢

• 問題: No.475 最終日 - Writerの怠慢
• ユーザー: startcpp
• 提出日時: 2016-12-30 16:04:02
• 言語: C++11 (gcc 11.4.0)
• 結果: AC
• 実行時間: 48 ms / 2,000 ms
• コード長: 1,025 bytes
• コンパイル時間: 803 ms
• コンパイル使用メモリ: 66,512 KB
• 実行使用メモリ: 5,376 KB
• 最終ジャッジ日時: 2024-06-06 10:48:02
• 合計ジャッジ時間: 2,008 ms
• ジャッジサーバーID （参考情報）: judge5 / judge1

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	1 ms; 5,248 KB
testcase_01	AC	2 ms; 5,376 KB
testcase_02	AC	2 ms; 5,376 KB
testcase_03	AC	6 ms; 5,376 KB
testcase_04	AC	47 ms; 5,376 KB
testcase_05	AC	47 ms; 5,376 KB
testcase_06	AC	45 ms; 5,376 KB
testcase_07	AC	46 ms; 5,376 KB
testcase_08	AC	47 ms; 5,376 KB
testcase_09	AC	48 ms; 5,376 KB
testcase_10	AC	47 ms; 5,376 KB
testcase_11	AC	46 ms; 5,376 KB
testcase_12	AC	41 ms; 5,376 KB
testcase_13	AC	46 ms; 5,376 KB
testcase_14	AC	2 ms; 5,376 KB

ソースコード

#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;
}