Submission #1227300

#	Time	Username	Problem	Language	Result	Execution time	Memory
1227300		dreamxhava	Naval battle (CEOI24_battle)	C++20	0 / 100	3092 ms	23964 KiB

Main

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

int main() {
    int n;
    cin >> n;
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    vector<int> x(n), y(n);
    vector<char> d(n);
    vector<bool> active(n, true);
    vector<bool> collided(n, false);

    for (int i = 0; i < n; i++) {
        cin >> x[i] >> y[i] >> d[i];
    }

    int xmax = *max_element(x.begin(), x.end());
    int ymax = *max_element(y.begin(), y.end());

    if (n == 1) {
        cout << 1 << "\n";
        return 0;
    }

    if (n == 2) {
        int x1 = x[0], y1 = y[0], x2 = x[1], y2 = y[1];
        char d1 = d[0], d2 = d[1];
        for (int t = 0; t < 1000; t++) {
            if (x1 == x2 && y1 == y2) return 0;
            int px1 = x1, py1 = y1, px2 = x2, py2 = y2;
            if (d1 == 'N') y1 -= 2;
            else if (d1 == 'S') y1 += 2;
            else if (d1 == 'E') x1 += 2;
            else if (d1 == 'W') x1 -= 2;
            if (d2 == 'N') y2 -= 2;
            else if (d2 == 'S') y2 += 2;
            else if (d2 == 'E') x2 += 2;
            else if (d2 == 'W') x2 -= 2;
            if (x1 == x2 && y1 == y2) return 0;
            if (x1 == px2 && y1 == py2 && x2 == px1 && y2 == py1) return 0;
            if (x1 > xmax || x1 < 0 || y1 > ymax || y1 < 0 ||
                x2 > xmax || x2 < 0 || y2 > ymax || y2 < 0) return 0;
        }
        cout << 1 << "\n" << 2 << "\n";
        return 0;
    }

    int max_steps = 101; // enough for x,y <= 100
    for (int step = 0; step < max_steps; step++) {
        map<pair<int, int>, vector<int>> pos;
        for (int i = 0; i < n; i++) {
            if (!active[i]) continue;
            pos[{x[i], y[i]}].push_back(i);
        }
        for (auto &p : pos) {
            if (p.second.size() > 1) {
                for (int idx : p.second) {
                    collided[idx] = true;
                    active[idx] = false;
                }
            }
        }
        for (int i = 0; i < n; i++) {
            if (!active[i]) continue;
            if (d[i] == 'N') y[i] -= 2;
            else if (d[i] == 'S') y[i] += 2;
            else if (d[i] == 'E') x[i] += 2;
            else if (d[i] == 'W') x[i] -= 2;
            if (x[i] > xmax || x[i] < 0 || y[i] > ymax || y[i] < 0) {
                active[i] = false;
            }
        }
    }

    for (int i = 0; i < n; i++) {
        if (!collided[i]) {
            cout << i + 1 << "\n";
        }
    }

    return 0;
}

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