Submission #714235

#	Time	Username	Problem	Language	Result	Execution time	Memory
714235		four_specks	Xylophone (JOI18_xylophone)	C++17	100 / 100	117 ms	592 KiB

xylophone

#include "xylophone.h"

#include <bits/stdc++.h>

using namespace std;

static int A[5000];

void solve(int N)
{
    vector mem(N, vector<int>(3, -1));

    auto qry = [&](int k, int d)
    {
        if (mem[k][d] == -1)
            mem[k][d] = query(k + 1, k + d + 1);

        return mem[k][d];
    };

    vector<bool> dir(N - 1);
    vector<int> diff(N - 1);

    diff[0] = qry(0, 1);
    for (int i = 0; i < N - 2; i++)
    {
        int
            x = qry(i, 1),
            y = qry(i + 1, 1),
            z = qry(i, 2);

        dir[i + 1] = dir[i] ^ (x + y != z);
        diff[i + 1] = y;
    }

    vector<int> a(N);
    for (int i = 0; i < N - 1; i++)
        a[i + 1] = a[i] + (dir[i] ? diff[i] : -diff[i]);

    if (max_element(a.begin(), a.end()) < min_element(a.begin(), a.end()))
    {
        for (int i = 0; i < N; i++)
            a[i] = -a[i];
    }

    int sub = *min_element(a.begin(), a.end());

    for (int i = 0; i < N; i++)
        a[i] = a[i] - sub;

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

Compilation message (stderr)

xylophone.cpp:7:12: warning: 'A' defined but not used [-Wunused-variable]
    7 | static int A[5000];
      |            ^

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