Untitled
unknown
plain_text
a year ago
2.3 kB
1
Indexable
Never
#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; }