Submission #250600

#TimeUsernameProblemLanguageResultExecution timeMemory
250600Vladikus004Doktor (COCI17_doktor)C++14
50 / 100
70 ms10204 KiB
#include <bits/stdc++.h> #define inf 2e9 #define all(v) v.begin(), v.end() using namespace std; typedef long long ll; typedef long double ld; typedef pair <int, int> pii; const int N = 500000 + 3; int n, a[N], pref[N], now[N]; int get_sum(int l, int r){ if (!l) return pref[r]; return pref[r] - pref[l - 1]; } vector <pii> v1, v2; int main() { ios_base::sync_with_stdio(false); cin.tie(0); #ifdef LOCAL freopen("input.txt", "r", stdin); #endif // LOCAL cin >> n; for (int i = 0; i < n; i++){ cin >> a[i]; --a[i]; if (a[i] == i + 1) pref[i] = 1; if (i) pref[i] += pref[i - 1]; int mid = (a[i] + i) / 2; if ((a[i] + i) & 1){ v2.push_back({abs(i - mid), mid}); }else{ v1.push_back({abs(i - mid), mid}); } } // sort(all(v1)); // sort(all(v2)); pair <int, pii> ans1 = {-inf,{-inf, -inf}}; for (int i = 0; i < v1.size(); i++){ now[v1[i].second]++; ans1 = max(ans1, {now[v1[i].second] - get_sum(v1[i].second - v1[i].first, v1[i].second + v1[i].first), v1[i]}); } fill(now, now + n, 0); pair <int, pii> ans2 = {-inf,{-inf, -inf}}; for (int i = 0; i < v2.size(); i++){ now[v2[i].second]++; ans2 = max(ans2, {now[v2[i].second] - get_sum(v2[i].second - v2[i].first + 1, v2[i].second + v2[i].first), v2[i]}); } if (ans1 > ans2){ cout << a[ans1.second.second - ans1.second.first] + 1 << " " << a[ans1.second.second + ans1.second.first] + 1 << "\n"; }else{ cout << a[ans2.second.second - ans2.second.first + 1] + 1 << " " << a[ans2.second.second + ans2 .second.first] + 1 << "\n"; } }

Compilation message (stderr)

doktor.cpp: In function 'int main()':
doktor.cpp:41:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < v1.size(); i++){
                     ~~^~~~~~~~~~~
doktor.cpp:48:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < v2.size(); i++){
                     ~~^~~~~~~~~~~
#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...