#include "minecraft.h"
#include <bits/stdc++.h>
#define fir first
#define sec second
using namespace std;
vector<long long> divide(long long l,long long r,long long cnt)
{
    if(cnt==0) return{};
    if(l==r)
    {
        return {l};
    }
    long long m=(l+r)/2;
    long long br=find_portals(l,m);
    vector<long long> v1,v2;
    v1=divide(l,m,br);
    v2=divide(m+1,r,cnt-br);
    vector<long long> ans=v1;
    for(long long x:v2)
    {
        ans.push_back(x);
    }
    return ans;
}
std::vector<long long> portals(long long N, long long K)
{
    return divide(1,N,K);
}
struct cell
{
    long long to,cost;
    cell(){};
    cell(long long _to,long long _cost)
    {
        to=_to;cost=_cost;
    };
    bool operator<(const cell& c)const
    {
        return cost>c.cost;
    }
};
const long long maxn=1e5+1000;
vector<cell> v[maxn];
long long from[maxn];
long long d[maxn];
void dijkstra(vector<long long>portal)
{
    for(long long i=1;i<maxn;i++)
    {
        d[i]=1e9;
    }
    priority_queue<cell> q;
    for(long long x:portal)
    {
        d[x]=0;
        q.push({x,0});
        from[x]=x;
    }
    while(q.size())
    {
        cell w=q.top();
        q.pop();
        if(d[w.to]<w.cost) continue;
        for(cell nb:v[w.to])
        {
            if(d[nb.to]>nb.cost+d[w.to])
            {
                d[nb.to]=nb.cost,d[w.to];
                from[nb.to]=from[w.to];
                q.push({nb.to,d[nb.to]});
            }
        }
    }
}
std::pair<long long, long long> minimal_danger(long long N, std::vector<std::pair<long long, std::pair<long long, long long>>> paths, std::vector<long long> portals, std::vector<long long> fortresses)
{
    for(pair<long long,pair<long long,long long>> p:paths)
    {
        v[p.sec.fir].push_back({p.sec.sec,p.fir});
        v[p.sec.sec].push_back({p.sec.fir,p.fir});
    }
    dijkstra(portals);
    long long dan=1e9,por,fort;
    for(long long x:fortresses)
    {
        if(d[x]<dan)
        {
            fort=x;
            por=from[x];
            dan=d[x];
        }
    }
    return {por,fort};
}
pair<long long,long long> find_end_portal(long long L)
{
    long long xmin=1,xmax=L;
    long long ymin=1,ymax=L;
    while(true)
    {
        long long mx=(xmin+xmax)/2;
        long long my=(ymin+ymax)/2;
        string s=throw_eye({mx,my});
        if(s=="NONE")
        {
            return {mx,my};
        }
        else if(s=="NE")
        {
            xmin=mx+1;
            ymin=my+1;
        }
        else if(s=="NW")
        {
            xmax=mx-1;
            ymin=my+1;
        }
        else if(s=="SE")
        {
            xmin=mx+1;
            ymax=my-1;
        }
        else if(s=="SW")
        {
            xmax=mx-1;
            ymax=my-1;
        }
        else if(s=="N")
        {
            xmin=mx;
            xmax=mx;
            ymin=my+1;
        }
        else if(s=="S")
        {
            xmin=mx;
            xmax=mx;
            ymax=my-1;
        }
        else if(s=="E")
        {
            xmin=mx+1;
            ymin=my;
            ymax=my;
        }
        else if(s=="W")
        {
            xmax=mx-1;
            ymin=my;
            ymax=my;
        }
    }
}
