結果
| 問題 |
No.484 収穫
|
| コンテスト | |
| ユーザー |
 qwewe
|
| 提出日時 | 2025-05-14 13:11:00 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 9,005 bytes |
| コンパイル時間 | 1,011 ms |
| コンパイル使用メモリ | 92,608 KB |
| 実行使用メモリ | 6,272 KB |
| 最終ジャッジ日時 | 2025-05-14 13:12:52 |
| 合計ジャッジ時間 | 2,848 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 WA * 1 |
| other | AC * 12 WA * 9 |
ソースコード
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath> // Include for abs
using namespace std;
// Define long long type for potentially large times
typedef long long ll;
// Check function determines if it's possible to harvest all fruits by time T.
// It checks four types of paths for each possible starting cell s:
// 1. Start at s, go to cell 1, then sweep linearly to cell N.
// 2. Start at s, go to cell N, then sweep linearly to cell 1.
// 3. Start at s, go to cell 1, sweep to N, then sweep back to 1.
// 4. Start at s, go to cell N, sweep to 1, then sweep back to N.
// The function incorporates waiting times: if arriving at cell i at time t_arrive < A[i-1],
// the agent must wait until A[i-1]. The time recorded is the finish time at cell i.
bool check(ll T, int N, const vector<ll>& A) {
// Basic check: If any fruit ripens after time T, it's impossible.
for (int i = 0; i < N; ++i) {
if (A[i] > T) {
return false;
}
}
// Special case: If there's only one cell.
if (N == 1) {
// The time needed is simply the ripening time of the single fruit.
return A[0] <= T;
}
// Iterate through all possible starting cells s (from 1 to N).
for (int s = 1; s <= N; ++s) {
// Check path type 1: s -> ... -> 1 -> ... -> N
// Calculate time to reach cell 1 from start s.
ll time_to_reach_1 = (ll)abs(s - 1);
// Calculate the time when harvest at cell 1 finishes. Max of arrival time and ripening time.
ll finish_time_at_1 = max(time_to_reach_1, A[0]);
bool possible_1N = true;
// If finishing at cell 1 already exceeds T, this path is impossible.
if (finish_time_at_1 > T) {
possible_1N = false;
} else {
ll prev_finish_time = finish_time_at_1;
// Calculate finish times for cells 2 to N.
for (int i = 2; i <= N; ++i) {
// Arrive at cell i at time prev_finish_time + 1.
// Finish harvest at cell i at time max(arrival_time, A[i-1]).
ll current_finish_time = max(prev_finish_time + 1, A[i - 1]);
// If finish time exceeds T, impossible.
if (current_finish_time > T) {
possible_1N = false;
break;
}
prev_finish_time = current_finish_time;
}
// If the loop completed, prev_finish_time holds the finish time at cell N. Check if it's <= T.
if (possible_1N && prev_finish_time <= T) {
return true; // This path type works for starting cell s.
}
// Need to reset possible_1N flag check based on final time condition.
if (possible_1N && prev_finish_time > T) {
possible_1N = false; // Final check, although inner loop checks this too
}
}
// Check path type 2: s -> ... -> N -> ... -> 1
// Similar logic as path type 1, but sweeping from N to 1.
ll time_to_reach_N = (ll)abs(s - N);
ll finish_time_at_N = max(time_to_reach_N, A[N - 1]);
bool possible_N1 = true;
if (finish_time_at_N > T) {
possible_N1 = false;
} else {
ll prev_finish_time = finish_time_at_N;
for (int i = N - 1; i >= 1; --i) {
ll current_finish_time = max(prev_finish_time + 1, A[i - 1]);
if (current_finish_time > T) {
possible_N1 = false;
break;
}
prev_finish_time = current_finish_time;
}
if (possible_N1 && prev_finish_time <= T) {
return true; // This path type works.
}
if (possible_N1 && prev_finish_time > T) {
possible_N1 = false;
}
}
// Check path type 3: s -> ... -> 1 -> ... -> N -> ... -> 1 (Two sweeps)
vector<ll> T_F(N + 1); // Stores finish time at cell i during forward sweep (1 to N)
ll time_to_reach_1_sweep1 = (ll)abs(s - 1);
T_F[1] = max(time_to_reach_1_sweep1, A[0]);
bool possible_1N_sweep = true;
if (T_F[1] > T) {
possible_1N_sweep = false;
} else {
// Calculate finish times for forward sweep (1 to N).
for (int i = 2; i <= N; ++i) {
T_F[i] = max(T_F[i-1] + 1, A[i-1]);
if (T_F[i] > T) {
possible_1N_sweep = false;
break;
}
}
}
// If the first sweep (1 to N) is possible within time T:
if (possible_1N_sweep) {
// Start backward sweep (N to 1) from cell N. Finish time at N is T_F[N].
ll prev_finish_time_B = T_F[N];
bool possible_N1_sweep = true;
// Calculate finish times for backward sweep (N to 1).
for (int i = N - 1; i >= 1; --i) {
ll current_finish_time_B = max(prev_finish_time_B + 1, A[i - 1]);
if (current_finish_time_B > T) {
possible_N1_sweep = false;
break;
}
prev_finish_time_B = current_finish_time_B;
}
// If the second sweep completed within time T:
if (possible_N1_sweep) {
// The final time is the finish time at cell 1 (end of second sweep).
if (prev_finish_time_B <= T) return true; // This path type works.
}
}
// Check path type 4: s -> ... -> N -> ... -> 1 -> ... -> N (Two sweeps)
vector<ll> T_B2(N + 1); // Stores finish time at cell i during backward sweep first (N to 1)
ll time_to_reach_N_first = (ll)abs(s - N);
T_B2[N] = max(time_to_reach_N_first, A[N-1]);
bool possible_N1_sweep2 = true;
if (T_B2[N] > T) {
possible_N1_sweep2 = false;
} else {
// Calculate finish times for first sweep (N to 1).
for (int i = N - 1; i >= 1; --i) {
T_B2[i] = max(T_B2[i + 1] + 1, A[i - 1]);
if (T_B2[i] > T) {
possible_N1_sweep2 = false;
break;
}
}
}
// If the first sweep (N to 1) is possible within time T:
if(possible_N1_sweep2){
// Start forward sweep (1 to N) from cell 1. Finish time at 1 is T_B2[1].
ll prev_finish_time_F2 = T_B2[1];
bool possible_1N_sweep2 = true;
// Calculate finish times for second sweep (1 to N).
for (int i = 2; i <= N; ++i) {
ll current_finish_time_F2 = max(prev_finish_time_F2 + 1, A[i - 1]);
if (current_finish_time_F2 > T) {
possible_1N_sweep2 = false;
break;
}
prev_finish_time_F2 = current_finish_time_F2;
}
// If the second sweep completed within time T:
if (possible_1N_sweep2) {
// The final time is the finish time at cell N (end of second sweep).
if (prev_finish_time_F2 <= T) return true; // This path type works.
}
}
}
// If none of the checked path types work for any starting cell s, return false.
return false;
}
int main() {
// Faster I/O operations
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int N; // Number of cells
cin >> N;
vector<ll> A(N); // Ripening times for each cell
ll max_A = 0; // Keep track of the maximum ripening time
for (int i = 0; i < N; ++i) {
cin >> A[i];
max_A = max(max_A, A[i]);
}
// Binary search for the minimum time T.
// The lowest possible time is the maximum ripening time.
ll low = max_A;
// A safe upper bound: max ripening time + generous travel time.
// Travel time can be at most related to N sweeps, maybe O(N^2) or O(N).
// Using max_A + 2*N*N as a very safe upper bound estimate. Add a small constant buffer.
ll high = max_A + 2LL * N * N + 5;
ll ans = high; // Initialize answer to the upper bound
// Standard binary search loop
while (low <= high) {
// Calculate midpoint carefully to avoid overflow
ll mid = low + (high - low) / 2;
// Check if it's possible to finish by time 'mid'
if (check(mid, N, A)) {
// If possible, 'mid' is a potential answer. Try smaller times.
ans = mid;
high = mid - 1;
} else {
// If not possible, need more time. Increase lower bound.
low = mid + 1;
}
}
// Output the minimum time found.
cout << ans << endl;
return 0;
}