Submission #381649

#TimeUsernameProblemLanguageResultExecution timeMemory
381649AdiZer0Doktor (COCI17_doktor)C++17
100 / 100
598 ms32468 KiB
#include <bits/stdc++.h> #define pb push_back #define whole(x) x.begin(), x.end() #define sz(x) (int)x.size() using namespace std; typedef long long ll; typedef long double ld; const int N = (int)5e5 + 7; const int INF = (int)1e9 + 7; const ll linf = (ll)1e18 + 1; bool cmp(pair<int, int> a, pair<int, int> b) { return a.second - a.first + 1 < b.second - b.first + 1; } int a[N]; ll pref[N]; map<int, int> mp; int main() { int n; scanf ("%d", &n); vector<pair<int, int>> v; for (int i = 1; i <= n; ++i) { scanf ("%d", a + i); if (i == a[i]) pref[i] = 1; pref[i] += pref[i - 1]; v.pb({min(i, a[i]), max(i, a[i])}); } sort(whole(v), &cmp); int ansL = 1, ansR = 1; int ans = pref[n]; for (int i = 0; i < n; ++i) { mp[v[i].first + v[i].second]++; int cur = pref[n] - (pref[v[i].second] - pref[(v[i].first - 1)]); if (cur + mp[v[i].first + v[i].second] > ans) { ans = cur + mp[v[i].first + v[i].second]; ansL = a[v[i].first], ansR = a[v[i].second]; } } printf ("%d %d\n", ansL, ansR); return 0; }

Compilation message (stderr)

doktor.cpp: In function 'int main()':
doktor.cpp:25:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   25 |     int n; scanf ("%d", &n);
      |            ~~~~~~^~~~~~~~~~
doktor.cpp:28:15: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   28 |         scanf ("%d", a + 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...