Submission #1262123

#	Time	Username	Problem	Language	Result	Execution time	Memory
1262123		kikitop1gg	Naval battle (CEOI24_battle)	C++17	100 / 100	909 ms	160772 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define vi vector<ll>
#define vvi vector<vector<ll>>
#define vs vector<string>
#define vc vector<char>
#define vb vector<bool>
#define vp vector<pair<ll, ll>>
#define vpp vector<pair<ll, pair<ll, ll>>>
#define pp pair<ll, ll>
#define qi queue<ll>
#define qp queue<pp>
#define pqi priority_queue<ll>
#define pqp priority_queue<pp>
#define mi map<ll, ll>
#define mpi map<pp, ll>
#define mip map<ll, pp>
#define mp map<pp, pp>
#define mb map<ll, bool>
#define si set<ll>
#define sp set<pp>
#define sc set<char>
#define mod 1000000007
#define inf INT_MAX
#define all(x) (x).begin(), (x).end()
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    ll n;
    cin >> n;
    vp a(n);
    vc type(n);
    vector<pair<pp, ll>> north, south, east, west;
    map<ll, vp> diagES;
    map<ll, vp> diagWN;
    map<ll, vp> diagEN;
    map<ll, vp> diagWS;
    map<ll, vp> vert;
    map<ll, vp> hor;
    for(int i = 0; i < n; i++) {
        cin >> a[i].first >> a[i].second >> type[i];
        if(type[i] == 'N') {
            north.push_back({a[i], i});
        }
        else if(type[i] == 'S') {
            south.push_back({a[i], i});
        }
        else if(type[i] == 'W') {
            west.push_back({a[i], i});
        }
        else {
            east.push_back({a[i], i});
        }

        auto[x, y] = a[i];
        ll d = x + y;
        if(type[i] == 'E' || type[i] == 'S') {
            diagES[d].push_back({y, i});
        }
        else {
            diagWN[d].push_back({y, i});
        }

        d = x - y;
        if(type[i] == 'E' || type[i] == 'N') {
            diagEN[d].push_back({y, i});
        }
        else {
            diagWS[d].push_back({y, i});
        }

        if(type[i] == 'W' || type[i] == 'E') {
            hor[y].push_back({x, i});
        }
        else {
            vert[x].push_back({y, i});
        }
    }

    vector<int> time_of_death(n, inf);
    priority_queue<pair<pair<ll, pair<string, ll>>, pp>> q;
    map<ll, si> usedES;
    for(auto&[d, v] : diagES) {
        sort(all(v));
        for(int i = 0; i < v.size(); i++) usedES[d].insert(i);
        for(int i = 0; i < v.size() - 1; i++) {
            ll ind1 = v[i].second, ind2 = v[i + 1].second;
            if(type[ind1] == 'S' && type[ind2] == 'E') {
                ll time = (abs(a[ind1].first - a[ind2].first) + abs(a[ind1].second - a[ind2].second)) / 2;
                q.push({{-time, {"ES", d}}, {i, i + 1}});
            }
        }
    }
    map<ll, si> usedWN;
    for(auto&[d, v] : diagWN) {
        sort(all(v));
        for(int i = 0; i < v.size(); i++) usedWN[d].insert(i);
        for(int i = 0; i < v.size() - 1; i++) {
            ll ind1 = v[i].second, ind2 = v[i + 1].second;
            if(type[ind1] == 'W' && type[ind2] == 'N') {
                ll time = (abs(a[ind1].first - a[ind2].first) + abs(a[ind1].second - a[ind2].second)) / 2;
                q.push({{-time, {"WN", d}}, {i, i + 1}});
            }
        }
    }
    map<ll, si> usedEN;
    for(auto&[d, v] : diagEN) {
        sort(all(v));
        for(int i = 0; i < v.size(); i++) usedEN[d].insert(i);
        for(int i = 0; i < v.size() - 1; i++) {
            ll ind1 = v[i].second, ind2 = v[i + 1].second;
            if(type[ind1] == 'E' && type[ind2] == 'N') {
                ll time = (abs(a[ind1].first - a[ind2].first) + abs(a[ind1].second - a[ind2].second)) / 2;
                q.push({{-time, {"EN", d}}, {i, i + 1}});
            }
        }
    }
    map<ll, si> usedWS;
    for(auto&[d, v] : diagWS) {
        sort(all(v));
        for(int i = 0; i < v.size(); i++) usedWS[d].insert(i);
        for(int i = 0; i < v.size() - 1; i++) {
            ll ind1 = v[i].second, ind2 = v[i + 1].second;
            if(type[ind1] == 'S' && type[ind2] == 'W') {
                ll time = (abs(a[ind1].first - a[ind2].first) + abs(a[ind1].second - a[ind2].second)) / 2;
                q.push({{-time, {"WS", d}}, {i, i + 1}});
            }
        }
    }
    map<ll, si> usedvert;
    for(auto&[d, v] : vert) {
        sort(all(v));
        for(int i = 0; i < v.size(); i++) usedvert[d].insert(i);
        for(int i = 0; i < v.size() - 1; i++) {
            ll ind1 = v[i].second, ind2 = v[i + 1].second;
            if(type[ind1] == 'S' && type[ind2] == 'N') {
                ll time = (abs(a[ind1].first - a[ind2].first) + abs(a[ind1].second - a[ind2].second)) / 2;
                q.push({{-time, {"vert", d}}, {i, i + 1}});
            }
        }
    }
    map<ll, si> usedhor;
    for(auto&[d, v] : hor) {
        sort(all(v));
        for(int i = 0; i < v.size(); i++) usedhor[d].insert(i);
        for(int i = 0; i < v.size() - 1; i++) {
            ll ind1 = v[i].second, ind2 = v[i + 1].second;
            if(type[ind1] == 'E' && type[ind2] == 'W') {
                ll time = (abs(a[ind1].first - a[ind2].first) + abs(a[ind1].second - a[ind2].second)) / 2;
                q.push({{-time, {"hor", d}}, {i, i + 1}});
            }
        }
    }

    while(q.size()) {
        ll curTime = -q.top().first.first;
        auto[from, d] = q.top().first.second;
        auto[i, j] = q.top().second;
        q.pop();

        vp *temp;
        si *usedTemp;
        char type1, type2;
        if(from == "ES") {
            temp = &diagES[d];
            usedTemp = &usedES[d];
            type1 = 'S';
            type2 = 'E';
        }
        else if(from == "WN") {
            temp = &diagWN[d];
            usedTemp = &usedWN[d];
            type1 = 'W';
            type2 = 'N';
        }
        else if(from == "EN") {
            temp = &diagEN[d];
            usedTemp = &usedEN[d];
            type1 = 'E';
            type2 = 'N';
        }
        else if(from == "WS") {
            temp = &diagWS[d];
            usedTemp = &usedWS[d];
            type1 = 'S';
            type2 = 'W';
        }
        else if(from == "vert") {
            temp = &vert[d];
            usedTemp = &usedvert[d];
            type1 = 'S';
            type2 = 'N';
        }
        else if(from == "hor") {
            temp = &hor[d];
            usedTemp = &usedhor[d];
            type1 = 'E';
            type2 = 'W';
        }
        vp &v = *temp;
        si &used = *usedTemp;

        ll realInd1 = v[i].second;
        ll realInd2 = v[j].second;

        if(time_of_death[realInd1] >= curTime && time_of_death[realInd2] >= curTime) {
            time_of_death[realInd1] = curTime;
            time_of_death[realInd2] = curTime;
        }

        if((time_of_death[realInd1] >= curTime && time_of_death[realInd2] >= curTime) || 
            (time_of_death[realInd1] < curTime && time_of_death[realInd2] < curTime)) {
            auto it1 = used.lower_bound(i);
            auto it2 = used.upper_bound(j);
            if(it1 == used.begin() || it2 == used.end()) {
                used.erase(i);
                used.erase(j);
                continue;
            }
            it1--;
            ll newI = *it1, newJ = *it2;
            ll ind1 = v[newI].second, ind2 = v[newJ].second;
            if(type[ind1] != type1 || type[ind2] != type2) {
                used.erase(i);
                used.erase(j);
                continue;
            }
            ll time = (abs(a[ind1].first - a[ind2].first) + abs(a[ind1].second - a[ind2].second)) / 2;
            q.push({{-time, {from, d}}, {newI, newJ}});
            used.erase(i);
            used.erase(j);
        }
        else if(time_of_death[realInd1] < curTime) {
            auto it1 = used.lower_bound(i);
            bool found = false;
            while(it1 != used.begin()) {
                it1--;
                ll newI = *it1, newJ = j;
                ll ind1 = v[newI].second, ind2 = v[newJ].second;
                if(type[ind1] != type1 || type[ind2] != type2) {
                    continue;
                }
                ll time = (abs(a[ind1].first - a[ind2].first) + abs(a[ind1].second - a[ind2].second)) / 2;
                q.push({{-time, {from, d}}, {newI, newJ}});
                used.erase(i);
                found = true;
                break;
            }
            if(!found) {
                used.erase(i);
                used.erase(j);
            }
        }
        else if(time_of_death[realInd2] < curTime) {
            auto it2 = used.upper_bound(j);
            bool found = false;
            while(it2 != used.end()) {
                ll newI = i, newJ = *it2;
                ll ind1 = v[newI].second, ind2 = v[newJ].second;
                if(type[ind1] != type1 || type[ind2] != type2) {
                    it2++;
                    continue;
                }
                ll time = (abs(a[ind1].first - a[ind2].first) + abs(a[ind1].second - a[ind2].second)) / 2;
                q.push({{-time, {from, d}}, {newI, newJ}});
                used.erase(j);
                found = true;
                break;
            }
            if(!found) {
                used.erase(i);
                used.erase(j);
            }
        }
        else cout << "o ou\n";
    }

    for(int i = 0; i < n; i++) {
        if(time_of_death[i] == inf) cout << i + 1 << '\n';
    }
    return 0;
}
/*
3
4 0 S
2 2 E
0 4 E
3

5
2 2 E
4 0 S
0 4 E
1 3 S
3 1 S
2

4
0 6 E
2 4 E
4 2 S
6 0 S

2
0 0 E
2 2 N

4
0 0 S
0 2 E
2 2 W
4 4 W

4
0 0 N
0 2 S
0 4 N
0 6 N
1 4

*/

• 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