#1084102 (C++17) No.1748 Parking Lot

• 問題: No.1748 Parking Lot
• ユーザー: qwewe
• 提出日時: 2025-05-14 13:19:15
• 言語: C++17 (gcc 13.3.0 + boost 1.89.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;
}