Submission #1091721

#	Time	Username	Problem	Language	Result	Execution time	Memory
1091721		raphaelp	Xylophone (JOI18_xylophone)	C++17	100 / 100	43 ms	608 KiB

xylophone

#include "xylophone.h"
#include <bits/stdc++.h>
using namespace std;
/*vector<int> Tab;
int query(int a, int b)
{
    a--, b--;
    int minn = Tab.size(), maxx = 0;
    for (int i = a; i <= b; i++)
    {
        minn = min(minn, Tab[i]);
        maxx = max(maxx, Tab[i]);
    }
    return maxx - minn;
}
void answer(int i, int val) { cout << val << ' '; }*/
void solve(int N)
{
    int L = 0, R = N;
    while (L != R)
    {
        int m = (L + R) / 2;
        int temp = query(m + 1, N);
        if (temp == N - 1)
            L = m + 1;
        else
            R = m;
    }
    int ref = L - 1;
    vector<int> ans(N, -1), occ(N);
    occ[0] = 1;
    ans[ref] = 0;
    for (int i = ref + 1; i < N; i++)
    {
        int temp = query(i, i + 1);
        if (ans[i - 1] + temp >= N || occ[ans[i - 1] + temp])
            ans[i] = ans[i - 1] - temp;
        else if (ans[i - 1] - temp < 0 || occ[ans[i - 1] - temp])
            ans[i] = ans[i - 1] + temp;
        else
        {
            int temp2 = query(i - 1, i + 1);
            if (temp2 == ans[i - 1] - ans[i - 2] + temp || ans[i - 2] - ans[i - 1] == temp2 || (temp == temp2 && ans[i - 2] > ans[i - 1]))
                ans[i] = ans[i - 1] + temp;
            else
                ans[i] = ans[i - 1] - temp;
        }
        occ[ans[i]] = 1;
    }
    for (int i = ref - 1; i >= 0; i--)
    {
        int temp = query(i + 1, i + 2);
        if (ans[i + 1] + temp >= N || occ[ans[i + 1] + temp])
            ans[i] = ans[i + 1] - temp;
        else if (ans[i + 1] - temp < 0 || occ[ans[i + 1] - temp])
            ans[i] = ans[i + 1] + temp;
        else
        {
            int temp2 = query(i + 1, i + 3);
            if (temp2 == ans[i + 1] - ans[i + 2] + temp || ans[i + 2] - ans[i + 1] == temp2 || (temp == temp2 && ans[i + 2] > ans[i + 1]))
                ans[i] = ans[i + 1] + temp;
            else
                ans[i] = ans[i + 1] - temp;
        }
        occ[ans[i]] = 1;
    }
    for (int i = 0; i < N; i++)
        answer(i + 1, ans[i] + 1);
}
/*int main()
{
    int N;
    cin >> N;
    Tab.assign(N, 0);
    for (int i = 0; i < N; i++)
    {
        cin >> Tab[i];
    }
    solve(N);
}*/

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