Submission #1143823

#	Time	Username	Problem	Language	Result	Execution time	Memory
1143823		lightentheshadow	Xylophone (JOI18_xylophone)	C++20	100 / 100	26 ms	496 KiB

xylophone

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

int cmp2[5005], cmp3[5005], diff[5005], a[5005];

void solve(int n) {
    for (int i = 1; i < n; i++) {
        cmp2[i] = query(i, i + 1);
        if (i + 2 <= n) cmp3[i] = query(i, i + 2);
    }

    diff[1] = cmp2[1];
    for (int i = 2; i < n; i++) {
        diff[i] = cmp2[i];
        if (cmp2[i - 1] + cmp2[i] == cmp3[i - 1]) {
            if (diff[i] * diff[i - 1] < 0) diff[i] *= -1;
        }
        else {
            if (diff[i] * diff[i - 1] > 0) diff[i] *= -1;
        }
    }

    a[1] = 0;
    for (int i = 1; i < n; i++)
        a[i + 1] = a[i] + diff[i];

    int mnPos = min_element(a + 1, a + n + 1) - a, mxPos = max_element(a + 1, a + n + 1) - a;
    if (mnPos > mxPos) {
        for (int i = 1; i <= n; i++)
            a[i] *= -1;
    }

    int x = *min_element(a + 1, a + n + 1);
    for (int i = 1; i <= n; i++)
        a[i] = a[i] - x + 1;

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

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