Submission #116906

#TimeUsernameProblemLanguageResultExecution timeMemory
116906nhimnam120Doktor (COCI17_doktor)C++14
0 / 100
860 ms45048 KiB
#include<bits/stdc++.h> using namespace std; int n, a[500001], pre[500001], mx, ans1, ans2; vector<int> change[500001]; vector<int> change2[500001]; signed main(){ ios_base::sync_with_stdio(0); cin >> n; for(int i = 1; i <= n; i++){ cin >> a[i]; pre[i] = pre[i - 1]; if(a[i] == i) pre[i]++; if((a[i] + i) % 2 == 0) change[(a[i] + i) / 2].push_back(abs(a[i] - i) / 2); else change2[(a[i] + i) / 2].push_back(abs(a[i] - i) / 2); } ans1 = ans2 = a[1]; for(int i = 1; i <= n; i++){ if(change[i].size()==0) continue; sort(change[i].begin(), change[i].end()); cout << i<< " "; for(auto x: change[i]){ cout << x<< " " ; } cout << endl; for(int j = change[i].size() - 1; j >= 0; j--){ if(mx < (j + 1 - pre[change[i][j] + i] + pre[i - change[i][j] - 1])){ mx = j + 1 - pre[change[i][j] + i] + pre[i - change[i][j] - 1]; ans1 = a[i - change[i][j]]; ans2 = a[i + change[i][j]]; } } } cout << endl; for(int i = 1; i < n; i++){ if(!change2[i].size()) continue; sort(change2[i].begin(), change2[i].end()); cout << i<< " "; for(auto x: change2[i]){ cout << x<< " "; } cout << endl; for(int j = change2[i].size() - 1; j >= 0; j--){ if(mx < (j + 1 - pre[change2[i][j] + i + 1] + pre[i - change2[i][j] - 1])){ mx = j + 1 - pre[change2[i][j] + i + 1] + pre[i - change2[i][j] - 1]; ans1 = a[i - change2[i][j]]; ans2 = a[i + change2[i][j] + 1]; } } } cout << ans1 << " " << ans2; }
#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...