Submission #1254125

#	Time	Username	Problem	Language	Result	Execution time	Memory
1254125		ofoz	Naval battle (CEOI24_battle)	C++20	0 / 100	724 ms	35984 KiB

Main

#include <bits/stdc++.h>
#pragma GCC optimize("O2") 
using namespace std;
#define vi vector<int>
#define pi pair<int, int>
#define ppi pair<pair<int, int>, int>
#define mtis multiset<pi>
#define endl '\n'
struct Ship {
    int x, y, ind;
    char dir;
    bool operator<(const Ship& other) const {
        return x < other.x;
    }
};

int man_dist(Ship s1, Ship s2) {
    return abs(s1.x - s2.x) + abs(s1.y - s2.y);
}

bool is_valid(Ship s1, Ship s2, bool b = 0) {
    bool res = s1.dir != s2.dir;

    if (s1.dir == 'E') {
        res &= (s2.x > s1.x);
        if (s2.dir == 'W') res &= (s2.y == s1.y);
        else res &= (abs(s1.x - s2.x) == abs(s1.y - s2.y));
    }

    if (s1.dir == 'W') {
        res &= (s2.x < s1.x);
        if (s2.dir == 'E') res &= (s2.y == s1.y);
        else res &= (abs(s1.x - s2.x) == abs(s1.y - s2.y));
    }

    if (s1.dir == 'N') {
        res &= (s2.y < s1.y);
        if (s2.dir == 'S') res &= (s2.x == s1.x);
        else res &= (abs(s1.x - s2.x) == abs(s1.y - s2.y));
    }

    if (s1.dir == 'S') {
        res &= (s2.y > s1.y);
        if (s2.dir == 'N') res &= (s2.x == s1.x);
        else res &= (abs(s1.x - s2.x) == abs(s1.y - s2.y));
    }
    if (!b) res &= is_valid(s2, s1, 1);
    return res;
}

void solve() {
    int n;
    cin >> n;
    vector<Ship> ships(n);
    for (int i = 0; i < n; i++) {
        cin >> ships[i].x >> ships[i].y >> ships[i].dir;
        ships[i].ind = i+1;
    }

    vector<Ship> ord;
    map<int, priority_queue<pair<int, Ship>>> mp;
    for (int i = 0; i < n; i++) {
        ord.push_back(ships[i]);
    }

    vector<int> sunk(n+1, 0);
    sort(ord.begin(), ord.end());
    vi res;
    set<int> survived;
    for (Ship s1 : ord) {
        cerr << s1.dir << ' ' << s1.x+s1.y << endl;
        if (s1.dir == 'E') {
            mp[s1.x + s1.y].push({s1.y, s1});
            survived.insert(s1.ind);
        }
        else {
            if (mp[s1.x + s1.y].empty()) { res.push_back(s1.ind); continue; }
            Ship s2 = mp[s1.x + s1.y].top().second;
            mp[s1.x + s1.y].pop();
            survived.erase(s2.ind);
        }
    }
    for (int p : survived) res.push_back(p);
    for (int p : res) {
        cout << p << endl;
    }
}


signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    bool test = 0;
    int t;
    if (!test) t = 1;
    else cin >> t;
    while (t--) {
        solve();
    }
    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