Submission #801949

#TimeUsernameProblemLanguageResultExecution timeMemory
801949Sohsoh84Giraffes (JOI22_giraffes)C++17
10 / 100
379 ms348 KiB
// Wounds should become scars but I'm cracked instead U+1FAE0 #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<ll, ll> pll; #define all(x) (x).begin(),(x).end() #define X first #define Y second #define sep ' ' #define endl '\n' #define debug(x) cerr << #x << ": " << x << endl; const ll MAXN = 1e6 + 10; mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); int n, T[MAXN], P[MAXN], F[MAXN], ind[MAXN]; inline void rand_perm() { int l = 1, r = n; int fl = 1, fr = n; for (int i = 1; i <= n; i++) { int x = (rng() % 2 ? fr-- : fl++); int y = (rng() % 2 ? r-- : l++); T[y] = x; } } inline int distance() { for (int i = 1; i <= n; i++) ind[P[i]] = i; for (int i = 1; i <= n; i++) F[ind[T[i]]] = i; int ans = 0; for (int i = 1; i <= n; i++) if (F[i] != i) ans++; return ans; } int main() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); int fuck = 1000000; cin >> n; for (int i = 1; i <= n; i++) cin >> P[i]; int ans = n; while (fuck--) { rand_perm(); ans = min(ans, distance()); } cout << ans << endl; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...