Submission #1324117

#	Time	Username	Problem	Language	Result	Execution time	Memory
1324117		sh_qaxxorov_571	Xylophone (JOI18_xylophone)	C++20	0 / 100	1 ms	400 KiB

xylophone

#include <bits/stdc++.h>
using namespace std;

// Grader tomonidan taqdim etiladigan funksiyalar
int query(int s, int t);     // s..t oralig'idagi max-min farqini qaytaradi
void answer(int i, int a);   // i-chi barni a balandlikda deb javob beradi

void solve(int N) {
    vector<int> pos(N+1, -1); // balandlik bo'yicha index saqlaymiz
    vector<int> bar(N+1, 0);  // index bo'yicha balandlik

    // Eng past (1) va eng yuqori (N) barlarni topamiz
    int l = 1, r = N;
    while(l < r) {
        int diff = query(l, r);
        if(diff == N-1) break;
        // Agar farq kam bo'lsa, segmentni qisqartiramiz
        int mid = (l+r)/2;
        int left_diff = query(l, mid);
        if(left_diff == mid-l) r = mid;
        else l = mid+1;
    }

    // Eng past balandlik = 1, eng yuqori balandlik = N
    int min_pos = l;
    int max_pos = r;
    pos[1] = min_pos;
    pos[N] = max_pos;
    bar[min_pos] = 1;
    bar[max_pos] = N;

    // Qolgan balandliklarni aniqlash
    set<int> remaining;
    for(int i=1; i<=N; i++) {
        if(i != min_pos && i != max_pos) remaining.insert(i);
    }

    // Segmentlarni bo'lib, binary search bilan aniqlash
    function<void(int,int,int,int)> dfs = [&](int l, int r, int low, int high) {
        if(l > r || low+1 == high) return;
        int mid_val = (low+high)/2;
        int left_diff = query(l, r);
        // left_diff yordamida qaysi bar yuqoriroq yoki pastroq ekanini aniqlash
        vector<int> new_remaining;
        for(int i : remaining) {
            int d = max(high, i) - min(low, i);
            if(d == left_diff) new_remaining.push_back(i);
        }
        // Recursive chaqirish
        for(int val : new_remaining) {
            bar[val] = val;
            pos[val] = val; // soddalashtirilgan misol uchun
            remaining.erase(val);
        }
    };

    dfs(1,N,1,N);

    // Javobni beramiz
    for(int i=1; i<=N; i++) {
        answer(i, bar[i]);
    }
}

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