Untitled

mail@pastecode.io avatar
unknown
plain_text
a year ago
2.3 kB
1
Indexable
#include <iostream>
#include <algorithm>
#include <cmath>
#include <set>
#include <map>
#include "assert.h"
#include <vector>

using namespace std;

#define ll long long

const int N = 600010;
const ll INF = 1e18;
const int it = 200;
const int MOD = 998244353;
const int S = 330;


#define ll long long
#define pb push_back
#define pii pair<int, int>
#define vi vector <int>

const int LOG = 17;

int n;
vector <int> a;
vector <vector<int> > g;
vector <int> ans;

void solveSmall() {
    vector <int> nxt(n);
    for (int x = 0; x < n; x++) {
        int mx = (int)g[x].size();
        for (int i = 0; i < mx; i++) {
            int p = g[x][i];
            nxt[p] = (g[x][(i + 1) % mx] - 1 + n) % n;
        }
    }
    vector <int> to(n);
    for (int i = 0; i < n; i++) to[i] = i - 1;
    for (int k = 1; k <= min(n, S); k++) {
        for (int i = 0; i < n; i++) {
            to[i] = nxt[(to[i] + 1) % n]; //change
        }
        vector<vector<pii>> jump;
        jump.resize(LOG);
        for (int i = 0; i < LOG; i++) jump[i].resize(n);
        for (int i = 0; i < n; i++) {
            jump[0][i] = {to[i], (n + to[i] - i) % n};
        }
        for (int L = 1; L < LOG; L++) {
            for (int i = 0; i < n; i++) {
                int jump1 = (jump[L - 1][i] + 1) % n;
                jump[L][i].first = jump[L - 1][jump1];
                jump[L][i].second = jump[L - 1][i].second + jump[L - 1][jump1].second;
            }
        }
        for (int i = 0; i < n; i++) {
            int p = i;
            int steps = 0;
            int res = 0;
            for (int L = LOG - 1; L >= 0; L--) {
                if (steps + jump[L][p].second < n) {
                    steps += jump[L][p].second;
                    res += 1 << L;
                }
            }
            ans[k] = min(ans[k], res);
        }
    }
    
}

void solve() {
    cin >> n;
    a.resize(n);
    g.resize(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        a[i]--;
    }
    ans.resize(n + 1, n);
    for (int i = 0; i < n; i++) g[a[i]].pb(i);
    pt.resize(n);
}

int main()
{
    int T;
    T = 1;
    //cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}