oj.uz

Submission #235168

# Submission time Handle Problem Language Result Execution time Memory
235168 2020-05-27T08:17:16 Z topovik Doktor (COCI17_doktor) C++14
50 / 100
 483 ms 89400 KB 
#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;
            if (j1==0) mx=lf[i][i1];
            else       mx=max(lf[i][i1],abs(rg[i][j1-1]));
            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

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++;
                    ~~^~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 640 KB Output is correct
2 Incorrect 6 ms 640 KB Output isn't correct

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 1152 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 1152 KB Output is correct
2 Incorrect 5 ms 384 KB Output isn't correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 2176 KB Output is correct
2 Correct 204 ms 51948 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 16632 KB Output is correct
2 Correct 66 ms 17524 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 483 ms 89400 KB Output is correct
2 Correct 342 ms 86612 KB Output is correct

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 260 ms 52472 KB Output isn't correct
2 Halted 0 ms 0 KB -