oj.uz

Submission #763575

# Submission time Handle Problem Language Result Execution time Memory
763575 2023-06-22T13:11:00 Z LucaIlie popa (BOI18_popa) C++17
61 / 100
 833 ms 5200 KB 
#include "popa.h"
#include <bits/stdc++.h>

using namespace std;

int leftSon[1000], rightSon[1000];
int leftExtend[1000], rightExtend[1000], ind[1000][1000];
bool dp[1000][1000];

void makeTree( int l, int r ) {
    if ( l == r ) {
        leftSon[l] = rightSon[l] = -1;
        return;
    }

    //printf( "%d %d %d\n", l, r, ind[l][r] );
    int k = ind[l][r];
    if ( k == l ) {
        leftSon[k] = -1;
        rightSon[k] = ind[k + 1][r];
        makeTree( k + 1, r );
        return;
    }
    if ( k == r ) {
        leftSon[k] = ind[l][k - 1];
        rightSon[k] = -1;
        makeTree( l, k - 1 );
        return;
    }
    makeTree( l, k - 1 );
    makeTree( k + 1, r );
    leftSon[k] = ind[l][k - 1];
    rightSon[k] = ind[k + 1][r];
}

int solve( int n, int leftt[], int rightt[] ) {
    for ( int i = 0; i < n; i++ ) {
        int j = i;
        while ( j - 1 >= 0 && query( i, i, j - 1, i ) ) {
            j--;
            int k = leftExtend[j];
            while ( j - 1 >= k ) {
                j--;
                k = min( k, leftExtend[j] );
            }
        }
        leftExtend[i] = j;
    }
    for ( int i = n - 1; i >= 0; i-- ) {
        int j = i;
        while ( j + 1 < n && query( i, i, i, j + 1 ) ) {
            j++;
            int k = rightExtend[j];
            while ( j + 1 <= k ) {
                j++;
                k = max( k, rightExtend[j] );
            }
        }
        rightExtend[i] = j;
    }

    for ( int i = 0; i < n; i++ ) {
        dp[i][i] = true;
        ind[i][i] = i;
        //printf( "%d: %d %d\n", i, leftExtend[i], rightExtend[i] );
    }
    for ( int len = 2; len <= n; len++ ) {
        for ( int l = 0; l <= n - len; l++ ) {
            int r = l + len - 1;
            for ( int k = l + 1; k <= r - 1; k++ ) {
                if ( leftExtend[k] <= l && r <= rightExtend[k] && dp[l][k - 1] && dp[k + 1][r] ) {
                    dp[l][r] = true;
                    ind[l][r] = k;
                }
            }
            if ( leftExtend[l] <= l && r <= rightExtend[l] && dp[l + 1][r] ) {
                dp[l][r] = true;
                ind[l][r] = l;
            }
            if ( leftExtend[r] <= l && r <= rightExtend[r] && dp[l][r - 1] ) {
                dp[l][r] = true;
                ind[l][r] = r;
            }
            //printf( "%d %d %d\n", l, r, ind[l][r] );
        }
    }

    makeTree( 0, n - 1 );

    for ( int i = 0; i < n; i++ ) {
        leftt[i] = leftSon[i];
        rightt[i] = rightSon[i];
    }

    return ind[0][n - 1];
}

Subtask #1
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 720 KB Output is correct
2 Correct 21 ms 696 KB Output is correct
3 Correct 9 ms 700 KB Output is correct
4 Correct 18 ms 700 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 808 ms 5200 KB Output is correct
2 Correct 804 ms 5196 KB Output is correct
3 Correct 490 ms 5200 KB Output is correct
4 Correct 833 ms 5200 KB Output is correct

Subtask #3
0 / 39.0

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