Submission #802051

#TimeUsernameProblemLanguageResultExecution timeMemory
802051Sohsoh84Giraffes (JOI22_giraffes)C++17
0 / 100
0 ms212 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 int rand_perm() { int l = 1, r = n; int fl = 1, fr = n; int ans = n; for (int i = 1; i <= n; i++) { if (P[l] == fl) { ans--; l++; fl++; } else if (P[l] == fr) { ans--; l++; fr--; } else if (P[r] == fl) { ans--; r--; fl++; } else if (P[r] == fr) { ans--; r--; fr--; } else { int tfl = fl; int tfr = fr; if (ind[tfl] < l || ind[tfl] > r) tfl++; else if (ind[tfr] < l || ind[tfr] > r) tfr--; else { int x = rng() % 2; if (x) tfl++; else tfr--; } if (P[l] < fl || P[l] > fr) l++; else if (P[r] < fl || P[r] > fr) r--; else if (rng() % 2) l++; else r--; fl = tfl; fr = tfr; } } 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]; ind[P[i]] = i; } int fuck = 10000000 * 13 / n; rand_perm(); return 0; 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...