#include "minecraft.h"
#include <iostream>
#include <vector>
#include <queue>
using namespace std;

struct edge {
    int ver;
    long long dist;
    const bool operator<(const edge &a) const {
        return dist>a.dist;
    }
};

long long dist[200000];
int start[200000];
vector<edge> v[200000];

vector<int> portals(int n, int k) {
    int curr = 1;
    vector<int> res;
    for(int i = 1; i <= k; i++) {
        int l = curr, r = n, mid, ans=-1;
        while(l<=r) {
            mid=(l+r)/2;
            if(find_portals(curr, mid)>=1) {
                ans=mid;
                r = mid - 1;
            }
            else {
                l = mid + 1;
            }
        }
        res.push_back(ans);
        curr = ans + 1;
    }
    return res;
}

pair<int,int> minimal_danger(int n, vector<pair<int, pair<int,int>>> paths, vector<int> portals, vector<int> fortresses) {
    for(auto x : paths) {
        v[x.second.first].push_back({x.second.second, x.first});
        v[x.second.second].push_back({x.second.first, x.first});
    }
    for(int i = 1; i <= n; i++) dist[i]=4e18;
    priority_queue<edge> q;
    for(auto x : portals) {
        q.push({x, 0});
        dist[x]=0;
        start[x]=x;
    }
    while(!q.empty()) {
        edge w = q.top();
        q.pop();
        for(auto x : v[w.ver]) {
            if(dist[x.ver]>dist[w.ver]+x.dist) {
                dist[x.ver]=dist[w.ver]+x.dist;
                start[x.ver]=start[w.ver];
                x.dist=dist[x.ver];
                q.push(x);
            }
        }
    }
    int mnFortress = fortresses[0];
    for(auto x : fortresses) {
        if(dist[x]<dist[mnFortress]) {
            mnFortress = x;
        }
    }
    return {start[mnFortress], mnFortress};
}

pair<int,int> find_end_portal(int L) {
    pair<int,int> tl={1,1}, br={L,L}, mid;
    while(tl.first<=br.first || tl.second<=br.second) {
        mid={(tl.first+br.first)/2, (tl.second+br.second)/2};
        string res = throw_eye(mid);
        if(res=="NONE") {
            break;
        }
        if(res=="NE" || res=="E" || res=="SE") {
            tl.first=mid.first+1;
        }
        else if(res=="NW" || res=="W" || res=="SW") {
            br.first=mid.first-1;
        }
        else {
            tl.first = mid.first;
            br.first = mid.first;
        }

        if(res=="NE"||res=="N"||res=="NW") {
            tl.second=mid.second+1;
        }
        else if(res=="SE"||res=="S"||res=="SW") {
            br.second=mid.second-1;
        }
        else {
            tl.second = mid.second;
            br.second = mid.second;
        }
    }
    return mid;
}
