Submission

Score: 0

User: pxsit

Problemset: ร้านปลอดภาษี (Duty Free)

Language: cpp

Time: 0.000 second

Submitted On: 2026-06-01 12:16:09

#include <bits/stdc++.h>
using namespace std;

int minimum_bag_rearrangement_time(vector<int> vec) {
    int n = vec.size();
    int ans = 0;
    int timer = 1;

    // next_avail[i] stores the next free slot below or equal to i
    // lazy[i] tracks if next_avail[i] is valid for the current epoch
    vector<int> next_avail(n + 9);
    vector<int> lazy(n + 9, 0);

    for (int x : vec) {
        // Step 1: Find the actual available slot for x
        int curr = x;
        
        // Path compression / Shortcut chasing
        while (curr > 0) {
            if (lazy[curr] != timer) {
                // If it hasn't been touched this epoch, it points to itself
                lazy[curr] = timer;
                next_avail[curr] = curr;
            }
            
            if (next_avail[curr] == curr) {
                break; // Found an empty slot!
            }
            curr = next_avail[curr]; // Jump closer to the free slot
        }

        // Step 2: If we hit 0, we must reset
        if (curr == 0) {
            timer++; // O(1) Reset
            ans++;
            
            // Re-evaluate x in the fresh epoch (it will definitely be x)
            curr = x;
            lazy[curr] = timer;
            next_avail[curr] = curr;
        }

        // Step 3: Memoize/Compress the paths we traversed to make future lookups O(1)
        int update_ptr = x;
        while (update_ptr != curr) {
            if (lazy[update_ptr] != timer) {
                lazy[update_ptr] = timer;
            }
            int next_hop = next_avail[update_ptr];
            next_avail[update_ptr] = curr - 1; // Point them to the slot below our newly filled slot
            update_ptr = next_hop;
        }

        // Occupy the current slot by pointing it to the one right below it
        next_avail[curr] = curr - 1; 
    }

    return ans;
}

int main(){}