제출 #1324116

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1324116		sh_qaxxorov_571	Xylophone (JOI18_xylophone)	C++20	47 / 100	25 ms	452 KiB

xylophone

#include "xylophone.h"
#include <vector>
#include <cmath>
#include <algorithm>

using namespace std;

/**
 * JOI Open 2018 - Xylophone
 * Vaqt murakkabligi: O(N)
 * So'rovlar soni: ~2N
 */

void solve(int N) {
    vector<int> A(N + 1);
    vector<int> diff1(N + 1); // query(i, i+1)
    vector<int> diff2(N + 1); // query(i, i+2)
    vector<bool> used(N + 1, false);

    // 1. Eng past tovush (1) indeksini topamiz
    int low = 1, high = N, first_pos = 1;
    while (low <= high) {
        int mid = (low + high) / 2;
        if (query(mid, N) == N - 1) {
            first_pos = mid;
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }

    A[first_pos] = 1;
    used[1] = true;

    // 2. O'ng tomonga qarab aniqlash
    if (first_pos < N) {
        A[first_pos + 1] = 1 + query(first_pos, first_pos + 1);
        used[A[first_pos + 1]] = true;
        
        for (int i = first_pos + 2; i <= N; i++) {
            int d1 = query(i - 1, i);
            int d2 = query(i - 2, i);
            
            // Ikki xil ehtimol bor: A[i-1] + d1 yoki A[i-1] - d1
            int opt1 = A[i - 1] + d1;
            int opt2 = A[i - 1] - d1;

            if (opt1 > N || used[opt1]) A[i] = opt2;
            else if (opt2 < 1 || used[opt2]) A[i] = opt1;
            else {
                // Yo'nalishni query(i-2, i) orqali aniqlaymiz
                int real_max = max({A[i - 2], A[i - 1], opt1});
                int real_min = min({A[i - 2], A[i - 1], opt1});
                if (real_max - real_min == d2) A[i] = opt1;
                else A[i] = opt2;
            }
            used[A[i]] = true;
        }
    }

    // 3. Chap tomonga qarab aniqlash (agar bo'lsa)
    for (int i = first_pos - 1; i >= 1; i--) {
        int d1 = query(i, i + 1);
        int opt1 = A[i + 1] + d1;
        int opt2 = A[i + 1] - d1;

        if (opt1 > N || used[opt1]) A[i] = opt2;
        else if (opt2 < 1 || used[opt2]) A[i] = opt1;
        else {
            int d2 = query(i, i + 2);
            int real_max = max({opt1, A[i + 1], A[i + 2]});
            int real_min = min({opt1, A[i + 1], A[i + 2]});
            if (real_max - real_min == d2) A[i] = opt1;
            else A[i] = opt2;
        }
        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: 0 / 53