oj.uz

Submission #235173

# Submission time Handle Problem Language Result Execution time Memory
235173 2020-05-27T08:31:26 Z topovik Doktor (COCI17_doktor) C++14
100 / 100
 481 ms 89440 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=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

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

# Verdict Execution time Memory Grader output
1 Correct 5 ms 256 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
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 640 KB Output is correct
2 Correct 6 ms 676 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 1152 KB Output is correct
2 Correct 6 ms 768 KB Output is correct

Subtask #6
10.0 / 10.0

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

Subtask #7
10.0 / 10.0

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

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 16632 KB Output is correct
2 Correct 68 ms 17500 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 481 ms 89440 KB Output is correct
2 Correct 356 ms 86372 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 276 ms 52680 KB Output is correct
2 Correct 319 ms 81888 KB Output is correct