Submission #802005

#TimeUsernameProblemLanguageResultExecution timeMemory
802005Sohsoh84Giraffes (JOI22_giraffes)C++17
32 / 100
3127 ms340 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]; bool P_val[MAXN]; inline int rand_perm() { int l = 1, r = n; int fl = 1, fr = n; int ans = n; fill(P_val, P_val + n + 5, false); for (int i = 1; i <= n; i++) { if (P[l] == fl) { ans--; l++; fl++; P_val[fl] = true; } else if (P[l] == fr) { ans--; l++; fr--; P_val[fr] = true; } else if (P[r] == fl) { ans--; r--; fl++; P_val[fl] = true; } else if (P[r] == fr) { ans--; r--; fr--; P_val[fr] = true; } else { // if (P_val[fl]) fl++; // else if (P_val[fr]) fr--; if (rng() % 2) fl++; else fr--; if (P[l] < fl || P[l] > fr) P_val[P[l]] = true, l++; else if (P[r] < fl || P[r] > fr) P_val[P[r]] = true, r--; else if (rng() % 2) P_val[P[l]] = true, l++; else P_val[P[r]] = true, r--; } } return ans; } int main() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin >> n; for (int i = 1; i <= n; i++) cin >> P[i]; int fuck = 10000000 * 13 / n; int ans = n; while (fuck--) { ans = min(ans, rand_perm()); } 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...