Submission #1208331

#	Time	Username	Problem	Language	Result	Execution time	Memory
1208331		HappyCapybara	Naval battle (CEOI24_battle)	C++20	6 / 100	3102 ms	159784 KiB

Main

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

#define int long long

pair<int,int> bruh = {1<<30, 1<<30};
unordered_map<char,unordered_map<int,set<pair<int,int>>>> rows, cols, ru, rd;

pair<int,int> gt(set<pair<int,int>>& s, int x){
    auto it = s.upper_bound({x, -1});
    if (it == s.end()) return bruh;
    return *it;
}

pair<int,int> lt(set<pair<int,int>>& s, int x){
    auto it = s.upper_bound({x, -1});
    if (it == s.begin()) return bruh;
    it--;
    return *it;
}

pair<int,int> find_next(int x, int y, char d){
    pair<int,int> res = bruh;
    if (d == 'N'){
        pair<int,int> pi = lt(cols['S'][x], y);
        if (pi != bruh) res = min(res, {abs(pi.first-y)/2, pi.second});
        pi = gt(ru['W'][x+y], x);
        if (pi != bruh) res = min(res, {abs(pi.first-x), pi.second});
        pi = lt(rd['E'][x-y], x);
        if (pi != bruh) res = min(res, {abs(pi.first-x), pi.second});
    }
    if (d == 'S'){
        pair<int,int> pi = gt(cols['N'][x], y);
        if (pi != bruh) res = min(res, {abs(pi.first-y)/2, pi.second});
        pi = lt(ru['E'][x+y], x);
        if (pi != bruh) res = min(res, {abs(pi.first-x), pi.second});
        pi = gt(rd['W'][x-y], x);
        if (pi != bruh) res = min(res, {abs(pi.first-x), pi.second});
    }
    if (d == 'E'){
        pair<int,int> pi = gt(rows['W'][y], x);
        if (pi != bruh) res = min(res, {abs(pi.first-x)/2, pi.second});
        pi = gt(ru['S'][x+y], x);
        if (pi != bruh) res = min(res, {abs(pi.first-x), pi.second});
        pi = gt(rd['N'][x-y], x);
        if (pi != bruh) res = min(res, {abs(pi.first-x), pi.second});
    }
    if (d == 'W'){
        pair<int,int> pi = lt(rows['E'][y], x);
        if (pi != bruh) res = min(res, {abs(pi.first-x)/2, pi.second});
        pi = lt(ru['N'][x+y], x);
        if (pi != bruh) res = min(res, {abs(pi.first-x), pi.second});
        pi = lt(rd['S'][x-y], x);
        if (pi != bruh) res = min(res, {abs(pi.first-x), pi.second});
    }
    return res;
}

signed main(){
    //freopen("out.txt", "w", stdout);
    cin.tie(0);
    iostream::sync_with_stdio(false);
    int n;
    cin >> n;
    vector<int> x(n), y(n);
    vector<char> d(n);
    for (int i=0; i<n; i++){
        cin >> x[i] >> y[i] >> d[i];
        rows[d[i]][y[i]].insert({x[i], i});
        cols[d[i]][x[i]].insert({y[i], i});
        ru[d[i]][x[i]+y[i]].insert({x[i], i});
        rd[d[i]][x[i]-y[i]].insert({x[i], i});
    }
    set<pair<int,pair<int,int>>> nc;
    for (int i=0; i<n; i++){
        pair<int,int> next = find_next(x[i], y[i], d[i]);
        //cout << next.first << " " << next.second << endl;
        if (next != bruh) nc.insert({next.first, {i, next.second}});
    }
    vector<bool> alive(n, true);
    vector<int> tod(n);
    while (true /*!nc.empty()*/){
        pair<int,pair<int,int>> cur = {1<<30, bruh};//*nc.begin();
        for (int i=0; i<n; i++){
            if (!alive[i]) continue;
            pair<int,int> next = find_next(x[i], y[i], d[i]);
            cur = min(cur, {next.first, {i, next.second}});
        }
        if (cur.first == 1<<30) break;
        //nc.erase(nc.begin());
        int a = cur.second.first, b = cur.second.second;
        //cout << a << " " << b << endl;
        if (alive[a] && alive[b]){
            alive[a] = false;
            tod[a] = cur.first;
            rows[d[a]][y[a]].erase({x[a], a});
            cols[d[a]][x[a]].erase({y[a], a});
            ru[d[a]][x[a]+y[a]].erase({x[a], a});
            rd[d[a]][x[a]-y[a]].erase({x[a], a});
            alive[b] = false;
            tod[b] = cur.first;
            rows[d[b]][y[b]].erase({x[b], b});
            cols[d[b]][x[b]].erase({y[b], b});
            ru[d[b]][x[b]+y[b]].erase({x[b], b});
            rd[d[b]][x[b]-y[b]].erase({x[b], b});
        }
        if (alive[a] && !alive[b]){
            if (tod[b] == cur.first){
                alive[a] = false;
                tod[a] = cur.first;
                rows[d[a]][y[a]].erase({x[a], a});
                cols[d[a]][x[a]].erase({y[a], a});
                ru[d[a]][x[a]+y[a]].erase({x[a], a});
                rd[d[a]][x[a]-y[a]].erase({x[a], a});
                continue;
            }
            pair<int,int> next = find_next(x[a], y[a], d[a]);
            if (next != bruh){
                nc.insert({next.first, {a, next.second}});
                //assert(alive[next.second]);
                //assert(next.first >= cur.first);
            }
        }
        if (alive[b] && !alive[a]){
            if (tod[a] == cur.first){
                alive[b] = false;
                tod[b] = cur.first;
                rows[d[b]][y[b]].erase({x[b], b});
                cols[d[b]][x[b]].erase({y[b], b});
                ru[d[b]][x[b]+y[b]].erase({x[b], b});
                rd[d[b]][x[b]-y[b]].erase({x[b], b});
                continue;
            }
            pair<int,int> next = find_next(x[b], y[b], d[b]);
            if (next != bruh){
                nc.insert({next.first, {b, next.second}});
                //assert(alive[next.second]);
                //assert(next.first >= cur.first);
            }
        }
    }
    for (int i=0; i<n; i++){
        if (alive[i]) cout << i+1 << endl;
    }
}

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