Submission #865559

#	Time	Username	Problem	Language	Result	Execution time	Memory
865559		12345678	Xylophone (JOI18_xylophone)	C++17	100 / 100	58 ms	1452 KiB

xylophone

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

using namespace std;

const int nx=5e3+5;
int d1[nx], d2[nx], v1[nx], v2[nx];
bool ad[nx], ad2[nx];

void solve(int N) {
    for (int i=1; i<N; i++) d1[i]=query(i, i+1);
    for (int i=1; i<N-1; i++) d2[i]=query(i, i+2);
    v1[2]=d1[1]; ad[1]=1;
    pair<int, int> mn={0, 1}, mx={d1[1], 2};
    for (int i=3; i<=N; i++)
    {
        if (d2[i-2]==d1[i-2]+d1[i-1])
        {
            if (ad[i-2]) v1[i]=v1[i-1]+d1[i-1], ad[i-1]=1;
            else v1[i]=v1[i-1]-d1[i-1], ad[i-1]=0;
        }
        else
        {
            if (ad[i-2]) v1[i]=v1[i-1]-d1[i-1], ad[i-1]=0;
            else v1[i]=v1[i-1]+d1[i-1], ad[i-1]=1;
        }
        mn=min(mn, {v1[i], i});
        mx=max(mx, {v1[i], i});
    }
    v2[2]=-d1[1]; ad2[1]=0;
    for (int i=3; i<=N; i++)
    {
        if (d2[i-2]==d1[i-2]+d1[i-1])
        {
            if (ad2[i-2]) v2[i]=v2[i-1]+d1[i-1], ad2[i-1]=1;
            else v2[i]=v2[i-1]-d1[i-1], ad2[i-1]=0;
        }
        else
        {
            if (ad2[i-2]) v2[i]=v2[i-1]-d1[i-1], ad2[i-1]=0;
            else v2[i]=v2[i-1]+d1[i-1], ad2[i-1]=1;
        }
    }
    if (mn.second<mx.second) for (int i=1; i<=N; i++) answer(i, v1[i]-mn.first+1);
    else for (int i=1; i<=N; i++) answer(i, v2[i]+mx.first+1);
}

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