結果
問題 |
No.1478 Simple Sugoroku
|
ユーザー |
![]() |
提出日時 | 2022-02-10 01:11:29 |
言語 | C++17(clang) (17.0.6 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,048 bytes |
コンパイル時間 | 4,105 ms |
コンパイル使用メモリ | 141,040 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-06-25 05:54:57 |
合計ジャッジ時間 | 5,065 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 31 WA * 7 |
ソースコード
#include <cassert> #include <cmath> #include <algorithm> #include <iostream> #include <iomanip> #include <climits> #include <map> #include <queue> #include <set> #include <cstring> #include <vector> using namespace std; typedef long long ll; int N, M; vector<int> B; double f(int mid) { if (mid < 0) return INT_MAX; if (M <= mid) return INT_MAX; int len = M - mid; double val = 0.0; for (int i = M - 1; i >= mid; --i) { int b = B[i]; double cnt = (B[0] - 1) + M * 1.0 / len + (N - b); val += cnt; } return val / len; } int main() { cin >> N >> M; for (int i = 0; i < M; ++i) { int b; cin >> b; B.push_back(b); } int l = 0; int r = M - 1; for (int i = 0; i < 10000; ++i) { int i_1 = (l * 2 + r) / 3; int i_2 = (l + r * 2) / 3; if (f(i_1) < f(i_2)) { r = i_1; } else { l = i_2; } } int mid = (l + r) / 2; double ans = N - 1.0; ans = min(ans, f(mid - 1)); ans = min(ans, f(mid)); ans = min(ans, f(mid + 1)); cout << ans << endl; return 0; }