Submission #1218579

#	Time	Username	Problem	Language	Result	Execution time	Memory
1218579		Double_Slash	Xylophone (JOI18_xylophone)	C++20	100 / 100	19 ms	432 KiB

xylophone

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

using namespace std;

bool seen[5001];
int ans[5001];

void solve(int n) {
    int lo = 1, hi = n;
    for (int k = 13; k--;) {
        if (hi - (1 << k) >= lo and query(lo, hi - (1 << k)) == n - 1) hi -= 1 << k;
        if (lo + (1 << k) <= hi and query(lo + (1 << k), hi) == n - 1) lo += 1 << k;
    }
    auto upd = [&] (int i, int v) {
        answer(i, ans[i] = v);
        seen[v] = true;
    };
    upd(lo, 1);
    upd(hi, n);
    auto can = [&] (int i) { return i >= 1 and i <= n and not seen[i]; };
    auto left = [&] (int i) {
        int d = query(i, i + 1);
        if (can(ans[i + 1] - d) and can(ans[i + 1] + d)) {
            if (max(ans[i + 1], ans[i + 2]) - min(ans[i + 1] - d, ans[i + 2]) == query(i, i + 2)) upd(i, ans[i + 1] - d);
            else upd(i, ans[i + 1] + d);
        } else if (can(ans[i + 1] - d)) upd(i, ans[i + 1] - d);
        else upd(i, ans[i + 1] + d);
    };
    auto right = [&] (int i) {
        int d = query(i - 1, i);
        if (can(ans[i - 1] - d) and can(ans[i - 1] + d)) {
            if (max(ans[i - 1], ans[i - 2]) - min(ans[i - 1] - d, ans[i - 2]) == query(i - 2, i)) upd(i, ans[i - 1] - d);
            else upd(i, ans[i - 1] + d);
        } else if (can(ans[i - 1] - d)) upd(i, ans[i - 1] - d);
        else upd(i, ans[i - 1] + d);
    };
    if (lo > 1) upd(lo - 1, 1 + query(lo - 1, lo));
    for (int i = lo - 1; --i >= 1;) left(i);
    if (lo + 1 < hi) upd(lo + 1, 1 + query(lo, lo + 1));
    for (int i = lo + 1; ++i < hi - 1;) right(i);
    if (hi - 1 > lo) upd(hi - 1, n - query(hi - 1, hi));
    if (hi < n) upd(hi + 1, n - query(hi, hi + 1));
    for (int i = hi + 1; ++i <= n;) right(i);
}

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