Submission #235173

#	Time	Username	Problem	Language	Result	Execution time	Memory
235173		topovik	Doktor (COCI17_doktor)	C++14	100 / 100	481 ms	89440 KiB

doktor

#include <bits/stdc++.h>

#define f first
#define s second
#define pb push_back
#define INF 1000000000
#define N (long)1e5+2

using namespace std;

typedef long long ll;
typedef long double ld;

int main()
{
    int n;
    cin>>n;
    int b[n];
    for (int i=0; i<n; i++) cin>>b[i];
    int a[n];
    for (int i=0; i<n; i++) a[i]=b[i]-i-1;

    vector <int> lf[n*2],rg[n*2];

    for (int i=0; i<n; i++)
        if (a[i]<0) rg[i*2+a[i]].pb(a[i]);
        else
        if (a[i]>0) lf[i*2+a[i]].pb(a[i]);
    int pr[n];
    pr[-1]=0;
    for (int i=0; i<n; i++) pr[i]=pr[i-1]+(a[i]==0);
    int ans=0,l=0,r=0;
    for (int i=0; i<n*2; i++)
    {
        lf[i].pb(0);
        sort(lf[i].begin(),lf[i].end());
        int kol=1*(i%2==0 && a[i/2]==0);
        int j1=0;
        for (int i1=0; i1<lf[i].size() && (i+lf[i][i1])<n*2; i1++)
        {
            while (j1<rg[i].size() && abs(rg[i][j1])<=lf[i][i1]) j1++;
            int mx=lf[i][i1];
            int c1=i1+j1-(pr[(i+mx)/2]-pr[(i-mx)/2-1])+kol;
            if (c1>ans) ans=c1,l=b[(i-mx)/2],r=b[(i+mx)/2];
        }
        j1=0;
        for (int i1=0; i1<rg[i].size() && (i+rg[i][i1])>=0; i1++)
        {
            while (j1<lf[i].size() && lf[i][j1]<=abs(rg[i][i1])) j1++;
            int mx=abs(rg[i][i1]);
            int c1=i1+j1-(pr[(i+mx)/2]-pr[(i-mx)/2-1])+kol;
            if (c1>ans) ans=c1,l=b[(i-mx)/2],r=b[(i+mx)/2];
        }
    }
   if (l==0) cout<<1<<" "<<1;
   else      cout<<l<<" "<<r;

}

Compilation message (stderr)

doktor.cpp: In function 'int main()':
doktor.cpp:39:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int i1=0; i1<lf[i].size() && (i+lf[i][i1])<n*2; i1++)
                        ~~^~~~~~~~~~~~~
doktor.cpp:41:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             while (j1<rg[i].size() && abs(rg[i][j1])<=lf[i][i1]) j1++;
                    ~~^~~~~~~~~~~~~
doktor.cpp:47:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int i1=0; i1<rg[i].size() && (i+rg[i][i1])>=0; i1++)
                        ~~^~~~~~~~~~~~~
doktor.cpp:49:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             while (j1<lf[i].size() && lf[i][j1]<=abs(rg[i][i1])) j1++;
                    ~~^~~~~~~~~~~~~

• 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