Submission #549259

#TimeUsernameProblemLanguageResultExecution timeMemory
549259xdfactor2034Doktor (COCI17_doktor)C++17
0 / 100
62 ms11712 KiB
#include<bits/stdc++.h> using namespace std; const int maxn = 5e5+5; int ar[maxn], lk[maxn]; int wl[maxn], wr[maxn]; int dpl[maxn], dpr[maxn]; #define cerr while(0) cerr signed main() { #ifndef cerr freopen("a.in", "r", stdin); freopen("a.out", "w", stdout); #endif ios_base::sync_with_stdio(0); cin.tie(0); int N; cin >> N; for(int i = 1; i <= N; i++) cin >> ar[i], lk[ar[i]] = i; for(int i = 1; i <= N; i++) { int score = i - ar[i]; if(score >= 0) wl[i] = score, wr[i] = -1; else wl[i] = -1, wr[i] = -score; } for(int i = 1; i <= N; i++) cerr << "w " << wl[i] << ' ' << wr[i] << '\n'; int glob = 0; for(int i = 1; i <= N; i++) if(ar[i] == i) glob++; for(int i = 1; i <= N; i++) dpl[i] = (wl[i-1] + 2 == wl[i]) ? dpl[i-1]+1 : 1; for(int i = N; i >= 1; i--) dpr[i] = (wr[i+1] + 2 == wl[i]) ? dpr[i+1]+1 : 1; for(int i = 1; i <= N; i++) cerr << dpl[i] << ' ' << dpr[i] << '\n'; int bg = 1; int res = 0; int a = -1, b = -1; for(int i = 1; i <= N; i++) { if(dpl[i] >= dpl[i+1]) { int old = 0; int first = bg - (i - bg); assert(first >= 1); for(int j = first; j <= i; j++) if(ar[j] == j) old++; glob -= old; reverse(ar+first, ar+i+1); int next = 0; for(int j = first; j <= i; j++) if(ar[j] == j) next++; if(glob + next > res) res = glob+next, a = first, b = i; glob += old; bg = i+1; reverse(ar+first, ar+i+1); } } int en = N; for(int i = N; i >= 1; i--) { if(dpr[i] >= dpr[i-1]) { int old = 0; int last = en+(en-i); assert(last <= N); for(int j = i; j <= last; j++) if(ar[j] == j) old++; glob -= old; reverse(ar+i, ar+last+1); int next = 0; for(int j = i; j <= last; j++) if(ar[j] == j) next++; if(glob + next > res) res = glob+next, a = i, b = last; glob += old; en = i-1; reverse(ar+i, ar+last+1); } } cerr << glob << '\n'; cout << ar[a] << ' ' << ar[b] << '\n'; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...