結果
| 問題 | No.1748 Parking Lot |
| ユーザー |
 qwewe
|
| 提出日時 | 2025-05-14 13:19:15 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
MLE
|
| 実行時間 | - |
| コード長 | 7,690 bytes |
| コンパイル時間 | 1,250 ms |
| コンパイル使用メモリ | 117,744 KB |
| 実行使用メモリ | 620,196 KB |
| 最終ジャッジ日時 | 2025-05-14 13:20:02 |
| 合計ジャッジ時間 | 5,145 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | AC * 8 MLE * 1 -- * 13 |
ソースコード
#include <iostream>
#include <vector>
#include <cmath>
#include <set> // Used for storing intervals with the same priority, ordered by L
#include <map> // Used to map priorities to sets of intervals
#include <tuple> // Used for storing interval data and within the set
#include <algorithm> // Used for min function
#include <vector> // Used temporarily to store intervals being processed in a batch
using namespace std;
// Use long long for coordinates and counts as N can be up to 10^9
typedef long long ll;
// The map will store intervals grouped by priority.
// The key is the priority: pair<ll, ll> representing (Comfort, -Spot).
// We use -Spot because map orders keys ascendingly, and we want max Comfort, then min Spot (max -Spot).
// The value is a set of tuples representing intervals: set<tuple<ll, ll, ll, ll>>.
// Each tuple stores (L, R, y_L, y_R): interval boundaries and nearest occupied spots.
// The set orders tuples lexicographically, effectively sorting intervals by L, then R, etc.
// This ensures that among intervals with the same priority, we process the one with the smallest L first.
map<pair<ll, ll>, set<tuple<ll, ll, ll, ll>>> interval_map;
ll N; // Make N global so it's accessible in add_interval function
// Helper function to add an interval to the map structure
void add_interval(ll L, ll R, ll y_L, ll y_R) {
// If the interval is empty (L > R), do nothing
if (L > R) return;
ll C, P; // Comfort level C, chosen Spot P for this interval type
// Determine Comfort level C and preferred Spot P based on boundary types
// Case 1: Interval is bounded by the conceptual boundary 0 on the left
if (y_L == 0) {
// In this case, the nearest occupied spot to the left doesn't exist.
// The comfort level is determined by the distance to the right neighbor y_R.
// The spot maximizing comfort is the one furthest from y_R, which is L.
C = y_R - L; // Comfort is distance from L to y_R
P = L; // Spot maximizing comfort is L
}
// Case 2: Interval is bounded by the conceptual boundary N+1 on the right
else if (y_R == N + 1) {
// Similar to Case 1, nearest occupied spot to the right doesn't exist.
// Comfort determined by distance to left neighbor y_L.
// Spot maximizing comfort is furthest from y_L, which is R.
C = R - y_L; // Comfort is distance from R to y_L
P = R; // Spot maximizing comfort is R
}
// Case 3: Interval is bounded by two occupied spots y_L and y_R
else {
ll G = y_R - y_L; // Gap size between the two occupied spots
C = G / 2; // Max comfort is half the gap size (integer division = floor)
// The spot P achieving maximum comfort is the midpoint between y_L and y_R.
// P = floor((y_L + y_R) / 2). This can be calculated as y_L + floor(G/2).
P = y_L + G / 2;
}
// Insert the interval information into the map.
// The key is the priority pair (C, -P).
// The value set stores the tuple (L, R, y_L, y_R).
interval_map[{C, -P}].insert({L, R, y_L, y_R});
}
int main() {
// Faster I/O operations
ios_base::sync_with_stdio(false);
cin.tie(NULL);
ll K; // K is the spot where the first car parks
cin >> N >> K;
// Handle edge case N=1. The only car parks at K (which must be 1).
if (N == 1) {
cout << K << endl;
return 0;
}
// Initial state: Add intervals created by the first car parking at K.
// The conceptual boundaries 0 and N+1 are used initially.
add_interval(1, K - 1, 0, K); // Interval to the left of K, bounded by 0 and K
add_interval(K + 1, N, K, N + 1); // Interval to the right of K, bounded by K and N+1
ll last_parked_spot = K; // The first car parked at K
ll cars_parked = 1; // Count of cars parked so far
// Main loop: Simulate parking cars one by one (or in batches) until N cars are parked
while (cars_parked < N) {
// If the map is empty, it implies no more available spots, loop should terminate.
// This check prevents errors if N cars somehow park earlier than expected.
if (interval_map.empty()) break;
// Find the highest priority group of intervals. `rbegin()` gives an iterator to the last element (max key).
auto it = interval_map.rbegin();
pair<ll, ll> current_priority = it->first; // The highest priority (C, -P)
// Get a reference to the set of intervals associated with this priority.
// Use a const reference since we initially just need its size.
const set<tuple<ll, ll, ll, ll>>& current_intervals_set = it->second;
// Determine how many cars can be parked in this batch.
ll k = current_intervals_set.size(); // Number of intervals available with this top priority
// We need to park N - cars_parked more cars. We can park at most k in this batch.
ll num_park = min(N - cars_parked, k);
// Collect the data of intervals to be processed in this batch.
// We need to take the first `num_park` intervals from the set, which are ordered by L.
vector<tuple<ll, ll, ll, ll>> parked_intervals_data;
parked_intervals_data.reserve(num_park); // Optimize memory allocation
// To modify the set (erase elements), we need a mutable reference.
// `at()` provides this reference. If key not found, throws exception (shouldn't happen here).
auto& mutable_intervals_set = interval_map.at(current_priority);
auto interval_it = mutable_intervals_set.begin(); // Iterator to the first element (smallest L)
// Extract and erase the first `num_park` intervals
for (int i = 0; i < num_park; ++i) {
// Safety check: ensure iterator is valid before dereferencing/erasing
if(interval_it == mutable_intervals_set.end()) break;
parked_intervals_data.push_back(*interval_it); // Store interval data
// Erase the element pointed to by iterator. `erase` returns iterator to the next element.
interval_it = mutable_intervals_set.erase(interval_it);
}
// If the set for this priority became empty after removals, remove the priority key from the map.
if (mutable_intervals_set.empty()) {
interval_map.erase(current_priority);
}
// Process each interval selected for parking in this batch
for (const auto& parked_tuple : parked_intervals_data) {
ll L, R, y_L, y_R;
tie(L, R, y_L, y_R) = parked_tuple; // Extract interval details
// The spot P is determined by the priority key. Retrieve it by negating the second element.
ll P = -current_priority.second;
// Update the last parked spot. Since we process intervals potentially in batches,
// this variable will hold the spot of the last car parked in the final iteration.
last_parked_spot = P;
// Add new intervals potentially created by parking at spot P.
// The original interval [L, R] is split into [L, P-1] and [P+1, R].
// New left interval: [L, P-1], bounded by original y_L and the newly parked P
add_interval(L, P - 1, y_L, P);
// New right interval: [P+1, R], bounded by newly parked P and original y_R
add_interval(P + 1, R, P, y_R);
}
// Update the total count of parked cars
cars_parked += num_park;
}
// Output the spot where the N-th car parked
cout << last_parked_spot << endl;
return 0;
}