Submission #92796

#	Time	Username	Problem	Language	Result	Execution time	Memory
92796		Alexa2001	Xylophone (JOI18_xylophone)	C++17	100 / 100	110 ms	460 KiB

xylophone

#include "xylophone.h"
#include<bits/stdc++.h>

using namespace std;

const int Nmax = 5005;
static int A[Nmax], B[Nmax], x[Nmax];

void solve(int N)
{
    int i;
    for(i=1; i<=N-1; ++i) A[i] = query(i, i+1);
    for(i=1; i<=N-2; ++i) B[i] = query(i, i+2);

    x[1] = 0; x[2] = A[1];

    for(i=3; i<=N; ++i)
        if(x[i-2] < x[i-1])
        {
            if(B[i-2] == A[i-2]) /// middle value
                x[i] = x[i-1] - A[i-1];
            else if(A[i-1] == B[i-2]) /// smallest value
                x[i] = x[i-1] - A[i-1];
            else x[i] = x[i-1] + A[i-1]; /// greatest value
        }
        else
        {
            if(B[i-2] == A[i-2]) /// middle
                x[i] = x[i-1] + A[i-1];
            else if(A[i-1] == B[i-2]) /// greatest
                x[i] = x[i-1] + A[i-1];
            else x[i] = x[i-1] - A[i-1];
        }
    int Min = 0;
    for(i=1; i<=N; ++i) Min = min(Min, x[i]);
    for(i=1; i<=N; ++i) x[i] -= Min - 1;

    int id1 = -1, idn = -1;
    for(i=1; i<=N; ++i)
        if(x[i] == 1) id1 = i;
            else if(x[i] == N) idn = i;

    assert(id1 != -1); assert(idn != -1);

    if(id1 > idn)
        for(i=1; i<=N; ++i) x[i] = N + 1 - x[i];
    for(i=1; i<=N; ++i) answer(i, x[i]);
}

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