Submission

Score: 100

User: exoworldgd

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

Language: cpp

Time: 0.293 second

Submitted On: 2025-11-09 00:15:16

#pragma GCC optimize("O5,unroll-loops,inline")
#pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt")
#include "duty_free.h"
#include <bits/stdc++.h>
#define exoworldgd cin.tie(0)->sync_with_stdio(0),cout.tie(0)
using namespace std;
int par[2000005];
int find(int x) {return par[x] == x ? x : par[x] = find(par[x]);}
void unite(int x, int y) {
    x = find(x), y = find(y);
    par[x] = min(x,y), par[y] = par[x];
}
int minimum_bag_rearrangement_time(vector<int> a) {
    int n = a.size(), ans=0;
    vector<int> v;
    bool yes[n+2]={};
    iota(par,par+n+1,0);
    for (int i : a) {
        if (!yes[i]) {
            yes[i] = 1, v.push_back(i);
            if (yes[i-1]) unite(i-1,i);
            if (yes[i+1]) unite(i+1,i);
        } else {
        	int j = find(i)-1;
            if (j > 0) {
                yes[j] = 1, v.push_back(j);
                if (yes[j-1]) unite(j-1,j);
                if (yes[j+1]) unite(j+1,j);
            } else {
                ans++;
                for (int k : v) yes[k] = 0, par[k] = k;
                v.clear(), yes[i] = 1, v.push_back(i);
            }
        }
    }
    return ans;
}