oj.uz

Submission #846098

# Submission time Handle Problem Language Result Execution time Memory
846098 2023-09-07T09:50:11 Z LucaIlie Xylophone (JOI18_xylophone) C++17
0 / 100
 1 ms 2496 KB 
#include "xylophone.h"
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 5000;
int v[MAX_N + 1], ans[MAX_N + 1][MAX_N + 1];

int q( int l, int r ) {
    if ( ans[l][r] == -1 )
        ans[l][r] = query( l, r );
    return ans[l][r];
}

void solve( int n ) {
    int l = 1, r = n;
    while ( r - l > 1 ) {
        int mid = (l + r) / 2;
        if ( query( mid, n ) == n - 1 )
            l = mid;
        else
            r = mid;
    }

    int p1 = l;
    for ( int l = 1; l <= n; l++ ) {
        for ( int r = l; r <= n; r++ )
            ans[l][r] = -1;
    }

    v[p1] = 1;
    v[p1 + 1] = 1 + q( p1, p1 + 1 );
    if ( p1 > 1 )
        v[p1 - 1] = 1 + q( p1 - 1, p1 );

    for ( int i = p1 + 2; i <= n; i++ ) {
        if ( v[i - 2] < v[i - 1] ) {
            if ( q( i - 2, i ) == q( i - 2, i - 1 ) )
                v[i] = v[i - 1] - q( i - 1, i );
            else if ( q( i - 2, i ) == q( i - 1, i ) )
                v[i] = v[i - 1] - q( i - 1, i );
            else
                v[i] = v[i - 1] + q( i - 1, i );
        } else {
            if ( q( i - 2, i ) == q( i - 2, i - 1 ) )
                v[i] = v[i - 1] + q( i - 1, i );
            else if ( q( i - 2, i ) == q( i - 1, i ) )
                v[i] = v[i - 1] + q( i - 1, i );
            else
                v[i] = v[i - 1] - q( i - 1, i );
        }
    }

    for ( int i = p1 - 2; i >= 1; i-- ) {
        if ( v[i + 2] < v[i + 1] ) {
            if ( q( i, i + 2 ) == q( i + 1, i + 2 ) )
                v[i] = v[i + 1] - q( i, i + 1);
            else if ( q( i, i + 2 ) == q( i + 1, i + 1 ) )
                v[i] = v[i + 1] - q( i, i + 1);
            else
                v[i] = v[i + 1] + q( i, i + 1);
        } else {
            if ( q( i, i + 2 ) == q( i + 1, i + 2 ) )
                v[i] = v[i + 1] + q( i, i + 1);
            else if ( q( i, i + 2 ) == q( i, i + 1 ) )
                v[i] = v[i + 1] + q( i, i + 1);
            else
                v[i] = v[i + 1] - q( i, i + 1);
        }
    }

    for ( int i = 1; i <= n; i++ )
        answer( i, v[i] );
}

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 440 KB Output is correct
3 Correct 1 ms 2492 KB Output is correct
4 Incorrect 1 ms 2496 KB Wrong Answer [4]
5 Halted 0 ms 0 KB -

Subtask #2
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 440 KB Output is correct
3 Correct 1 ms 2492 KB Output is correct
4 Incorrect 1 ms 2496 KB Wrong Answer [4]
5 Halted 0 ms 0 KB -

Subtask #3
0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 440 KB Output is correct
3 Correct 1 ms 2492 KB Output is correct
4 Incorrect 1 ms 2496 KB Wrong Answer [4]
5 Halted 0 ms 0 KB -