Submission #358521

#	Time	Username	Problem	Language	Result	Execution time	Memory
358521		Lam_lai_cuoc_doi	Xylophone (JOI18_xylophone)	C++17	100 / 100	125 ms	492 KiB

xylophone

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;

#include "xylophone.h"

void solve(int n)
{
    vector<int> a(n + 1);
    vector<bool> ck(n + 1);
    ck[1] = 1;
    for (int i = 1; i < n; ++i)
        a[i + 1] = query(i, i + 1);
    for (int i = 1; i < n - 1; ++i)
    {
        int v = query(i, i + 2);
        if (v == a[i + 2] + a[i + 1])
            ck[i + 1] = ck[i];
        else
            ck[i + 1] = !ck[i];
    }
    int maxn(a[1]), minn(a[1]);
    int mnp(1), mxp(1);
    for (int i = 1; i < n; ++i)
    {
        a[i + 1] = a[i] + a[i + 1] * (ck[i] ? 1 : -1);
        if (maxn < a[i + 1])
        {
            maxn = a[i + 1];
            mxp = i + 1;
        }
        if (minn > a[i + 1])
        {
            minn = a[i + 1];
            mnp = i + 1;
        }
    }
    if (mnp < mxp)
    {
        for (int i = 1; i <= n; ++i)
            answer(i, a[i] - minn + 1);
    }
    else
    {
        for (int i = 1; i <= n; ++i)
            answer(i, -a[i] - (-maxn) + 1);
    }
}

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