Submission #1306894

#	Time	Username	Problem	Language	Result	Execution time	Memory
1306894		teamcuddlepie	Xylophone (JOI18_xylophone)	C++20	100 / 100	19 ms	444 KiB

xylophone

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

using namespace std;

void solve(int N) {
    vector<int> a(N + 1, 0);
    vector<bool> used(N + 1, false);

    // 1. Find position of 1 using binary search
    int low = 1, high = N, pos1 = 1;
    while (low <= high) {
        int mid = (low + high) / 2;
        if (mid == N) break; // Avoid query(N, N) if unnecessary
        if (query(mid, N) == N - 1) {
            pos1 = mid;
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }

    auto determine = [&](int cur, int prev, int pprev) {
        int d1 = query(min(cur, prev), max(cur, prev));
        int c1 = a[prev] + d1;
        int c2 = a[prev] - d1;

        // Validation against bounds and used numbers
        if (c1 < 1 || c1 > N || used[c1]) return c2;
        if (c2 < 1 || c2 > N || used[c2]) return c1;

        // Tie-breaker using query(i-2, i)
        int d2 = query(min(cur, pprev), max(cur, pprev));
        if (max({a[prev], a[pprev], c1}) - min({a[prev], a[pprev], c1}) == d2) {
            return c1;
        }
        return c2;
    };

    // Initialize 1
    a[pos1] = 1;
    used[1] = true;

    // 2. Solve Right
    if (pos1 < N) {
        a[pos1 + 1] = 1 + query(pos1, pos1 + 1);
        used[a[pos1 + 1]] = true;
        for (int i = pos1 + 2; i <= N; i++) {
            a[i] = determine(i, i - 1, i - 2);
            used[a[i]] = true;
        }
    }

    // 3. Solve Left
    if (pos1 > 1) {
        a[pos1 - 1] = 1 + query(pos1 - 1, pos1);
        used[a[pos1 - 1]] = true;
        for (int i = pos1 - 2; i >= 1; i--) {
            a[i] = determine(i, i + 1, i + 2);
            used[a[i]] = true;
        }
    }

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

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