#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.397;
        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;
}

std::pair<int, int> minimal_danger(int N, std::vector<std::pair<int, std::pair<int, int>>> paths,
                                   std::vector<int> portals, std::vector<int> fortresses) {
    return {0, 0};
}

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