oj.uz

Submission #92926

# Submission time Handle Problem Language Result Execution time Memory
92926 2019-01-05T20:19:37 Z vex Doktor (COCI17_doktor) C++14
100 / 100
 210 ms 45928 KB 
#include <bits/stdc++.h>
#define maxn 500005
using namespace std;

int n;
int niz[maxn];
vector<int>a[2*maxn];
int l[maxn];

int fix(int levo,int desno)
{
    return l[desno]-l[levo-1];
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    cin>>n;
    l[0]=0;
    for(int i=1;i<=n;i++)
    {
        int x;
        cin>>x;
        a[x+i].push_back(abs(x-i));

        l[i]=l[i-1];
        if(x==i)l[i]++;

        niz[i]=x;
    }

    int sol=l[n];
    int levo=1;
    int desno=1;
    for(int i=1;i<=2*n;i++)
    {
        sort(a[i].begin(),a[i].end());
        int len=a[i].size();

        for(int j=0;j<len;j++)
        {
            int left=(i-a[i][j])/2;
            int right=(i+a[i][j])/2;
            int tre=j+1+l[left-1]+fix(right+1,n);
            if(tre>sol)
            {
                sol=tre;
                levo=left;
                desno=right;
            }
        }
    }

    cout<<niz[levo]<<" "<<niz[desno]<<endl;
    return 0;
}

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 23800 KB Output is correct
2 Correct 22 ms 23920 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 23928 KB Output is correct
2 Correct 22 ms 23928 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 24056 KB Output is correct
2 Correct 24 ms 23928 KB Output is correct

Subtask #6
10.0 / 10.0

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

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 24184 KB Output is correct
2 Correct 84 ms 29932 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 27128 KB Output is correct
2 Correct 42 ms 25716 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 210 ms 42360 KB Output is correct
2 Correct 122 ms 33232 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 132 ms 34620 KB Output is correct
2 Correct 108 ms 45928 KB Output is correct