제출 #64418

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
64418		Bodo171	popa (BOI18_popa)	C++14	0 / 100	1067 ms	528 KiB

popa

#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-i;i++)
          dp[len][i]=0;
    n=N;
    for(len=1;len<=n;len++)
        for(i=0;i<n-len;i++)
    {
        for(j=i;j<i+len&&(!dp[j-i+1][j]);j++)
        {
            if(dp[j-i+1][j]&&dp[len-(j-i+1)][j+1]&&st[j]<=i&&dr[j]>=i+len-1)
                dp[j-i+1][j]=0,par[j-i+1][j]=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: 0 / 37
• Subtask 2: 0 / 24
• Subtask 3: 0 / 39