제출 #1324049

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1324049		sh_qaxxorov_571	Gap (APIO16_gap)	C++20	100 / 100	47 ms	1880 KiB

gap

#include "gap.h"
#include <algorithm>
#include <vector>

using namespace std;

typedef long long ll;

ll findGap(int T, int N) {
    if (T == 1) {
        // 1-Subtask: Har safar chetki elementlarni topib, oraliqni toraytiramiz
        ll mn_val, mx_val;
        ll l = 0, r = 1e18;
        vector<ll> a(N);
        int i = 0, j = N - 1;

        while (i <= j) {
            MinMax(l, r, &mn_val, &mx_val);
            a[i++] = mn_val;
            a[j--] = mx_val;
            l = mn_val + 1;
            r = mx_val - 1;
        }

        ll max_diff = 0;
        for (int k = 0; k < N - 1; k++) {
            max_diff = max(max_diff, a[k+1] - a[k]);
        }
        return max_diff;
    } else {
        // 2-Subtask: Oraliqni teng bo'laklarga bo'lib, maksimal farqni qidiramiz
        ll mn_all, mx_all;
        MinMax(0, 1e18, &mn_all, &mx_all);
        
        ll L = mn_all, R = mx_all;
        // Kamida (R-L)/(N-1) masofa bo'lishi aniq
        ll block_size = (R - L + N - 2) / (N - 1); 
        ll max_diff = block_size;
        ll last_val = mn_all;

        for (ll i = L + 1; i < R; i += block_size + 1) {
            ll cur_mn, cur_mx;
            // Har bir blokdan faqat min va max ni olamiz
            MinMax(i, min(i + block_size, R - 1), &cur_mn, &cur_mx);
            
            if (cur_mn != -1) {
                max_diff = max(max_diff, cur_mn - last_val);
                last_val = cur_mx;
            }
        }
        max_diff = max(max_diff, R - last_val);
        return max_diff;
    }
}

• Subtask 1: 30 / 30
• Subtask 2: 70 / 70