Submission #1156129

#	Time	Username	Problem	Language	Result	Execution time	Memory
1156129		tvgk	Xylophone (JOI18_xylophone)	C++20	100 / 100	17 ms	448 KiB

xylophone

#include "xylophone.h"
#include<bits/stdc++.h>
using namespace std;
#define task "a"
#define se second
#define fi first
#define ll long long
#define ii pair<ll, ll>
const long mxN = 5e3 + 7;
bool dd[mxN];
int a[mxN], dif[mxN];

int Check(int j, int n)
{
    if (j <= 0 || j > n || dd[j])
        return 0;
    return j;
}

void solve(int n)
{
    int l = 1, r = n, vt = 0;
    while (l <= r)
    {
        int mid = (l + r) / 2;
        int tmp = query(1, mid);

        if (tmp == n - 1)
        {
            vt = mid;
            r = mid - 1;
        }
        else
            l = mid + 1;
    }

    dd[n] = 1;
    a[vt] = n;
    for (int i = vt + 1; i <= n; i++)
    {
        dif[i] = query(i - 1, i);

        if (Check(a[i - 1] - dif[i], n) && Check(a[i - 1] + dif[i], n))
        {
            int tmp = query(i - 2, i);

            if (tmp == dif[i] + dif[i - 1])
                a[i] = a[i - 2] - (a[i - 2] - a[i - 1]) / dif[i - 1] * tmp;
            else
                a[i] = a[i - 1] + (a[i - 2] - a[i - 1]) / dif[i - 1] * dif[i];
        }
        else
            a[i] = max(Check(a[i - 1] - dif[i], n), Check(a[i - 1] + dif[i], n));
        dd[a[i]] = 1;
    }

    for (int i = vt - 1; i >= 1; i--)
    {
        dif[i] = query(i, i + 1);

        if (Check(a[i + 1] - dif[i], n) && Check(a[i + 1] + dif[i], n))
        {
            int tmp = query(i, i + 2);

            if (tmp == dif[i] + dif[i + 1])
                a[i] = a[i + 2] - (a[i + 2] - a[i + 1]) / dif[i + 1] * tmp;
            else
                a[i] = a[i + 1] + (a[i + 2] - a[i + 1]) / dif[i + 1] * dif[i];
        }
        else
            a[i] = max(Check(a[i + 1] - dif[i], n), Check(a[i + 1] + dif[i], n));
        dd[a[i]] = 1;
    }

//    cout << vt << '\n';
//    for (int i = 1; i <= n; i++)
//        cout << a[i] << " " << dif[i] << "  ";
//    cout << '\n';

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

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