Submission #1227628

#	Time	Username	Problem	Language	Result	Execution time	Memory
1227628		SpyrosAliv	Naval battle (CEOI24_battle)	C++20	46 / 100	3108 ms	790340 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define ll long long

const int INF = 1e9;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n; cin >> n;
    vector<int> x(n), y(n);
    vector<char> dir(n);
    for (int i = 0; i < n; i++) {
        cin >> x[i] >> y[i] >> dir[i];
        y[i] = INF - y[i];
    }
    vector<bool> collide(n, false);
    vector<tuple<int, int, int>> colls;
    for (int i = 0; i < n; i++) {
        for (int j = i+1; j < n; j++) {
            if (dir[i] == dir[j]) continue;
            bool sw = false;
            if (dir[j] == 'E' || dir[j] == 'W') {
                sw = true;
                swap(i, j);
            }
            else if (dir[i] != 'E' && dir[i] != 'W' && dir[j] == 'N') {
                swap(i, j);
                sw = true;
            }
            if (dir[i] == 'E') {
                if (dir[j] == 'W') {
                    if (y[i] != y[j] || x[i] > x[j]) {
                        if (sw) swap(i, j);
                        continue;
                    }
                    int mid = (x[i] + x[j]) / 2;
                    colls.push_back({mid - x[i], i, j});
                }
                else if (dir[j] == 'S') {
                    if (y[j] <= y[i] || x[j] <= x[i]) {
                        if (sw) swap(i, j);
                        continue;
                    }
                    if (y[j] - y[i] == x[j] - x[i]) {
                        colls.push_back({x[j] - x[i], i, j});
                    }
                }
                else if (dir[j] == 'N') {
                    if (y[j] >= y[i] || x[j] <= x[i]) {
                        if (sw) swap(i, j);
                        continue;
                    }
                    if (abs(y[j] - y[i]) == abs(x[j] - x[i])) {
                        colls.push_back({abs(x[j] - x[i]), i, j});
                    }
                }
            }
            else if (dir[i] == 'W') {
                if (dir[j] == 'E') {
                    if (y[j] != y[i] || x[j] > x[i]) {
                        if (sw) swap(i, j);
                        continue;
                    }
                    int mid = (x[j] + x[i]) / 2;
                    colls.push_back({mid - x[j], i, j});
                }
                else if (dir[j] == 'S') {
                    if (y[j] <= y[i] || x[j] >= x[i]) {
                        if (sw) swap(i, j);
                        continue;
                    }
                    if (y[j] - y[i] == x[i] - x[j]) {
                        colls.push_back({x[i] - x[j], i, j});
                    }
                }
                else if (dir[j] == 'N') {
                    if (y[j] >= y[i] || x[j] >= x[i]) {
                        if (sw) swap(i, j);
                        continue;
                    }
                    if (abs(y[j] - y[i]) == x[i] - x[j]) {
                        colls.push_back({x[i] - x[j], i, j});
                    }
                }
            }
            else if (dir[i] == 'N') {
                if (dir[j] == 'S') {
                    if (x[i] != x[j] || y[i] >= y[j]) {
                        if (sw) swap(i, j);
                        continue;
                    }
                    int mid = (y[i] + y[j]) / 2;
                    colls.push_back({mid - y[i], i, j});
                }
                else assert(false);
            }
            if (sw) swap(i, j);
        }
    }
    sort(colls.begin(), colls.end());
    vector<pair<int, int>> proc;
    for (int i = 0; i < (int)colls.size(); i++) {
        if (proc.empty() || get<0>(colls[i]) == get<0>(colls[i-1])) {
            proc.push_back({get<1>(colls[i]), get<2>(colls[i])});
        }
        else {
            vector<int> willCrash;
            for (auto [u, v]: proc) {
                if (collide[u] || collide[v]) continue;
                willCrash.push_back(u);
                willCrash.push_back(v);
            }
            for (auto x: willCrash) collide[x] = true;
            proc.clear();
            proc.push_back({get<1>(colls[i]), get<2>(colls[i])});
        }
    }
    vector<int> willCrash;
    for (auto [u, v]: proc) {
        if (collide[u] || collide[v]) continue;
        willCrash.push_back(u);
        willCrash.push_back(v);
    }
    for (auto x: willCrash) collide[x] = true;
    for (int i = 0; i < n; i++) {
        if (!collide[i]) cout << i+1 << "\n";
    }
}

• 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: 0 / 30
• Subtask 7: 0 / 24