Submission #846105

#	Time	Username	Problem	Language	Result	Execution time	Memory
846105		LucaIlie	Xylophone (JOI18_xylophone)	C++17	100 / 100	55 ms	98960 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];
unordered_map<int, bool> used;

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;
    used[1] = true;
    v[p1 + 1] = 1 + q( p1, p1 + 1 );
    used[v[p1 + 1]] = true;
    if ( p1 > 1 )
        v[p1 - 1] = 1 + q( p1 - 1, p1 );
    used[v[p1 - 1]] = true;

    for ( int i = p1 + 2; i <= n; i++ ) {
        int x = q( i - 1, i );
        if ( v[i - 1] - x < 1 || used[v[i - 1] - x] ) {
            v[i] = v[i - 1] + x;
            continue;
        }
        if ( v[i - 1] + x > n || used[v[i - 1] + x] ) {
            v[i] = v[i - 1] - x;
            continue;
        }

        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 );
        }
        used[v[i]] = true;
    }

    for ( int i = p1 - 2; i >= 1; i-- ) {
        int x = q( i, i + 1 );
        if ( v[i + 1] - x < 1 || used[v[i + 1] - x] ) {
            v[i] = v[i + 1] + x;
            continue;
        }
        if ( v[i + 1] + x > n || used[v[i + 1] + x] ) {
            v[i] = v[i + 1] - x;
            continue;
        }

        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, 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 );
        }
        used[v[i]] = true;
    }

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

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