Submission

Score: 100

User: Dormon

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

Language: cpp

Time: 0.475 second

Submitted On: 2025-06-22 21:52:55

#include <bits/stdc++.h>
#include "duty_free.h"

using namespace std;

int fp(int n, vector<int> &pa, vector<int> &lvl, int last, int i){
  if(lvl[n] <= last) {
    lvl[n] = i;
    pa[n] = n;
  }
  if(pa[n] == n) return n;
  return pa[n] = fp(pa[n], pa, lvl, last, i);
}

int minimum_bag_rearrangement_time(vector<int> max_allowed_positions){
  vector<int> vc = max_allowed_positions, pa(vc.size() + 1, 0), lvl(vc.size() + 1, -1);
  int n = vc.size(), ans = 0, last = -1;
  iota(pa.begin(), pa.end(), 0);
  vc.insert(vc.begin(), 0);
  for(int i = 1; i <= n; ++i){
    int x = fp(vc[i], pa, lvl, last, i);
    if(x == 0) ans++, last = i - 1, x = fp(vc[i], pa, lvl, last, i);
    pa[x] = fp(x - 1, pa, lvl, last, i);
  }
  return ans;
}