Submission #831341

#TimeUsernameProblemLanguageResultExecution timeMemory
831341maomao90Giraffes (JOI22_giraffes)C++17
10 / 100
7023 ms340 KiB
// Hallelujah, praise the one who set me free // Hallelujah, death has lost its grip on me // You have broken every chain, There's salvation in your name // Jesus Christ, my living hope #include <bits/stdc++.h> using namespace std; #define REP(i, s, e) for (int i = (s); i < (e); i++) #define RREP(i, s, e) for (int i = (s); i >= (e); i--) template <class T> inline bool mnto(T& a, T b) {return a > b ? a = b, 1 : 0;} template <class T> inline bool mxto(T& a, T b) {return a < b ? a = b, 1: 0;} typedef unsigned long long ull; typedef long long ll; typedef long double ld; #define FI first #define SE second typedef pair<int, int> ii; typedef pair<ll, ll> pll; typedef tuple<int, int, int> iii; #define ALL(_a) _a.begin(), _a.end() #define SZ(_a) (int) _a.size() #define pb push_back typedef vector<int> vi; typedef vector<ll> vll; typedef vector<ii> vii; typedef vector<iii> viii; #ifndef DEBUG #define cerr if (0) cerr #endif const int INF = 1000000005; const ll LINF = 1000000000000000005ll; const int MAXN = 200005; int n; int p[MAXN]; int a[MAXN]; int ans; int main() { #ifndef DEBUG ios::sync_with_stdio(0), cin.tie(0); #endif cin >> n; REP (i, 0, n) { cin >> p[i]; } ans = n; iota(a, a + n, 1); do { bool bad = 0; REP (i, 0, n) { ii mn = {INF, INF}, mx = {-INF, -INF}; REP (j, i, n) { mnto(mn, {a[j], j}); mxto(mx, {a[j], j}); if (mn.SE != i && mn.SE != j && mx.SE != i && mx.SE != j) { bad = 1; break; } } if (bad) { break; } } if (bad) { continue; } int cost = 0; REP (i, 0, n) { cost += a[i] != p[i]; } mnto(ans, cost); } while (next_permutation(a, a + n)); cout << ans << '\n'; 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...