Submission

Score: 79

User: kungarooo

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

Language: cpp

Time: 1.085 second

Submitted On: 2025-11-01 23:17:22

#include <bits/stdc++.h>
using namespace std;
// you can write more function here
set<int> eridx;
int own[2000001]={};//to where
int par(int idx){
    if(own[idx]==idx)return idx;
    own[idx]=par(own[idx]);
    return own[idx];
}
void reset(){
  for(auto i:eridx){
    own[i]=i;
  }
  eridx.clear();
}
int minimum_bag_rearrangement_time(vector<int> max_allowed_positions) {
  int sz=max_allowed_positions.size(),ans=0;
  for(int i=0;i<=sz;i++){
    own[i]=i;
  }
  for(int i=0;i<sz;i++){
    int u=max_allowed_positions[i];
    par(u);
    if(own[u]==0){
      //cout<<i<<":\n";
      ans++;
      reset();
    }
    eridx.insert(own[u]);
    own[own[u]]=par(own[u]-1);
  }
  return ans;
}