Submission #1183075

#	Time	Username	Problem	Language	Result	Execution time	Memory
1183075		gyg	Naval battle (CEOI24_battle)	C++20	100 / 100	1910 ms	132980 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define arr array 
#define vec vector 
#define pii pair<int, int>
#define fir first 
#define sec second 
const int N = 2e5 + 5;

int n;
arr<int, N> cl, rw;
arr<char, N> dr;

map<char, pii> dlt = {{'N', {-1, 0}}, {'S', {1, 0}}, {'W', {0, -1}}, {'E', {0, 1}}};
vec<vec<int>> in(int i) {
    vec<vec<int>> ans;
    if (dr[i] == 'N') {
        ans.push_back({1, cl[i], rw[i], i, 1});
        ans.push_back({3, rw[i] + cl[i], cl[i], i, 0});
        ans.push_back({5, rw[i] - cl[i], cl[i], i, 1});
    } else if (dr[i] == 'S') {
        ans.push_back({1, cl[i], rw[i], i, 0});
        ans.push_back({4, rw[i] + cl[i], cl[i], i, 1});
        ans.push_back({6, rw[i] - cl[i], cl[i], i, 0});
    } else if (dr[i] == 'W') {
        ans.push_back({2, rw[i], cl[i], i, 1});
        ans.push_back({3, rw[i] + cl[i], cl[i], i, 1});
        ans.push_back({6, rw[i] - cl[i], cl[i], i, 1});
    } else {
        ans.push_back({2, rw[i], cl[i], i, 0});
        ans.push_back({4, rw[i] + cl[i], cl[i], i, 0});
        ans.push_back({5, rw[i] - cl[i], cl[i], i, 0});
    }  
    return ans;
}
vec<int> evl(vec<int> x, vec<int> y) {
    if (x.size() != 3 || y.size() != 3) return {};
    if (x[2] == 1 || y[2] == 0) return {};
    
    int i = x[1], j = y[1];
    int dst = ((dr[i] == 'S' && dr[j] == 'N') || (dr[i] == 'E' && dr[j] == 'W')) ? (y[0] - x[0]) / 2 : (y[0] - x[0]);
    pii sqr = {rw[i] + dst * dlt[dr[i]].fir, cl[i] + dst * dlt[dr[i]].sec};

    return {dst, sqr.fir, sqr.sec};
}

map<pii, int> id;
arr<bool, N> usd;
arr<map<int, set<vec<int>>>, 10> dgn;
multiset<vec<int>> ord;

void intl() {
    for (int i = 1; i <= n; i++)
        id[{rw[i], cl[i]}] = i;

    for (int i = 1; i <= n; i++) {
        for (vec<int> x : in(i)) {
            dgn[x[0]][x[1]].insert({x[2], x[3], x[4]});
        }
    }

    for (int i = 1; i <= 6; i++) {
        for (pair<int, set<vec<int>>> x : dgn[i]) {
            for (auto it = x.sec.begin(); it != x.sec.end(); it++) {
                auto nx = next(it, 1);
                if (nx == x.sec.end()) continue;
                vec<int> y = evl(*it, *nx);
                if (y.empty()) continue;
                ord.insert(y);
            }
        }
    }

    // for (vec<int> x : ord) {
    //     cout << x[0] << " " << x[1] << " " << x[2] << '\n';
    // }
    // for (int i = 1; i <= 6; i++) {
    //     for (auto x : dgn[i]) {
    //         for (vec<int> y : x.sec)
    //             cout << y[0] << " " << y[1] << " " << y[2] << '\n';
    //         cout << '\n';
    //     }
    // }
}

void ers(int i, int j, vec<int> x) {
    auto it = dgn[i][j].find(x);
    vec<int> y = (it == dgn[i][j].begin()) ? vec<int>(0) : *next(it, -1);
    vec<int> z = (next(it, 1) == dgn[i][j].end()) ? vec<int>(0) : *next(it, 1);
    dgn[i][j].erase(it);

    vec<int> a = evl(y, x), b = evl(x, z), c = evl(y, z);
    if (a.size()) ord.erase(ord.find(a));
    if (b.size()) ord.erase(ord.find(b));
    if (c.size()) ord.insert(c);
}
void rmv(int i) {
    usd[i] = true;
    for (vec<int> x : in(i))
        ers(x[0], x[1], {x[2], x[3], x[4]});
}

vec<int> frm(int z, int x, int y) {
    vec<int> ans;
    for (char w : {'N', 'S', 'W', 'E'}) {
        int nw_x = x - z * dlt[w].fir, nw_y = y - z * dlt[w].sec;
        int i = id[{nw_x, nw_y}];
        if (!i) continue;
        if (dr[i] != w) continue;
        if (usd[i]) continue;
        ans.push_back(i);
    }
    return ans;
}

void cmp() {
    while (ord.size()) {
        // for (vec<int> x : ord) {
        //     cout << x[0] << " " << x[1] << " " << x[2] << '\n';
        // }
        // cout << '\n';

        // for (vec<int> x : dgn[4][6]) {
        //     cout << x[0] << " " << x[1] << " " << x[2] << '\n';
        // }
        // cout << '\n';

        vec<int> x = *ord.begin(); 
        for (int i : frm(x[0], x[1], x[2])) {
            rmv(i);
        }

        // for (vec<int> x : ord) {
        //     cout << x[0] << " " << x[1] << " " << x[2] << '\n';
        // }
        // cout << '\n';

        // for (vec<int> x : dgn[4][6]) {
        //     cout << x[0] << " " << x[1] << " " << x[2] << '\n';
        // }
        // cout << '\n';
    }
}

signed main() {
    // freopen("in", "r", stdin);
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> cl[i] >> rw[i] >> dr[i];

    intl();
    cmp();

    for (int i = 1; i <= n; i++)
        if (!usd[i]) cout << i << '\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: 30 / 30
• Subtask 7: 24 / 24