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

int uniK;

void fart(vector<int>& ans, int ll, int rr) {
  ///  cout << "Interval: " << ll << " " << rr << endl;
    int idx = ll - 1, cnt = 0;
    while(idx + 1 <= rr) {
        if(uniK == 0) {
          ///  cout << idx + 1 << " " << rr << endl;
            break;
        }
        if(find_portals(idx + 1, rr) == 0) {
            break;
        }
        int l = idx + 1, r = rr, mid, jk = idx + 1;
        idx = INT_MAX;
        while(l <= r) {
            mid = (l + r) >> 1;
            if(find_portals(jk, mid) >= 1) {
                idx = mid;
                r = mid - 1;
            }
            else {
                l = mid + 1;
            }
        }
        if(idx == INT_MAX) {
            break;
        }
        ans.push_back(idx);
        uniK--;
      ///  cout << idx << endl;
    }
}

vector<int> portals(int n, int k) {
    int sq, i = 1;
    uniK = k;
    vector<int> ans;
    while(i <= n) {
        if(ans.size() == k) break;
        double CheatMultiplier = 1.435;
        int fuh = k - ans.size();
        int ert = CheatMultiplier * fuh;
        int sq = (n - i + 1) / ert;
        fart(ans, i, min(i + sq - 1, n));
        i = min(i + sq - 1, n) + 1;
    }
    return ans;
}

typedef long long int LL;

pair<int, int> minimal_danger(int N, vector<pair<int, pair<int, int>>> paths,
                                   vector<int> portals, vector<int> fortresses) {
    vector<pair<int, LL>> to[N + 1];
    for(auto it : paths) {
        to[it.second.first].push_back({it.second.second, (LL)it.first});
        to[it.second.second].push_back({it.second.first, (LL)it.first});
    }
    vector<LL> dist(N + 1);
    for(int i = 0; i < dist.size(); i++) {
        dist[i] = LLONG_MAX;
    }
    priority_queue<pair<LL, LL>> pq;
    pq.push({0, fortresses[0]});
    dist[fortresses[0]] = 0;
    while(!pq.empty()) {
        auto [d, curr] = pq.top();
        pq.pop();
        d = -d;
        for(auto [next, w] : to[curr]) {
            if(dist[next] > dist[curr] + w) {
                dist[next] = dist[curr] + w;
                pq.push({-dist[next], next});
            }
        }
    }
    int ans = portals[0];
    for(int i : portals) {
     ///   cout << i << " " << dist[i] << endl;
        if(dist[ans] > dist[i] && i != fortresses[0]) {

            ans = i;
        }
    }
    return {ans, fortresses[0]};
}

pair<int, int> find_end_portal(int L) {
    return {1, 1};
}










