oj.uz

Submission #154524

# Submission time Handle Problem Language Result Execution time Memory
154524 2019-09-22T13:08:21 Z phillip Doktor (COCI17_doktor) C++14
100 / 100
 495 ms 45972 KB 
#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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 23800 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 23800 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 23800 KB Output is correct
2 Correct 29 ms 23848 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 23972 KB Output is correct
2 Correct 27 ms 23900 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 23900 KB Output is correct
2 Correct 26 ms 23928 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 23908 KB Output is correct
2 Correct 24 ms 23800 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 24184 KB Output is correct
2 Correct 229 ms 30308 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 27144 KB Output is correct
2 Correct 88 ms 25940 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 495 ms 42344 KB Output is correct
2 Correct 367 ms 33328 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 275 ms 34652 KB Output is correct
2 Correct 335 ms 45972 KB Output is correct