Submission #772031

#	Time	Username	Problem	Language	Result	Execution time	Memory
772031		Tenis0206	Sequence (APIO23_sequence)	C++17	0 / 100	50 ms	13912 KiB

sequence

#include <bits/stdc++.h>

using namespace std;

const int nmax = 5e5;

int n;
int v[nmax + 5];

int lst[nmax + 5], ldr[nmax + 5], rst[nmax + 5], rdr[nmax + 5];

bool subtask3()
{
    return true;
}

int solve3()
{
    int poz = 0;
    for(int i=1; i<=n; i++)
    {
        if(v[i] > v[i + 1])
        {
            poz = i;
            break;
        }
    }
    for(int i=1; i<=poz; i++)
    {
        if(!lst[v[i]])
        {
            lst[v[i]] = i;
        }
        ldr[v[i]] = i;
    }
    for(int i=poz+1; i<=n; i++)
    {
        if(!rst[v[i]])
        {
            rst[v[i]] = i;
        }
        rdr[v[i]] = i;
    }
    int rez = 0;
    for(int i=1;i<=n;i++)
    {
        if(!lst[i] || !rst[i])
        {
            rez = max(rez, ldr[i] - lst[i] + 1);
            rez = max(rez, rdr[i] - rst[i] + 1);
            continue;
        }
        int lmax = min(n,(rdr[i] - lst[i] + 1) * 2);
        if(rst[i] - ldr[i] - 1 <= (lmax + 1) / 2)
        {
            rez = max(rez, ldr[i] - lst[i] + 1 + rdr[i] - rst[i] + 1);
        }
    }
    return rez;
}

int sequence(int N, vector<int> A)
{
    n = N;
    for(int i=1;i<=n;i++)
    {
        lst[i] = ldr[i] = rst[i] = rdr[i] = 0;
        v[i] = A[i - 1];
    }
    if(subtask3())
    {
        return solve3();
    }
}

#ifdef home

int main()
{
    freopen("nr.in","r",stdin);
    freopen("nr.out","w",stdout);
    int nn;
    cin>>nn;
    vector<int> vv(nn);
    for(int i=1; i<=nn; i++)
    {
        cin>>vv[i - 1];
    }
    cout<<sequence(nn,vv)<<'\n';
    return 0;
}

#endif // home

Compilation message (stderr)

sequence.cpp: In function 'int sequence(int, std::vector<int>)':
sequence.cpp:74:1: warning: control reaches end of non-void function [-Wreturn-type]
   74 | }
      | ^

• Subtask 1: 0 / 11
• Subtask 2: 0 / 17
• Subtask 3: 0 / 7
• Subtask 4: 0 / 12
• Subtask 5: 0 / 13
• Subtask 6: 0 / 22
• Subtask 7: 0 / 18