oj.uz

Submission #846073

# Submission time Handle Problem Language Result Execution time Memory
846073 2023-09-07T09:10:20 Z LucaIlie Xylophone (JOI18_xylophone) C++17
0 / 100
 1 ms 2488 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];

void solve( int n ) {
    int p1 = 1;
    while ( query( p1 + 1, n ) == n - 1 )
        p1++;

    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 >= n; 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
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 444 KB Output is correct
2 Correct 0 ms 448 KB Output is correct
3 Incorrect 1 ms 2488 KB Wrong Answer [4]
4 Halted 0 ms 0 KB -

Subtask #2
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 444 KB Output is correct
2 Correct 0 ms 448 KB Output is correct
3 Incorrect 1 ms 2488 KB Wrong Answer [4]
4 Halted 0 ms 0 KB -

Subtask #3
0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 444 KB Output is correct
2 Correct 0 ms 448 KB Output is correct
3 Incorrect 1 ms 2488 KB Wrong Answer [4]
4 Halted 0 ms 0 KB -