Submission #1103747

#	Time	Username	Problem	Language	Result	Execution time	Memory
1103747		ShadowShark	Naval battle (CEOI24_battle)	C++17	6 / 100	686 ms	148988 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define piii pair<int, pair<int, int>>

const int maxN = 2e5 + 5;
vector<int> hor, ver, dg1, dg2;
set<pair<int, int>> H[maxN], V[maxN], D1[maxN], D2[maxN];
struct point {
    int x, y; char type;
} p[maxN];
int tick[maxN];

priority_queue<piii, vector<piii>, greater<piii>> pq;

void del(int id) {
    /// remove D1
    int pos = lower_bound(dg1.begin(), dg1.end(), p[id].x - p[id].y) - dg1.begin();
    D1[pos].erase(D1[pos].find({p[id].x, id}));
    auto it = D1[pos].lower_bound({p[id].x, id});
    if (it != D1[pos].end()) {
        auto it2 = it; it2--;
        auto [num1, id1] = *it2; auto [num2, id2] = *it;
        char t1 = p[id1].type, t2 = p[id2].type;

        if ((t1 == 'E' && t2 == 'N') || (t1 == 'S' && t2 == 'W'))
            pq.push({num2 - num1, {id1, id2}});
    }

    /// remove D2
    pos = lower_bound(dg2.begin(), dg2.end(), p[id].x + p[id].y) - dg2.begin();
    D2[pos].erase(D2[pos].find({p[id].x, id}));
    it = D2[pos].lower_bound({p[id].x, id});
    if (it != D2[pos].end()) {
        auto it2 = it; it2--;
        auto [num1, id1] = *it2; auto[num2, id2] = *it;
        char t1 = p[id1].type, t2 = p[id2].type;

        if ((t1 == 'E' && t2 == 'S') || (t1 == 'N' && t2 == 'W'))
            pq.push({num2 - num1, {id1, id2}});
    }

    /// remove H or V
    if (p[id].type == 'N' || p[id].type == 'S') {
        int pos = lower_bound(hor.begin(), hor.end(), p[id].y) - hor.begin();
        H[pos].erase(H[pos].find({p[id].x, id}));
        auto it = H[pos].lower_bound({p[id].x, id});
        if (it != H[pos].end()) {
            auto it2 = it; it2--;
            auto [num1, id1] = *it2; auto [num2, id2] = *it;
            char t1 = p[id1].type, t2 = p[id2].type;

            if (t1 != t2) pq.push({num2 - num1, {id1, id2}});
        }
    }
    else {
        int pos = lower_bound(ver.begin(), ver.end(), p[id].x) - ver.begin();
        V[pos].erase(V[pos].find({p[id].y, id}));
        auto it = V[pos].lower_bound({p[id].y, id});
        if (it != V[pos].end()) {
            auto it2 = it; it2--;
            auto [num1, id1] = *it2; auto [num2, id2] = *it;
            char t1 = p[id1].type, t2 = p[id2].type;

            if (t1 != t2) pq.push({num2 - num1, {id1, id2}});
        }
    }
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    int n;
    cin >> n;

    for (int i = 1; i <= n; i++) {
        cin >> p[i].x >> p[i].y >> p[i].type;
        if (p[i].type == 'S' || p[i].type == 'N') hor.push_back(p[i].y); /// -
        if (p[i].type == 'W' || p[i].type == 'E') ver.push_back(p[i].x); /// |
        dg1.push_back(p[i].x - p[i].y);
        dg2.push_back(p[i].x + p[i].y);
    }

    if (hor.size() > 0) {sort(hor.begin(), hor.end()); hor.erase(unique(hor.begin(), hor.end()), hor.end());};
    if (ver.size() > 0) {sort(ver.begin(), ver.end()); ver.erase(unique(ver.begin(), ver.end()), ver.end());};
    sort(dg1.begin(), dg1.end()); dg1.erase(unique(dg1.begin(), dg1.end()), dg1.end());
    sort(dg2.begin(), dg2.end()); dg2.erase(unique(dg2.begin(), dg2.end()), dg2.end());

    for (int i = 1; i <= n; i++) {
        int pos;

        /// hor
        if (p[i].type == 'N' || p[i].type == 'S') {
            pos = lower_bound(hor.begin(), hor.end(), p[i].y) - hor.begin();
            H[pos].insert({p[i].x, i});
        }
        else {
            /// ver
            pos = lower_bound(ver.begin(), ver.end(), p[i].x) - ver.begin();
            V[pos].insert({p[i].y, i});
        }

        /// dg1
        pos = lower_bound(dg1.begin(), dg1.end(), p[i].x - p[i].y) - dg1.begin();
        D1[pos].insert({p[i].x, i});

        /// dg2
        pos = lower_bound(dg2.begin(), dg2.end(), p[i].x + p[i].y) - dg2.begin();
        D2[pos].insert({p[i].x, i});
    }

    /// Consider d2
    for (int i = 0; i < dg2.size(); i++) {
        auto it = D2[i].begin(); it++;
        while (it != D2[i].end()) {
            auto it2 = it; it2--;
            auto [num1, id1] = *it2; auto [num2, id2] = *it;
            char t1 = p[id1].type, t2 = p[id2].type;

            if ((t1 == 'E' && t2 == 'S') || (t1 == 'N' && t2 == 'W'))
                pq.push({num2 - num1, {id1, id2}});
            it++;
        }
    }


    /// Consider d1
    for (int i = 0; i < dg1.size(); i++) {
        auto it = D1[i].begin(); it++;
        for ( ; it != D1[i].end(); it++) {
            auto it2 = it; it2--;
            auto [num1, id1] = *it2; auto [num2, id2] = *it;
            char t1 = p[id1].type, t2 = p[id2].type;

            if ((t1 == 'E' && t2 == 'N') || (t1 == 'S' && t2 == 'W'))
                pq.push({num2 - num1, {id1, id2}});
        }
    }

    /// Consider hor
    for (int i = 0; i < hor.size(); i++) {
        auto it = H[i].begin(); it++;
        for ( ; it != H[i].end(); it++) {
            auto it2 = it; it2--;
            auto [num1, id1] = *it2; auto [num2, id2] = *it;
            char t1 = p[id1].type, t2 = p[id2].type;

            if (t1 != t2) pq.push({num2 - num1, {id1, id2}});
        }
    }

    /// Consider ver
    for (int i = 0; i < ver.size(); i++) {
        auto it = V[i].begin(); it++;
        for ( ; it != V[i].end(); it++) {
            auto it2 = it; it2--;
            auto [num1, id1] = *it2; auto [num2, id2] = *it;
            char t1 = p[id1].type, t2 = p[id2].type;

            if (t1 != t2) pq.push({num2 - num1, {id1, id2}});
        }
    }

    while (pq.size() > 0) {
        auto it = pq.top(); pq.pop();

        int hel = it.first, x = it.second.first, y = it.second.second;

        if (tick[x] && tick[y]) continue;
        if (!tick[x] && !tick[y]) {
            tick[x] = tick[y] = hel;
            del(x); del(y);
            continue;
        }

        if (tick[x] == hel) {
            tick[y] = hel;
            del(y);
            continue;
        }

        if (tick[y] == hel) {
            tick[x] = hel;
            del(x);
            continue;
        }
    }

    vector<int> res; res.clear();
    for (int i = 1; i <= n; i++)
        if (!tick[i]) res.push_back(i);

    if (res.size() > 0) {
        for (auto v: res)
            cout << v << '\n';
        return 0;
    }

    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:112:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  112 |     for (int i = 0; i < dg2.size(); i++) {
      |                     ~~^~~~~~~~~~~~
Main.cpp:127:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  127 |     for (int i = 0; i < dg1.size(); i++) {
      |                     ~~^~~~~~~~~~~~
Main.cpp:140:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  140 |     for (int i = 0; i < hor.size(); i++) {
      |                     ~~^~~~~~~~~~~~
Main.cpp:152:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  152 |     for (int i = 0; i < ver.size(); i++) {
      |                     ~~^~~~~~~~~~~~

• Subtask 0: 0 / 0
• Subtask 1: 6 / 6
• Subtask 2: 0 / 12
• Subtask 3: 0 / 8
• Subtask 4: 0 / 11
• Subtask 5: 0 / 9
• Subtask 6: 0 / 30
• Subtask 7: 0 / 24