Submission #1040842

#	Time	Username	Problem	Language	Result	Execution time	Memory
1040842		elazarkoren	Naval battle (CEOI24_battle)	C++17	100 / 100	1016 ms	93416 KiB

Main

#include <bits/stdc++.h>
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define chkmin(a, b) a = min(a, b)
#define chkmax(a, b) a = max(a, b)
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pii;
typedef vector<pii> vii;
typedef vector<bool> vb;

const int MAX_N = 2e5 + 5;

const int dx[] = {0, 0, 1, -1};
const int dy[] = {1, -1, 0, 0};
int mptype[200];

int x[MAX_N], y[MAX_N], type[MAX_N];

int Crash(int i, int j) {
    if (type[i] == type[j]) return -1;
    if (type[i] > type[j]) swap(i, j);
    if (!type[i] && type[j] == 1) {
        if (x[i] != x[j] || y[i] > y[j]) return -1;
        return (y[j] - y[i]) / 2;
    }
    if (!type[i] && type[j] == 2) {
        if (x[i] + y[i] != x[j] + y[j] || x[i] < x[j]) return -1;
        return x[i] - x[j];
    }
    if (!type[i] && type[j] == 3) {
        if (x[i] - y[i] != x[j] - y[j] || x[i] > x[j]) return -1;
        return x[j] - x[i];
    }
    if (type[i] == 1 && type[j] == 2) {
        if (x[i] - y[i] != x[j] - y[j] || x[i] < x[j]) return -1;
        return x[i] - x[j];
    }
    if (type[i] == 1 && type[j] == 3) {
        if (x[i] + y[i] != x[j] + y[j] || x[i] > x[j]) return -1;
        return x[j] - x[i];
    }
    if (y[i] != y[j] || x[i] > x[j]) return -1;
    return (x[j] - x[i]) / 2;
}

priority_queue<pair<int, pii>, vector<pair<int, pii>>, greater<pair<int, pii>>> pq;

void Erase(set<pii> &s, pii p) {
    auto it = s.erase(s.find(p));
    if (it == s.end() || it == s.begin()) return;
    auto it2 = it--;
    int i = it->y, j = it2->y;
    int t = Crash(i, j);
    if (t != -1) pq.push({t, {i, j}});
}

map<int, set<pii>> rows, cols, digp[2], digm[2];

void Erase(int i) {
    int t = type[i];
    if (!t) {
        Erase(cols[x[i]], {y[i], i});
        Erase(digp[0][x[i] + y[i]], {x[i], i});
        Erase(digm[0][x[i] - y[i]], {x[i], i});
    } else if (t == 1) {
        Erase(cols[x[i]], {y[i], i});
        Erase(digp[1][x[i] + y[i]], {x[i], i});
        Erase(digm[1][x[i] - y[i]], {x[i], i});
    } else if (t == 2) {
        Erase(rows[y[i]], {x[i], i});
        Erase(digp[0][x[i] + y[i]], {x[i], i});
        Erase(digm[1][x[i] - y[i]], {x[i], i});
    } else {
        Erase(rows[y[i]], {x[i], i});
        Erase(digp[1][x[i] + y[i]], {x[i], i});
        Erase(digm[0][x[i] - y[i]], {x[i], i});
    }
}


int crash_t[MAX_N];

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    mptype['S'] = 0, mptype['N'] = 1, mptype['E'] = 2, mptype['W'] = 3;
    mptype[0] = 'S', mptype[1] = 'N', mptype[2] = 'E', mptype[3] = 'W';
    int n;
    cin >> n;
    set<pii> pos;
    vvi board(20, vi(20));
    for (int i = 0; i < n; i++) {
//        do {
//            x[i] = rand() % 5, y[i] = rand() % 5;
//            x[i] <<= 1, y[i] <<= 1;
//        } while (pos.count({x[i], y[i]}));
//        pos.insert({x[i], y[i]});
//        type[i] = rand() % 4;
//        board[x[i]][y[i]] = mptype[type[i]];
        char t;
        cin >> x[i] >> y[i] >> t;
        type[i] = mptype[t];
    }
//    for (int i = 0; i < 20; i++) {
//        for (int j = 0; j < 20; j++) {
//            if (!board[j][i]) cout << 0;
//            else cout << char(board[j][i]);
//        }
//        cout << "\n";
//    }
//    return 0;

    for (int i = 0; i < n; i++) {
        int t = type[i];
        if (!t) { //S
            cols[x[i]].insert({y[i], i});
            digp[0][x[i] + y[i]].insert({x[i], i});
            digm[0][x[i] - y[i]].insert({x[i], i});
        } else if (t == 1) {//N
            cols[x[i]].insert({y[i], i});
            digp[1][x[i] + y[i]].insert({x[i], i});
            digm[1][x[i] - y[i]].insert({x[i], i});
        } else if (t == 2) {//E
            rows[y[i]].insert({x[i], i});
            digp[0][x[i] + y[i]].insert({x[i], i});
            digm[1][x[i] - y[i]].insert({x[i], i});
        } else {//W
            rows[y[i]].insert({x[i], i});
            digp[1][x[i] + y[i]].insert({x[i], i});
            digm[0][x[i] - y[i]].insert({x[i], i});
        }
    }

    for (auto &[x, s] : rows) {
        for (auto it = s.begin(); it != s.end();) {
            auto it2 = it++;
            if (it == s.end()) break;
            int i = it->y, j = it2->y;
            int t = Crash(i, j);
            if (t != -1) pq.push({t, {i, j}});
        }
    }
    for (auto &[x, s] : cols) {
        for (auto it = s.begin(); it != s.end();) {
            auto it2 = it++;
            if (it == s.end()) break;
            int i = it->y, j = it2->y;
            int t = Crash(i, j);
            if (t != -1) pq.push({t, {i, j}});
        }
    }
    for (int a = 0; a < 2; a++) {
        for (auto &[x, s] : digp[a]) {
            for (auto it = s.begin(); it != s.end();) {
                auto it2 = it++;
                if (it == s.end()) break;
                int i = it->y, j = it2->y;
                int t = Crash(i, j);
                if (t != -1) pq.push({t, {i, j}});
            }
        }
    }
    for (int a = 0; a < 2; a++) {
        for (auto &[x, s] : digm[a]) {
            for (auto it = s.begin(); it != s.end();) {
                auto it2 = it++;
                if (it == s.end()) break;
                int i = it->y, j = it2->y;
                int t = Crash(i, j);
                if (t != -1) pq.push({t, {i, j}});
            }
        }
    }

    while (!pq.empty()) {
        auto [t, q] = pq.top();
        pq.pop();
        auto [i, j] = q;
        if (crash_t[j]) swap(i, j);
        if (crash_t[j]) continue;
        if (!crash_t[i]) {
            if (!i || !j) {
                cout << "";
            }
            crash_t[i] = crash_t[j] = t;
            Erase(i), Erase(j);
        } else if (crash_t[i] == t) {
            if (!j) {
                cout << "";
            }
            crash_t[j] = t;
            Erase(j);
        }
    }

//    vector<pair<int, pii>> events; //{{time, {x, y}}, {s1, s2}}
//    for (int i = 0; i < n; i++) {
//        for (int j = i + 1; j < n; j++) {
//            auto p = Crash(i, j);
//            if (p == -1) continue;
//            events.push_back({p, {i, j}});
//        }
//    }
//    vi crash_t2(n);
//    sort(all(events));
//    for (auto [t, q] : events) {
//        auto [i, j] = q;
//        if (crash_t2[j]) swap(i, j);
//        if (crash_t2[j]) continue;
//        if (!crash_t2[i]) {
//            crash_t2[i] = crash_t2[j] = t;
//        } else if (crash_t2[i] == t) {
//            crash_t2[j] = t;
//        }
//    }
//    for (int i = 0; i < n; i++) {
//        if (crash_t[i] != crash_t2[i]) {
//            cout << i << " BAD\n";
//        }
//    }

    for (int i = 0; i < n; i++) {
        if (!crash_t[i]) cout << i + 1 << '\n';
    }
}
/*
2
2 2 W
0 4 N
 */

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:106:26: warning: array subscript has type 'char' [-Wchar-subscripts]
  106 |         type[i] = mptype[t];
      |                          ^

• 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