Submission #1129121

#	Time	Username	Problem	Language	Result	Execution time	Memory
1129121		not_amir	Xylophone (JOI18_xylophone)	C++20	100 / 100	39 ms	436 KiB

xylophone

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

static int A[5000];

void solve(int N) {
    vector<int> val(N);
    for (int i = 1; i < N; i++) {
        val[i] = query(i, i + 1);
    }
    vector<bool> dir(N);
    for (int i = 1; i < N - 1; i++) {
        int x = query(i, i + 2);
        if (val[i] + val[i + 1] == x)
            dir[i + 1] = dir[i];
        else
            dir[i + 1] = !dir[i];
    }
    vector<int> sum(N);
    int minv = 0, idxmin = 0;
    int maxv = 0, idxmax = 0;
    for (int i = 1; i < N; i++) {
        if (dir[i])
            sum[i] = sum[i - 1] + val[i];
        else
            sum[i] = sum[i - 1] - val[i];
        if (sum[i] < minv)
            minv = sum[i], idxmin = i;
        if (sum[i] > maxv)
            maxv = sum[i], idxmax = i;
    }
    if (idxmin > idxmax) {
        minv = -maxv;
        for (int i = 0; i < N; i++)
            sum[i] *= -1;
    }
    for (int i = 0; i < N; i++)
        answer(i + 1, sum[i] - minv + 1);
}

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