Submission #1273006

#	Time	Username	Problem	Language	Result	Execution time	Memory
1273006		ken7236	Xylophone (JOI18_xylophone)	C++20	100 / 100	28 ms	452 KiB

xylophone

#include "xylophone.h"
#include <bits/stdc++.h>
using namespace std;

static int A[5005];

void solve(int N) {
    vector<int> diff1(N), diff2(N);
    // query(i, i+1)
    for (int i = 1; i < N; i++) {
        diff1[i] = query(i, i+1);
    }
    // query(i, i+2)
    for (int i = 1; i+1 < N; i++) {
        diff2[i] = query(i, i+2);
    }

    vector<int> arr(N+1);
    arr[1] = 0;
    arr[2] = diff1[1]; // either + or -

    // reconstruct with unknown sign
    for (int i = 2; i < N; i++) {
        int d1 = diff1[i];   // |Ai+1 - Ai|
        int d2 = diff2[i-1]; // max-min on (Ai-1, Ai, Ai+1)
        int prev = arr[i-1], cur = arr[i];
        // possible next values
        int cand1 = cur + d1;
        int cand2 = cur - d1;
        // check which one consistent with diff2
        int x1 = min({prev, cur, cand1});
        int y1 = max({prev, cur, cand1});
        bool ok1 = (y1 - x1 == d2);
        int x2 = min({prev, cur, cand2});
        int y2 = max({prev, cur, cand2});
        bool ok2 = (y2 - x2 == d2);
        if (ok1) arr[i+1] = cand1;
        else arr[i+1] = cand2;
    }

    // shift to [1..N]
    int mn = *min_element(arr.begin()+1, arr.begin()+N+1);
    for (int i = 1; i <= N; i++) arr[i] -= mn-1;

    // check orientation: smallest index must be before largest index
    int posMin = min_element(arr.begin()+1, arr.begin()+N+1) - arr.begin();
    int posMax = max_element(arr.begin()+1, arr.begin()+N+1) - arr.begin();
    if (posMin > posMax) {
        // flip
        for (int i = 1; i <= N; i++) arr[i] = N+1-arr[i];
    }

    // output answers
    for (int i = 1; i <= N; i++) {
        answer(i, arr[i]);
    }
}

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