Submission #374370

#TimeUsernameProblemLanguageResultExecution timeMemory
374370Atill83Doktor (COCI17_doktor)C++14
100 / 100
250 ms46060 KiB
#include <bits/stdc++.h> #define ff first #define ss second #define endl '\n' using namespace std; const long long INF = (long long) 1e18; const int mod = (int) 1e9+7; const int MAXN = (int) 5e5+5; typedef long long ll; typedef unsigned long long ull; typedef pair<int,int> pii; typedef pair<ll,ll> pll; ll n; int a[MAXN]; vector<int> deg[2*MAXN]; int pre[MAXN]; int main(){ ios_base::sync_with_stdio(false); cin.tie(nullptr);cout.tie(nullptr); #ifdef Local freopen("C:/Users/Admin/Desktop/Yazilim/C/IO/int.txt","r",stdin); freopen("C:/Users/Admin/Desktop/Yazilim/C/IO/out.txt","w",stdout); #endif cin>>n; for(int i = 1; i <= n; i++){ cin>>a[i]; deg[i + a[i]].push_back(i); pre[i] = pre[i - 1] + (a[i] == i); } pii ans; int mx = -1; for(int i = 1; i <= n; i++){ int l = i, r = a[i]; if(r < l) swap(l, r); int df = (upper_bound(deg[l + r].begin(), deg[l + r].end(), r) - lower_bound(deg[l + r].begin(), deg[l + r].end(), l)) - (pre[r] - pre[l - 1]); if((r - l + 1) % 2){ if(a[(r + l) / 2] == (r + l) / 2) df++; } if(df > mx){ ans = {l, r}; mx = df; } } cout<<a[ans.ff]<<" "<<a[ans.ss]<<endl; #ifdef Local cout<<endl<<fixed<<setprecision(2)<<1000.0 * clock() / CLOCKS_PER_SEC<< " milliseconds "; #endif }
#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...