Submission #1103775

#	Time	Username	Problem	Language	Result	Execution time	Memory
1103775		ShadowShark	Naval battle (CEOI24_battle)	C++17	100 / 100	878 ms	94248 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_en, dg1_sw, dg2_es, dg2_nw;
set<pair<int, int>> H[maxN], V[maxN], D1_EN[maxN], D1_SW[maxN], D2_ES[maxN], D2_NW[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) {
    int pos;

    /// remove D1_EN
    if (p[id].type == 'E' || p[id].type == 'N') {
        pos = lower_bound(dg1_en.begin(), dg1_en.end(), p[id].x - p[id].y) - dg1_en.begin();
        D1_EN[pos].erase(D1_EN[pos].find({p[id].x, id}));
        auto it = D1_EN[pos].lower_bound({p[id].x, id});
        if (it != D1_EN[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') pq.push({num2 - num1, {id1, id2}});
        }
    }
    else {
        /// remove D1_SW
        pos = lower_bound(dg1_sw.begin(), dg1_sw.end(), p[id].x - p[id].y) - dg1_sw.begin();
        D1_SW[pos].erase(D1_SW[pos].find({p[id].x, id}));
        auto it = D1_SW[pos].lower_bound({p[id].x, id});
        if (it != D1_SW[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 == 'S' && t2 == 'W') pq.push({num2 - num1, {id1, id2}});
        }
    }


    /// remove D2_ES
    if (p[id].type == 'E' || p[id].type == 'S') {
        pos = lower_bound(dg2_es.begin(), dg2_es.end(), p[id].x + p[id].y) - dg2_es.begin();
        D2_ES[pos].erase(D2_ES[pos].find({p[id].x, id}));
        auto it = D2_ES[pos].lower_bound({p[id].x, id});
        if (it != D2_ES[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') pq.push({num2 - num1, {id1, id2}});
        }
    }
    else {
        pos = lower_bound(dg2_nw.begin(), dg2_nw.end(), p[id].x + p[id].y) - dg2_nw.begin();
        D2_NW[pos].erase(D2_NW[pos].find({p[id].x, id}));
        auto it = D2_NW[pos].lower_bound({p[id].x, id});
        if (it != D2_NW[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 == 'N' && t2 == 'W') pq.push({num2 - num1, {id1, id2}});
        }
    }


    /// remove H or V
    if (p[id].type == 'E' || p[id].type == 'W') {
        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 == 'E' && t2 == 'W') pq.push({(num2 - num1) / 2, {id1, id2}});
        }
    }
    else {
        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 == 'S' && t2 == 'N') pq.push({(num2 - num1) / 2, {id1, id2}});
        }
    }
}

void compress(vector<int> &a) {
    if (a.size() > 0) {
        sort(a.begin(), a.end());
        a.erase(unique(a.begin(), a.end()), a.end());
    }
}

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 == 'E' || p[i].type == 'W') hor.push_back(p[i].y); /// -
            else ver.push_back(p[i].x); /// |

        if (p[i].type == 'E' || p[i].type == 'N') dg1_en.push_back(p[i].x - p[i].y);
            else dg1_sw.push_back(p[i].x - p[i].y);

        if (p[i].type == 'E' || p[i].type == 'S') dg2_es.push_back(p[i].x + p[i].y);
            else dg2_nw.push_back(p[i].x + p[i].y);
    }

    compress(hor); compress(ver);
    compress(dg1_en); compress(dg1_sw);
    compress(dg2_es); compress(dg2_nw);

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

        /// hor
        if (p[i].type == 'E' || p[i].type == 'W') {
            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
        if (p[i].type == 'E' || p[i].type == 'N') {
            pos = lower_bound(dg1_en.begin(), dg1_en.end(), p[i].x - p[i].y) - dg1_en.begin();
            D1_EN[pos].insert({p[i].x, i});
        }
        else {
            pos = lower_bound(dg1_sw.begin(), dg1_sw.end(), p[i].x - p[i].y) - dg1_sw.begin();
            D1_SW[pos].insert({p[i].x, i});
        }

        /// dg2
        if (p[i].type == 'E' || p[i].type == 'S') {
            pos = lower_bound(dg2_es.begin(), dg2_es.end(), p[i].x + p[i].y) - dg2_es.begin();
            D2_ES[pos].insert({p[i].x, i});
        }
        else {
            pos = lower_bound(dg2_nw.begin(), dg2_nw.end(), p[i].x + p[i].y) - dg2_nw.begin();
            D2_NW[pos].insert({p[i].x, i});
        }
    }

    /// Consider d2
    for (int i = 0; i < dg2_es.size(); i++) {
        auto it = D2_ES[i].begin(); it++;
        while (it != D2_ES[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') pq.push({num2 - num1, {id1, id2}});
            it++;
        }
    }

    for (int i = 0; i < dg2_nw.size(); i++) {
        auto it = D2_NW[i].begin(); it++;
        while (it != D2_NW[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 == 'N' && t2 == 'W') pq.push({num2 - num1, {id1, id2}});
            it++;
        }
    }

    /// Consider d1
    for (int i = 0; i < dg1_en.size(); i++) {
        auto it = D1_EN[i].begin(); it++;
        for ( ; it != D1_EN[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') pq.push({num2 - num1, {id1, id2}});
        }
    }

    for (int i = 0; i < dg1_sw.size(); i++) {
        auto it = D1_SW[i].begin(); it++;
        for ( ; it != D1_SW[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 == '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 == 'E' && t2 == 'W') pq.push({(num2 - num1) / 2, {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 == 'S' && t2 == 'N') pq.push({(num2 - num1) / 2, {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);

    for (auto v: res)
        cout << v << '\n';

    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:165:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  165 |     for (int i = 0; i < dg2_es.size(); i++) {
      |                     ~~^~~~~~~~~~~~~~~
Main.cpp:177:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  177 |     for (int i = 0; i < dg2_nw.size(); i++) {
      |                     ~~^~~~~~~~~~~~~~~
Main.cpp:190:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  190 |     for (int i = 0; i < dg1_en.size(); i++) {
      |                     ~~^~~~~~~~~~~~~~~
Main.cpp:201:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  201 |     for (int i = 0; i < dg1_sw.size(); i++) {
      |                     ~~^~~~~~~~~~~~~~~
Main.cpp:213:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  213 |     for (int i = 0; i < hor.size(); i++) {
      |                     ~~^~~~~~~~~~~~
Main.cpp:225:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  225 |     for (int i = 0; i < ver.size(); i++) {
      |                     ~~^~~~~~~~~~~~

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