Submission #801993

#TimeUsernameProblemLanguageResultExecution timeMemory
801993fatemetmhrGiraffes (JOI22_giraffes)C++17
32 / 100
10 ms360 KiB
// Be name khode // #include <bits/stdc++.h> using namespace std; mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); typedef long long ll; typedef long double ld; #define all(x) x.begin(), x.end() #define mp make_pair #define pb push_back #define fi first #define se second const int maxn5 = 8e3 + 5; int a[maxn5], ind[maxn5]; bool rem[maxn5]; int main(){ ios_base::sync_with_stdio(false); cin.tie(0); int n; cin >> n; for(int i = 0; i < n; i++){ cin >> a[i]; a[i]--; ind[a[i]] = i; } int tt = 10000; int ans = n; while(tt-- && ans){ int l = 0, r = n - 1; int ptl = 0, ptr = n - 1; int cur = 0; memset(rem, false, sizeof rem); for(int x = 0; x < n; x++){ if(ind[ptl] == l && !rem[l]){ ptl++; l++; continue; } if(ind[ptl] == r && !rem[r]){ ptl++; r--; continue; } if(ind[ptr] == l && !rem[l]){ ptr--; l++; continue; } if(ind[ptr] == r && !rem[r]){ ptr--; r--; continue; } int ty1 = rng() % 2, ty2 = rng() % 2; //cout << "in " << tt << ' ' << ptl << ' ' << ptr << ' ' << l << ' ' << r << ' ' << ty1 << ' ' << ty2 << endl; if(ty1){ if(!rem[ind[ptl]]) cur++; rem[ind[ptl]] = true; ptl++; } else{ if(!rem[ind[ptr]]) cur++; rem[ind[ptr]] = true; ptr--; } if(ty2){ if(!rem[l]) cur++; rem[l] = true; l++; } else{ if(!rem[r]) cur++; rem[r] = true; r--; } } ans = min(ans, cur); } cout << ans << endl; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...