Submission #763066

#	Time	Username	Problem	Language	Result	Execution time	Memory
763066		vjudge1	Xylophone (JOI18_xylophone)	C++17	100 / 100	121 ms	98420 KiB

xylophone

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

using namespace std;

void solve(int n)
{
    vector<vector<int>> q(n + 1, vector<int>(n + 1, INT_MAX));
    for (int i = 2; i <= n; i++)
        q[i - 1][i] = query(i - 1, i);
    for (int i = 3; i <= n; i++)
        q[i - 2][i] = query(i - 2, i);

    vector<int> trend(n + 1);
    trend[2] = 1;
    for (int i = 3; i <= n; i++)
    {
        if (q[i - 2][i - 1] + q[i - 1][i] == q[i - 2][i])
            trend[i] = trend[i - 1];
        else
            trend[i] = - trend[i - 1];
    }

    vector<int> v(n + 1);

    int iMin = 1, iMax = 1;
    v[1] = 0;
    for (int i = 2; i <= n; i++)
    {
        v[i] = v[i - 1] + trend[i] * q[i - 1][i];
        if (v[i] < v[iMin]) iMin = i;
        if (v[i] > v[iMax]) iMax = i;
    }

    int d = 1 - v[iMin];
    for (int i = 1; i <= n; i++)
        v[i] += d;

    if (iMin > iMax)
        for (int i = 1; i <= n; i++)
            v[i] = n + 1 - v[i];

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

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