Submission #1196474

#	Time	Username	Problem	Language	Result	Execution time	Memory
1196474		anmattroi	Naval battle (CEOI24_battle)	C++20	37 / 100	744 ms	157492 KiB

Main

#include <bits/stdc++.h>
#define maxn 200005
using namespace std;

enum DIRECTION {
    UP,
    RIGHT,
    DOWN,
    LEFT
};

int n;

struct ship {
    int x, y, dir;
    ship() {}
    ship(int _x, int _y, int _dir) : x(_x), y(_y), dir(_dir) {}
} a[maxn];


namespace verticalCompression {
    int c[maxn], n1 = 0;

    void init() {
        for (int i = 1; i <= n; i++) c[++n1] = a[i].x;
        sort(c + 1, c + n1 + 1);
        n1 = unique(c + 1, c + n1 + 1) - c - 1;
    }

    int get(int x) {
        return lower_bound(c + 1, c + n1 + 1, x) - c;
    }
}

namespace horizontalCompression {
    int c[maxn], n1 = 0;

    void init() {
        for (int i = 1; i <= n; i++) c[++n1] = a[i].y;
        sort(c + 1, c + n1 + 1);
        n1 = unique(c + 1, c + n1 + 1) - c - 1;
    }

    int get(int y) {
        return lower_bound(c + 1, c + n1 + 1, y) - c;
    }
}

namespace mainDiagonalCompression {
    int c[maxn], n1 = 0;

    void init() {
        for (int i = 1; i <= n; i++) c[++n1] = a[i].x-a[i].y;
        sort(c + 1, c + n1 + 1);
        n1 = unique(c + 1, c + n1 + 1) - c- 1;
    }

    int get(int xMinusY) {
        return lower_bound(c + 1, c + n1 + 1, xMinusY) - c;
    }
}

namespace gwynDiagonalCompression {
    int c[maxn], n1 = 0;

    void init() {
        for (int i = 1; i <= n; i++) c[++n1] = a[i].x+a[i].y;
        sort(c + 1, c + n1 + 1);
        n1 = unique(c + 1, c + n1 + 1) - c - 1;
    }

    int get(int xPlusY) {
        return lower_bound(c + 1, c + n1 + 1, xPlusY) - c;
    }
}

struct node {
    int pos, idx;
    node() {}
    node(int _pos, int _idx) : pos(_pos), idx(_idx) {}

    bool operator < (const node &other) const {
        if (pos != other.pos) return pos < other.pos;
    }
};

struct tuplets {
    int dis, idxOne, idxTwo;
    tuplets() {}
    tuplets(int _dis, int _idxOne, int _idxTwo) : dis(_dis), idxOne(_idxOne), idxTwo(_idxTwo) {
        if (idxOne > idxTwo) swap(idxOne, idxTwo);
    }

    bool operator < (const tuplets &other) const {
        if (dis != other.dis) return dis < other.dis;
        if (idxOne != other.idxOne) return idxOne < other.idxOne;
        return idxTwo < other.idxTwo;
    }
};

int cl[maxn];

set<node> verticalUp[maxn], verticalDown[maxn],
          horizontalLeft[maxn], horizontalRight[maxn],
          mainDiagonalUp[maxn], mainDiagonalLeft[maxn], mainDiagonalRight[maxn], mainDiagonalDown[maxn],
          gwynDiagonalUp[maxn], gwynDiagonalLeft[maxn], gwynDiagonalRight[maxn], gwynDiagonalDown[maxn];


set<tuplets> pq;

int manhattanDistance(int x, int y) {
    return abs(a[x].x-a[y].x) + abs(a[x].y-a[y].y);
}

void init() {
    for (int _ = 1; _ <= n; _++) {
        switch (a[_].dir) {
        case UP :
            verticalUp[horizontalCompression::get(a[_].y)].insert(node(a[_].x, _));
            mainDiagonalUp[mainDiagonalCompression::get(a[_].x-a[_].y)].insert(node(a[_].y, _));
            gwynDiagonalUp[gwynDiagonalCompression::get(a[_].x+a[_].y)].insert(node(a[_].y, _));
            break;
        case DOWN :
            verticalDown[horizontalCompression::get(a[_].y)].insert(node(a[_].x, _));
            mainDiagonalDown[mainDiagonalCompression::get(a[_].x-a[_].y)].insert(node(a[_].y, _));
            gwynDiagonalDown[gwynDiagonalCompression::get(a[_].x+a[_].y)].insert(node(a[_].y, _));
            break;
        case LEFT :
            horizontalLeft[verticalCompression::get(a[_].x)].insert(node(a[_].y, _));
            mainDiagonalLeft[mainDiagonalCompression::get(a[_].x-a[_].y)].insert(node(a[_].y, _));
            gwynDiagonalLeft[gwynDiagonalCompression::get(a[_].x+a[_].y)].insert(node(a[_].y, _));
            break;
        case RIGHT :
            horizontalRight[verticalCompression::get(a[_].x)].insert(node(a[_].y, _));
            mainDiagonalRight[mainDiagonalCompression::get(a[_].x-a[_].y)].insert(node(a[_].y, _));
            gwynDiagonalRight[gwynDiagonalCompression::get(a[_].x+a[_].y)].insert(node(a[_].y, _));
        default :
            break;
        }
    }

    for (int _ = 1; _ <= verticalCompression::n1; _++) {
        for (auto [pos, idx] : horizontalLeft[_]) {
            auto it = horizontalRight[_].lower_bound(node(pos, INT_MAX));
            if (it != horizontalRight[_].begin()) {
                --it;
                pq.insert(tuplets(manhattanDistance(idx, it->idx), idx, it->idx));
            }
        }
        for (auto [pos, idx] : horizontalRight[_]) {
            auto it = horizontalLeft[_].lower_bound(node(pos, INT_MAX));
            if (it != horizontalLeft[_].end())
                pq.insert(tuplets(manhattanDistance(idx, it->idx), idx, it->idx));
        }
    }

    for (int _ = 1; _ <= horizontalCompression::n1; _++) {
        for (auto [pos, idx] : verticalUp[_]) {
            auto it = verticalDown[_].lower_bound(node(pos, INT_MAX));
            if (it != verticalDown[_].begin()) {
                --it;
                pq.insert(tuplets(manhattanDistance(idx, it->idx), idx, it->idx));
            }
        }
        for (auto [pos, idx] : verticalDown[_]) {
            auto it = verticalUp[_].lower_bound(node(pos, INT_MAX));
            if (it != verticalUp[_].end()) pq.insert(tuplets(manhattanDistance(idx, it->idx), idx, it->idx));
        }
    }

    for (int _ = 1; _ <= mainDiagonalCompression::n1; _++) {
        for (auto [pos, idx] : mainDiagonalDown[_]) {
            auto it = mainDiagonalLeft[_].lower_bound(node(pos, INT_MAX));
            if (it != mainDiagonalLeft[_].end()) pq.insert(tuplets(manhattanDistance(idx, it->idx), idx, it->idx));
        }
        for (auto [pos, idx] : mainDiagonalLeft[_]) {
            auto it = mainDiagonalDown[_].lower_bound(node(pos, INT_MAX));
            if (it != mainDiagonalDown[_].begin()) {
                --it;
                pq.insert(tuplets(manhattanDistance(idx, it->idx), idx, it->idx));
            }
        }
        for (auto [pos, idx] : mainDiagonalRight[_]) {
            auto it = mainDiagonalUp[_].lower_bound(node(pos, INT_MAX));
            if (it != mainDiagonalUp[_].end()) pq.insert(tuplets(manhattanDistance(idx, it->idx), idx, it->idx));
        }
        for (auto [pos, idx] : mainDiagonalUp[_]) {
            auto it = mainDiagonalRight[_].lower_bound(node(pos, INT_MAX));
            if (it != mainDiagonalRight[_].begin()) {
                --it;
                pq.insert(tuplets(manhattanDistance(idx, it->idx), idx, it->idx));
            }
        }
    }

    for (int _ = 1; _ <= gwynDiagonalCompression::n1; _++) {
        for (auto [pos, idx] : gwynDiagonalUp[_]) {
            auto it = gwynDiagonalLeft[_].lower_bound(node(pos, INT_MAX));
            if (it != gwynDiagonalLeft[_].end()) pq.insert(tuplets(manhattanDistance(idx, it->idx), idx, it->idx));
        }
        for (auto [pos, idx] : gwynDiagonalLeft[_]) {
            auto it = gwynDiagonalUp[_].lower_bound(node(pos, INT_MAX));
            if (it != gwynDiagonalUp[_].begin()) {
                --it;
                pq.insert(tuplets(manhattanDistance(idx, it->idx), idx, it->idx));
            }
        }
        for (auto [pos, idx] : gwynDiagonalRight[_]) {
            auto it = gwynDiagonalDown[_].lower_bound(node(pos, INT_MAX));
            if (it != gwynDiagonalDown[_].end()) pq.insert(tuplets(manhattanDistance(idx, it->idx), idx, it->idx));
        }
        for (auto [pos, idx] : gwynDiagonalDown[_]) {
            auto it = gwynDiagonalRight[_].lower_bound(node(pos, INT_MAX));
            if (it != gwynDiagonalRight[_].begin()) {
                --it;
                pq.insert(tuplets(manhattanDistance(idx, it->idx), idx, it->idx));
            }
        }
    }
}


void del(int _) {
    switch (a[_].dir) {
    case UP :
        if (1) {
            int o = horizontalCompression::get(a[_].y);
            verticalUp[o].erase(node(a[_].x, _));
            auto it = verticalDown[o].lower_bound(node(a[_].x, INT_MAX));
            if (it != verticalDown[o].begin()) {
                --it;
                auto ti = verticalUp[o].lower_bound(node(it->pos, INT_MAX));
                if (ti != verticalUp[o].end())
                    pq.insert(tuplets(manhattanDistance(it->idx, ti->idx), it->idx, ti->idx));
            }
        }
        if (1) {
            int o = mainDiagonalCompression::get(a[_].x-a[_].y);
            mainDiagonalUp[o].erase(node(a[_].y, _));
            auto it = mainDiagonalRight[o].lower_bound(node(a[_].y, INT_MAX));
            if (it != mainDiagonalRight[o].begin()) {
                --it;
                auto ti = mainDiagonalUp[o].lower_bound(node(it->pos, INT_MAX));
                if (ti != mainDiagonalUp[o].end())
                    pq.insert(tuplets(manhattanDistance(it->idx, ti->idx), it->idx, ti->idx));
            }
        }
        if (1) {
            int o = gwynDiagonalCompression::get(a[_].x+a[_].y);
            gwynDiagonalUp[o].erase(node(a[_].y, _));
            auto it = gwynDiagonalLeft[o].lower_bound(node(a[_].y, INT_MAX));
            if (it != gwynDiagonalLeft[o].end()) {
                auto ti = gwynDiagonalUp[o].lower_bound(node(it->pos, INT_MAX));
                if (ti != gwynDiagonalUp[o].begin()) {
                    --ti;
                    pq.insert(tuplets(manhattanDistance(it->idx, ti->idx), it->idx, ti->idx));
                }
            }
        }
        break;
    case DOWN :
        if (1) {
            int o = horizontalCompression::get(a[_].y);
            verticalDown[o].erase(node(a[_].x, _));
            auto it = verticalUp[o].lower_bound(node(a[_].x, INT_MAX));
            if (it != verticalUp[o].end()) {
                auto ti = verticalDown[o].lower_bound(node(it->pos, INT_MAX));
                if (ti != verticalDown[o].begin()) {
                    --ti;
                    pq.insert(tuplets(manhattanDistance(it->idx, ti->idx), it->idx, ti->idx));
                }
            }
        }
        if (1) {
            int o = mainDiagonalCompression::get(a[_].x-a[_].y);
            mainDiagonalDown[o].erase(node(a[_].y, _));
            auto it = mainDiagonalLeft[o].lower_bound(node(a[_].y, INT_MAX));
            if (it != mainDiagonalLeft[o].end()) {
                auto ti = mainDiagonalDown[o].lower_bound(node(it->pos, INT_MAX));
                if (ti != mainDiagonalDown[o].begin()) {
                    --ti;
                    pq.insert(tuplets(manhattanDistance(it->idx, ti->idx), it->idx, ti->idx));
                }
            }
        }
        if (1) {
            int o = gwynDiagonalCompression::get(a[_].x+a[_].y);
            gwynDiagonalDown[o].erase(node(a[_].y, _));
            auto it = gwynDiagonalRight[o].lower_bound(node(a[_].y, INT_MAX));
            if (it != gwynDiagonalRight[o].begin()) {
                --it;
                auto ti = gwynDiagonalDown[o].lower_bound(node(a[_].y, INT_MAX));
                if (ti != gwynDiagonalDown[o].end())
                    pq.insert(tuplets(manhattanDistance(it->idx, ti->idx), it->idx, ti->idx));
            }
        }
        break;
    case LEFT :
        if (1) {
            int o = verticalCompression::get(a[_].x);
            horizontalLeft[o].erase(node(a[_].y, _));
            auto it = horizontalRight[o].lower_bound(node(a[_].y, INT_MAX));
            if (it != horizontalRight[o].begin()) {
                --it;
                auto ti = horizontalLeft[o].lower_bound(node(it->pos, INT_MAX));
                if (ti != horizontalLeft[o].end())
                    pq.insert(tuplets(manhattanDistance(it->idx, ti->idx), it->idx, ti->idx));
            }
        }
        if (1) {
            int o = mainDiagonalCompression::get(a[_].x-a[_].y);
            mainDiagonalLeft[o].erase(node(a[_].y, _));
            auto it = mainDiagonalDown[o].lower_bound(node(a[_].y, INT_MAX));
            if (it != mainDiagonalDown[o].begin()) {
                --it;
                auto ti = mainDiagonalLeft[o].lower_bound(node(it->pos, INT_MAX));
                if (ti != mainDiagonalLeft[o].end())
                    pq.insert(tuplets(manhattanDistance(it->idx, ti->idx), it->idx, ti->idx));
            }
        }
        if (1) {
            int o = gwynDiagonalCompression::get(a[_].x+a[_].y);
            gwynDiagonalLeft[o].erase(node(a[_].y, _));
            auto it = gwynDiagonalUp[o].lower_bound(node(a[_].y, INT_MAX));
            if (it != gwynDiagonalUp[o].begin()) {
                --it;
                auto ti = gwynDiagonalLeft[o].lower_bound(node(it->pos, INT_MAX));
                if (ti != gwynDiagonalLeft[o].end())
                    pq.insert(tuplets(manhattanDistance(it->idx, ti->idx), it->idx, ti->idx));
            }
        }
        break;
    case RIGHT :
        if (1) {
            int o = verticalCompression::get(a[_].x);
            horizontalRight[o].erase(node(a[_].y, _));
            auto it = horizontalLeft[o].lower_bound(node(a[_].y, INT_MAX));
            if (it != horizontalLeft[o].end()) {
                auto ti = horizontalRight[o].lower_bound(node(it->pos, INT_MAX));
                if (ti != horizontalRight[o].begin()) {
                    --ti;
                    pq.insert(tuplets(manhattanDistance(it->idx, ti->idx), it->idx, ti->idx));
                }
            }
        }
        if (1) {
            int o = mainDiagonalCompression::get(a[_].x-a[_].y);
            mainDiagonalRight[o].erase(node(a[_].y, _));
            auto it = mainDiagonalUp[o].lower_bound(node(a[_].y, INT_MAX));
            if (it != mainDiagonalUp[o].end()) {
                auto ti = mainDiagonalRight[o].lower_bound(node(it->pos, INT_MAX));
                if (ti != mainDiagonalRight[o].begin()) {
                    --ti;
                    pq.insert(tuplets(manhattanDistance(it->idx, ti->idx), it->idx, ti->idx));
                }
            }
        }
        if (1) {
            int o = gwynDiagonalCompression::get(a[_].x+a[_].y);
            gwynDiagonalRight[o].erase(node(a[_].x+a[_].y, _));
            auto it = gwynDiagonalDown[o].lower_bound(node(a[_].y, INT_MAX));
            if (it != gwynDiagonalDown[o].end()) {
                auto ti = gwynDiagonalRight[o].lower_bound(node(it->pos, INT_MAX));
                if (ti != gwynDiagonalRight[o].begin()) {
                    --ti;
                    pq.insert(tuplets(manhattanDistance(it->idx, ti->idx), it->idx, ti->idx));
                }
            }
        }
        break;
    default :
        break;
    }
}

void solve() {
    vector<int> candidates;
    while (!pq.empty()) {
        int D = pq.begin()->dis;
        candidates.clear();
        candidates.shrink_to_fit();
        while (!pq.empty() && pq.begin()->dis == D) {
            if (cl[pq.begin()->idxOne] || cl[pq.begin()->idxTwo]) {
                pq.erase(pq.begin());
                continue;
            }
            candidates.emplace_back(pq.begin()->idxOne);
            candidates.emplace_back(pq.begin()->idxTwo);
            pq.erase(pq.begin());
        }
        for (int i : candidates)
        if (!cl[i]) {
            cl[i] = 1;
            del(i);
        }
    }
}

int main() {
//    if (fopen("check.inp", "r")) {
//        freopen("check.inp", "r", stdin);
//        freopen("check.out", "w", stdout);
//    }
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n;
    for (int i = 1; i <= n; i++) {
        int x, y; char dir;
        cin >> x >> y >> dir;
        int d;
        switch (dir) {
        case 'N' :
            d = UP;
            break;
        case 'W' :
            d = LEFT;
            break;
        case 'S' :
            d = DOWN;
            break;
        default :
            d = RIGHT;
        }
        a[i] = ship(y, x, d);
    }

    verticalCompression::init();
    horizontalCompression::init();
    mainDiagonalCompression::init();
    gwynDiagonalCompression::init();

    init();
    solve();

    for (int i = 1; i <= n; i++) if (!cl[i]) cout << i << "\n";
}
/*
5
6 6 W
8 10 N
8 6 E
4 2 E
8 0 E

1 2 3 4 5

*/

Compilation message (stderr)

Main.cpp: In member function 'bool node::operator<(const node&) const':
Main.cpp:84:5: warning: control reaches end of non-void function [-Wreturn-type]
   84 |     }
      |     ^

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