Submission #846087

#	Time	Username	Problem	Language	Result	Execution time	Memory
846087		LucaIlie	Xylophone (JOI18_xylophone)	C++17	47 / 100	58 ms	97212 KiB

xylophone

#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];

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;
    }
    for ( int i = 1; i <= n - 1; i++ )
        ans[i][i + 1] = query( i, i + 1 );
    for ( int i = 1; i <= n - 2; i++ )
        ans[i][i + 2] = query( i, i + 2 );

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

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

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

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

• Subtask 1: 11 / 11
• Subtask 2: 36 / 36
• Subtask 3: 0 / 53