oj.uz

Submission #64422

# Submission time Handle Problem Language Result Execution time Memory
64422 2018-08-04T11:58:16 Z Bodo171 popa (BOI18_popa) C++14
37 / 100
 1000 ms 8376 KB 
#include "popa.h"
#include <iostream>
using namespace std;
const int nmax=1005;
int i,st[nmax],dr[nmax],root,p,n,len,j;
int dp[nmax][nmax];
int l[nmax],r[nmax];
int par[nmax][nmax];
void deco(int st,int dr)
{
    int x=par[dr-st+1][st];
    if(x>st)
    {
        l[x]=par[x-st][st];
        deco(st,x-1);
    }
    else
        l[x]=-1;
    if(x<dr)
    {
        r[x]=par[dr-x][x+1];
        deco(x+1,dr);
    }
    else r[x]=-1;
}
int solve(int N, int* Left, int* Right)
{
    for(i=1;i<N;i++)
    {
        st[i]=i;
        for(p=9;p>=0;p--)
            if(st[i]-(1<<p)>=0&&query(st[i]-(1<<p),i,i,i))
               st[i]-=(1<<p);
    }
    dr[N-1]=N-1;
    for(i=N-2;i>=0;i--)
    {
        dr[i]=i;
        for(p=9;p>=0;p--)
            if(dr[i]+(1<<p)<N&&query(i,dr[i]+(1<<p),i,i))
                dr[i]+=(1<<p);
    }
    for(len=1;len<=n;len++)
        for(i=0;i<=n-len;i++)
          dp[len][i]=0;
    n=N;
    for(i=0;i<n;i++)
        dp[1][i]=dp[0][i]=1,par[1][i]=i;
    dp[0][n]=1;
    for(len=2;len<=n;len++)
    {
        for(i=0;i<=n-len;i++)
     {
        for(j=i;j<i+len&&(!dp[len][i]);j++)
        {
            if(dp[j-i][i]&&dp[len-(j-i+1)][j+1]&&st[j]<=i&&dr[j]>=i+len-1)
                dp[len][i]=1,par[len][i]=j;
        }
     }
    }
    deco(0,n-1);
    for(i=0;i<n;i++)
        Left[i]=l[i],Right[i]=r[i];
    return par[n][0];
}

Subtask #1
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 1016 KB Output is correct
2 Correct 41 ms 1204 KB Output is correct
3 Correct 83 ms 1204 KB Output is correct
4 Correct 72 ms 1212 KB Output is correct

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1027 ms 8376 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 39.0

# Verdict Execution time Memory Grader output
1 Incorrect 24 ms 8376 KB too many queries
2 Halted 0 ms 0 KB -