Submission #92926

#	Time	Username	Problem	Language	Result	Execution time	Memory
92926		vex	Doktor (COCI17_doktor)	C++14	100 / 100	210 ms	45928 KiB

doktor

#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 / 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