Submission #154524

#	Time	Username	Problem	Language	Result	Execution time	Memory
154524		phillip	Doktor (COCI17_doktor)	C++14	100 / 100	495 ms	45972 KiB

doktor

#include <bits/stdc++.h>
#define N 500009
using namespace std;
int n;
int prs[N],a[N];
vector<int>rs[2*N];
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=1;i<=n;i++)
    {
        prs[i]+=prs[i-1];
        if(i==a[i])prs[i]++;
    }
    for(int i=1;i<=n;i++)
    {
        rs[i+a[i]].push_back(abs(a[i]-i));
    }
    for(int i=2;i<=2*n;i++)sort(rs[i].begin(),rs[i].end());
    int mx=-N,ml=1,mr=1;
    for(int i=2;i<=2*n;i++)
    {
        int o=0;
        for(int j=0;j<rs[i].size();j++)
        {
            o++;
            int c=i,rad=rs[i][j],ans;
            int l=(c-rad)/2,r=(c+rad)/2;
            ans=o-prs[r]+prs[l-1];
            if(ans>=mx)
            {
                mx=ans;
                ml=l;
                mr=r;
            }
        }
    }
    cout<<a[ml]<<" "<<a[mr];
}

Compilation message (stderr)

doktor.cpp: In function 'int main()':
doktor.cpp:25:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j=0;j<rs[i].size();j++)
                     ~^~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 10 / 10
• Subtask 10: 10 / 10