<div class="solution-view">
    <div class="row">
        <div class="col-md-6">
            <p>提交时间：2026-04-18 21:29:34</p>
        </div>
        <div class="col-md-6">
            <p>运行 ID: <a href="/solution/detail?id=41362">41362</a></p>
        </div>
    </div>
    <div class="pre"><p>#pragma GCC optimize(&quot;Ofast,no-stack-protector,inline,fast-math,unroll-loops,omit-frame-pointer&quot;)
#define NDEBUG

#include &lt;algorithm&gt;
#include &lt;iostream&gt;
#include &lt;iterator&gt;
#include &lt;queue&gt;
#include &lt;set&gt;
#include &lt;tuple&gt;
#include &lt;vector&gt;

using namespace std;
using i64 = long long;
using Ship = tuple&lt;int, int, char&gt;;

constexpr int INF = 0x7f7f7f7f;

vector&lt;Ship&gt; ships;

#pragma region compare
// (x + y, x)
struct Cmp1 {
    bool operator()(int i, int j) const
    {
        int x1 = get&lt;0&gt;(ships[i]), y1 = get&lt;1&gt;(ships[i]), x2 = get&lt;0&gt;(ships[j]), y2 = get&lt;1&gt;(ships[j]);
        return x1 + y1 == x2 + y2 ? x1 &lt; x2 : x1 + y1 &lt; x2 + y2;
    }
};

// (x - y, x)
struct Cmp2 {
    bool operator()(int i, int j) const
    {
        int x1 = get&lt;0&gt;(ships[i]), y1 = get&lt;1&gt;(ships[i]), x2 = get&lt;0&gt;(ships[j]), y2 = get&lt;1&gt;(ships[j]);
        return x1 - y1 == x2 - y2 ? x1 &lt; x2 : x1 - y1 &lt; x2 - y2;
    }
};

// (y, x)
struct Cmp3 {
    bool operator()(int i, int j) const
    {
        int x1 = get&lt;0&gt;(ships[i]), y1 = get&lt;1&gt;(ships[i]), x2 = get&lt;0&gt;(ships[j]), y2 = get&lt;1&gt;(ships[j]);
        return y1 == y2 ? x1 &lt; x2 : y1 &lt; y2;
    }
};

// (x, y)
struct Cmp4 {
    bool operator()(int i, int j) const
    {
        int x1 = get&lt;0&gt;(ships[i]), y1 = get&lt;1&gt;(ships[i]), x2 = get&lt;0&gt;(ships[j]), y2 = get&lt;1&gt;(ships[j]);
        return x1 == x2 ? y1 &lt; y2 : x1 &lt; x2;
    }
};
#pragma endregion

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int N;
    cin &gt;&gt; N;

    vector&lt;int&gt; ship_S, ship_W, ship_E, ship_N;
    for (int i = 0; i &lt; N; ++i) {
        int x, y;
        char d;
        cin &gt;&gt; x &gt;&gt; y &gt;&gt; d;
        ships.push_back(make_tuple(x, y, d));
        if (d == &#039;S&#039;)
            ship_S.push_back(i);
        else if (d == &#039;N&#039;)
            ship_N.push_back(i);
        else if (d == &#039;E&#039;)
            ship_E.push_back(i);
        else if (d == &#039;W&#039;)
            ship_W.push_back(i);
    }

    priority_queue&lt;tuple&lt;int, int, int&gt;&gt; events;

#pragma region initialize
    int lst = -1;
    set&lt;int, Cmp1&gt; SE;
    vector&lt;int&gt; del_SE;
    SE.insert(ship_S.begin(), ship_S.end());
    SE.insert(ship_E.begin(), ship_E.end());
    for (int i : SE) {
        if (lst == -1) {
            lst = i;
            continue;
        }
        int x1 = get&lt;0&gt;(ships[lst]), y1 = get&lt;1&gt;(ships[lst]);
        char d1 = get&lt;2&gt;(ships[lst]);
        int x2 = get&lt;0&gt;(ships[i]), y2 = get&lt;1&gt;(ships[i]);
        char d2 = get&lt;2&gt;(ships[i]);
        if (d1 == &#039;E&#039; &amp;&amp; d2 == &#039;S&#039; &amp;&amp; x1 + y1 == x2 + y2)
            events.emplace(x1 - x2, i, lst);
        lst = i;
    }

    lst = -1;
    set&lt;int, Cmp1&gt; NW;
    vector&lt;int&gt; del_NW;
    NW.insert(ship_N.begin(), ship_N.end());
    NW.insert(ship_W.begin(), ship_W.end());
    for (int i : NW) {
        if (lst == -1) {
            lst = i;
            continue;
        }
        int x1 = get&lt;0&gt;(ships[lst]), y1 = get&lt;1&gt;(ships[lst]);
        char d1 = get&lt;2&gt;(ships[lst]);
        int x2 = get&lt;0&gt;(ships[i]), y2 = get&lt;1&gt;(ships[i]);
        char d2 = get&lt;2&gt;(ships[i]);
        if (d1 == &#039;N&#039; &amp;&amp; d2 == &#039;W&#039; &amp;&amp; x1 + y1 == x2 + y2)
            events.emplace(x1 - x2, i, lst);
        lst = i;
    }

    lst = -1;
    set&lt;int, Cmp2&gt; NE;
    vector&lt;int&gt; del_NE;
    NE.insert(ship_N.begin(), ship_N.end());
    NE.insert(ship_E.begin(), ship_E.end());
    for (int i : NE) {
        if (lst == -1) {
            lst = i;
            continue;
        }
        int x1 = get&lt;0&gt;(ships[lst]), y1 = get&lt;1&gt;(ships[lst]);
        char d1 = get&lt;2&gt;(ships[lst]);
        int x2 = get&lt;0&gt;(ships[i]), y2 = get&lt;1&gt;(ships[i]);
        char d2 = get&lt;2&gt;(ships[i]);
        if (d1 == &#039;E&#039; &amp;&amp; d2 == &#039;N&#039; &amp;&amp; x1 - y1 == x2 - y2)
            events.emplace(x1 - x2, i, lst);
        lst = i;
    }

    lst = -1;
    set&lt;int, Cmp2&gt; SW;
    vector&lt;int&gt; del_SW;
    SW.insert(ship_S.begin(), ship_S.end());
    SW.insert(ship_W.begin(), ship_W.end());
    for (int i : SW) {
        if (lst == -1) {
            lst = i;
            continue;
        }
        int x1 = get&lt;0&gt;(ships[lst]), y1 = get&lt;1&gt;(ships[lst]);
        char d1 = get&lt;2&gt;(ships[lst]);
        int x2 = get&lt;0&gt;(ships[i]), y2 = get&lt;1&gt;(ships[i]);
        char d2 = get&lt;2&gt;(ships[i]);
        if (d1 == &#039;S&#039; &amp;&amp; d2 == &#039;W&#039; &amp;&amp; x1 - y1 == x2 - y2)
            events.emplace(x1 - x2, i, lst);
        lst = i;
    }

    lst = -1;
    set&lt;int, Cmp3&gt; EW;
    vector&lt;int&gt; del_EW;
    EW.insert(ship_W.begin(), ship_W.end());
    EW.insert(ship_E.begin(), ship_E.end());
    for (int i : EW) {
        if (lst == -1) {
            lst = i;
            continue;
        }
        int x1 = get&lt;0&gt;(ships[lst]), y1 = get&lt;1&gt;(ships[lst]);
        char d1 = get&lt;2&gt;(ships[lst]);
        int x2 = get&lt;0&gt;(ships[i]), y2 = get&lt;1&gt;(ships[i]);
        char d2 = get&lt;2&gt;(ships[i]);
        if (d1 == &#039;E&#039; &amp;&amp; d2 == &#039;W&#039; &amp;&amp; y1 == y2)
            events.emplace((x1 - x2) &gt;&gt; 1, i, lst);
        lst = i;
    }

    lst = -1;
    set&lt;int, Cmp4&gt; SN;
    vector&lt;int&gt; del_SN;
    SN.insert(ship_S.begin(), ship_S.end());
    SN.insert(ship_N.begin(), ship_N.end());
    for (int i : SN) {
        if (lst == -1) {
            lst = i;
            continue;
        }
        int x1 = get&lt;0&gt;(ships[lst]), y1 = get&lt;1&gt;(ships[lst]);
        char d1 = get&lt;2&gt;(ships[lst]);
        int x2 = get&lt;0&gt;(ships[i]), y2 = get&lt;1&gt;(ships[i]);
        char d2 = get&lt;2&gt;(ships[i]);
        if (d1 == &#039;S&#039; &amp;&amp; d2 == &#039;N&#039; &amp;&amp; x1 == x2)
            events.emplace((y1 - y2) &gt;&gt; 1, i, lst);
        lst = i;
    }
#pragma endregion

    auto erase_all = [&amp;]() {
        int l = -1, r = -1;
        sort(del_EW.begin(), del_EW.end(), Cmp3());
        for (int x : del_EW) {
            set&lt;int, Cmp3&gt;::iterator itr = EW.find(x);
            if (itr == EW.end())
                continue;
            if (itr == EW.begin()) {
                EW.erase(itr);
                continue;
            } else if (next(itr) == EW.end()) {
                EW.erase(itr);
                r = -1;
                continue;
            }

            int pre = *prev(itr);
            if (pre != l) {
                if (l != -1 &amp;&amp; r != -1) {
                    int x1 = get&lt;0&gt;(ships[l]), y1 = get&lt;1&gt;(ships[l]);
                    char d1 = get&lt;2&gt;(ships[l]);
                    int x2 = get&lt;0&gt;(ships[r]), y2 = get&lt;1&gt;(ships[r]);
                    char d2 = get&lt;2&gt;(ships[r]);
                    if (d1 == &#039;E&#039; &amp;&amp; d2 == &#039;W&#039; &amp;&amp; y1 == y2)
                        events.emplace((x1 - x2) &gt;&gt; 1, l, r);
                }
                l = pre;
            }
            r = *next(itr);
            EW.erase(itr);
        }
        if (l != -1 &amp;&amp; r != -1) {
            int x1 = get&lt;0&gt;(ships[l]), y1 = get&lt;1&gt;(ships[l]);
            char d1 = get&lt;2&gt;(ships[l]);
            int x2 = get&lt;0&gt;(ships[r]), y2 = get&lt;1&gt;(ships[r]);
            char d2 = get&lt;2&gt;(ships[r]);
            if (d1 == &#039;E&#039; &amp;&amp; d2 == &#039;W&#039; &amp;&amp; y1 == y2)
                events.emplace((x1 - x2) &gt;&gt; 1, l, r);
        }
        del_EW.clear();

        l = -1;
        r = -1;
        sort(del_NE.begin(), del_NE.end(), Cmp2());
        for (int x : del_NE) {
            set&lt;int, Cmp2&gt;::iterator itr = NE.find(x);
            if (itr == NE.end())
                continue;
            if (itr == NE.begin()) {
                NE.erase(itr);
                continue;
            } else if (next(itr) == NE.end()) {
                NE.erase(itr);
                r = -1;
                continue;
            }

            int pre = *prev(itr);
            if (pre != l) {
                if (l != -1 &amp;&amp; r != -1) {
                    int x1 = get&lt;0&gt;(ships[l]), y1 = get&lt;1&gt;(ships[l]);
                    char d1 = get&lt;2&gt;(ships[l]);
                    int x2 = get&lt;0&gt;(ships[r]), y2 = get&lt;1&gt;(ships[r]);
                    char d2 = get&lt;2&gt;(ships[r]);
                    if (d1 == &#039;E&#039; &amp;&amp; d2 == &#039;N&#039; &amp;&amp; x1 - y1 == x2 - y2)
                        events.emplace(x1 - x2, l, r);
                }
                l = pre;
            }
            r = *next(itr);
            NE.erase(itr);
        }
        if (l != -1 &amp;&amp; r != -1) {
            int x1 = get&lt;0&gt;(ships[l]), y1 = get&lt;1&gt;(ships[l]);
            char d1 = get&lt;2&gt;(ships[l]);
            int x2 = get&lt;0&gt;(ships[r]), y2 = get&lt;1&gt;(ships[r]);
            char d2 = get&lt;2&gt;(ships[r]);
            if (d1 == &#039;E&#039; &amp;&amp; d2 == &#039;N&#039; &amp;&amp; x1 - y1 == x2 - y2)
                events.emplace(x1 - x2, l, r);
        }
        del_NE.clear();

        l = -1;
        r = -1;
        sort(del_NW.begin(), del_NW.end(), Cmp1());
        for (int x : del_NW) {
            set&lt;int, Cmp1&gt;::iterator itr = NW.find(x);
            if (itr == NW.end())
                continue;
            if (itr == NW.begin()) {
                NW.erase(itr);
                continue;
            } else if (next(itr) == NW.end()) {
                NW.erase(itr);
                r = -1;
                continue;
            }

            int pre = *prev(itr);
            if (pre != l) {
                if (l != -1 &amp;&amp; r != -1) {
                    int x1 = get&lt;0&gt;(ships[l]), y1 = get&lt;1&gt;(ships[l]);
                    char d1 = get&lt;2&gt;(ships[l]);
                    int x2 = get&lt;0&gt;(ships[r]), y2 = get&lt;1&gt;(ships[r]);
                    char d2 = get&lt;2&gt;(ships[r]);
                    if (d1 == &#039;N&#039; &amp;&amp; d2 == &#039;W&#039; &amp;&amp; x1 + y1 == x2 + y2)
                        events.emplace(x1 - x2, l, r);
                }
                l = pre;
            }
            r = *next(itr);
            NW.erase(itr);
        }
        if (l != -1 &amp;&amp; r != -1) {
            int x1 = get&lt;0&gt;(ships[l]), y1 = get&lt;1&gt;(ships[l]);
            char d1 = get&lt;2&gt;(ships[l]);
            int x2 = get&lt;0&gt;(ships[r]), y2 = get&lt;1&gt;(ships[r]);
            char d2 = get&lt;2&gt;(ships[r]);
            if (d1 == &#039;N&#039; &amp;&amp; d2 == &#039;W&#039; &amp;&amp; x1 + y1 == x2 + y2)
                events.emplace(x1 - x2, l, r);
        }
        del_NW.clear();

        l = -1;
        r = -1;
        sort(del_SE.begin(), del_SE.end(), Cmp1());
        for (int x : del_SE) {
            set&lt;int, Cmp1&gt;::iterator itr = SE.find(x);
            if (itr == SE.end())
                continue;
            if (itr == SE.begin()) {
                SE.erase(itr);
                continue;
            } else if (next(itr) == SE.end()) {
                SE.erase(itr);
                r = -1;
                continue;
            }

            int pre = *prev(itr);
            if (pre != l) {
                if (l != -1 &amp;&amp; r != -1) {
                    int x1 = get&lt;0&gt;(ships[l]), y1 = get&lt;1&gt;(ships[l]);
                    char d1 = get&lt;2&gt;(ships[l]);
                    int x2 = get&lt;0&gt;(ships[r]), y2 = get&lt;1&gt;(ships[r]);
                    char d2 = get&lt;2&gt;(ships[r]);
                    if (d1 == &#039;E&#039; &amp;&amp; d2 == &#039;S&#039; &amp;&amp; x1 + y1 == x2 + y2)
                        events.emplace(x1 - x2, l, r);
                }
                l = pre;
            }
            r = *next(itr);
            SE.erase(itr);
        }
        if (l != -1 &amp;&amp; r != -1) {
            int x1 = get&lt;0&gt;(ships[l]), y1 = get&lt;1&gt;(ships[l]);
            char d1 = get&lt;2&gt;(ships[l]);
            int x2 = get&lt;0&gt;(ships[r]), y2 = get&lt;1&gt;(ships[r]);
            char d2 = get&lt;2&gt;(ships[r]);
            if (d1 == &#039;E&#039; &amp;&amp; d2 == &#039;S&#039; &amp;&amp; x1 + y1 == x2 + y2)
                events.emplace(x1 - x2, l, r);
        }
        del_SE.clear();

        l = -1;
        r = -1;
        sort(del_SN.begin(), del_SN.end(), Cmp4());
        for (int x : del_SN) {
            set&lt;int, Cmp4&gt;::iterator itr = SN.find(x);
            if (itr == SN.end())
                continue;
            if (itr == SN.begin()) {
                SN.erase(itr);
                continue;
            } else if (next(itr) == SN.end()) {
                SN.erase(itr);
                r = -1;
                continue;
            }

            int pre = *prev(itr);
            if (pre != l) {
                if (l != -1 &amp;&amp; r != -1) {
                    int x1 = get&lt;0&gt;(ships[l]), y1 = get&lt;1&gt;(ships[l]);
                    char d1 = get&lt;2&gt;(ships[l]);
                    int x2 = get&lt;0&gt;(ships[r]), y2 = get&lt;1&gt;(ships[r]);
                    char d2 = get&lt;2&gt;(ships[r]);
                    if (d1 == &#039;S&#039; &amp;&amp; d2 == &#039;N&#039; &amp;&amp; x1 == x2)
                        events.emplace((y1 - y2) &gt;&gt; 1, l, r);
                }
                l = pre;
            }
            r = *next(itr);
            SN.erase(itr);
        }
        if (l != -1 &amp;&amp; r != -1) {
            int x1 = get&lt;0&gt;(ships[l]), y1 = get&lt;1&gt;(ships[l]);
            char d1 = get&lt;2&gt;(ships[l]);
            int x2 = get&lt;0&gt;(ships[r]), y2 = get&lt;1&gt;(ships[r]);
            char d2 = get&lt;2&gt;(ships[r]);
            if (d1 == &#039;S&#039; &amp;&amp; d2 == &#039;N&#039; &amp;&amp; x1 == x2)
                events.emplace((y1 - y2) &gt;&gt; 1, l, r);
        }
        del_SN.clear();

        l = -1;
        r = -1;
        sort(del_SW.begin(), del_SW.end(), Cmp2());
        for (int x : del_SW) {
            set&lt;int, Cmp2&gt;::iterator itr = SW.find(x);
            if (itr == SW.end())
                continue;
            if (itr == SW.begin()) {
                SW.erase(itr);
                continue;
            } else if (next(itr) == SW.end()) {
                SW.erase(itr);
                r = -1;
                continue;
            }

            int pre = *prev(itr);
            if (pre != l) {
                if (l != -1 &amp;&amp; r != -1) {
                    int x1 = get&lt;0&gt;(ships[l]), y1 = get&lt;1&gt;(ships[l]);
                    char d1 = get&lt;2&gt;(ships[l]);
                    int x2 = get&lt;0&gt;(ships[r]), y2 = get&lt;1&gt;(ships[r]);
                    char d2 = get&lt;2&gt;(ships[r]);
                    if (d1 == &#039;S&#039; &amp;&amp; d2 == &#039;W&#039; &amp;&amp; x1 - y1 == x2 - y2)
                        events.emplace(x1 - x2, l, r);
                }
                l = pre;
            }
            r = *next(itr);
            SW.erase(itr);
        }
        if (l != -1 &amp;&amp; r != -1) {
            int x1 = get&lt;0&gt;(ships[l]), y1 = get&lt;1&gt;(ships[l]);
            char d1 = get&lt;2&gt;(ships[l]);
            int x2 = get&lt;0&gt;(ships[r]), y2 = get&lt;1&gt;(ships[r]);
            char d2 = get&lt;2&gt;(ships[r]);
            if (d1 == &#039;S&#039; &amp;&amp; d2 == &#039;W&#039; &amp;&amp; x1 - y1 == x2 - y2)
                events.emplace(x1 - x2, l, r);
        }
        del_SW.clear();
    };

    vector&lt;int&gt; del(N, INF);
    while (!events.empty()) {
        tuple&lt;int, int, int&gt; e = events.top();
        events.pop();
        int t = -get&lt;0&gt;(e);
        int u = get&lt;1&gt;(e);
        int v = get&lt;2&gt;(e);

        if (del[u] &lt; t || del[v] &lt; t)
            continue;
        del[u] = del[v] = t;

#pragma region update
        char d1 = get&lt;2&gt;(ships[u]), d2 = get&lt;2&gt;(ships[v]);
        if (d1 == &#039;N&#039;) {
            if (d2 == &#039;S&#039;) {
                del_SN.push_back(u);
                del_SN.push_back(v);
                del_NE.push_back(u);
                del_NW.push_back(u);
                del_SE.push_back(v);
                del_SW.push_back(v);
            } else if (d2 == &#039;E&#039;) {
                del_NE.push_back(u);
                del_NE.push_back(v);
                del_NW.push_back(u);
                del_SN.push_back(u);
                del_EW.push_back(v);
                del_SE.push_back(v);
            } else if (d2 == &#039;W&#039;) {
                del_NW.push_back(u);
                del_NW.push_back(v);
                del_NE.push_back(u);
                del_SN.push_back(u);
                del_EW.push_back(v);
                del_SW.push_back(v);
            }
        } else if (d1 == &#039;S&#039;) {
            if (d2 == &#039;N&#039;) {
                del_SN.push_back(u);
                del_SN.push_back(v);
                del_SE.push_back(u);
                del_SW.push_back(u);
                del_NE.push_back(v);
                del_NW.push_back(v);
            } else if (d2 == &#039;E&#039;) {
                del_SE.push_back(u);
                del_SE.push_back(v);
                del_SW.push_back(u);
                del_SN.push_back(u);
                del_EW.push_back(v);
                del_NE.push_back(v);
            } else if (d2 == &#039;W&#039;) {
                del_SW.push_back(u);
                del_SW.push_back(v);
                del_SE.push_back(u);
                del_SN.push_back(u);
                del_EW.push_back(v);
                del_NW.push_back(v);
            }
        } else if (d1 == &#039;E&#039;) {
            if (d2 == &#039;W&#039;) {
                del_EW.push_back(u);
                del_EW.push_back(v);
                del_SE.push_back(u);
                del_NE.push_back(u);
                del_SW.push_back(v);
                del_NW.push_back(v);
            } else if (d2 == &#039;S&#039;) {
                del_SE.push_back(u);
                del_SE.push_back(v);
                del_NE.push_back(u);
                del_EW.push_back(u);
                del_SW.push_back(v);
                del_SN.push_back(v);
            } else if (d2 == &#039;N&#039;) {
                del_NE.push_back(u);
                del_NE.push_back(v);
                del_SE.push_back(u);
                del_EW.push_back(u);
                del_NW.push_back(v);
                del_SN.push_back(v);
            }
        } else if (d1 == &#039;W&#039;) {
            if (d2 == &#039;E&#039;) {
                del_EW.push_back(u);
                del_EW.push_back(v);
                del_NW.push_back(u);
                del_SW.push_back(u);
                del_SE.push_back(v);
                del_NE.push_back(v);
            } else if (d2 == &#039;N&#039;) {
                del_NW.push_back(u);
                del_NW.push_back(v);
                del_SW.push_back(u);
                del_EW.push_back(u);
                del_SN.push_back(v);
                del_NE.push_back(v);
            } else if (d2 == &#039;S&#039;) {
                del_SW.push_back(u);
                del_SW.push_back(v);
                del_NW.push_back(u);
                del_EW.push_back(u);
                del_SE.push_back(v);
                del_SN.push_back(v);
            }
        }
#pragma endregion

        if (events.empty() || get&lt;0&gt;(events.top()) != t)
            erase_all();
    }

    for (int i = 0; i &lt; N; ++i) {
        if (del[i] &gt;= INF)
            cout &lt;&lt; i + 1 &lt;&lt; &#039;\n&#039;;
    }

    return 0;
}
</p></div>
</div>
<script type="text/javascript">
    (function ($) {
        $(document).ready(function () {
            $('.pre p').each(function(i, block) {  // use <pre><p>
                hljs.highlightBlock(block);
            });
        })
    })(jQuery);
</script>