Submission #1138266

#	Time	Username	Problem	Language	Result	Execution time	Memory
1138266		altern23	Naval battle (CEOI24_battle)	C++20	6 / 100	3068 ms	193012 KiB

Main

#include <bits/stdc++.h>
using namespace std;
 
#pragma GCC optimize ("O2")
#pragma GCC optimize ("unroll-loops")
 
#define ll long long
#define pii pair<ll,ll>
#define fi first
#define sec second
#define ld long double

ostream& operator << (ostream& os, pii x){
    os << "[";
    os << " " << x.fi << " " << x.sec;
    os << " ]";
 
    return os;
}

ostream& operator << (ostream& os, pair<pii, ll> x){
    os << "[";
    os << " " << x.fi << " " << x.sec;
    os << " ]";
 
    return os;
}

ostream& operator << (ostream& os, pair<ll, pii> x){
    os << "[";
    os << " " << x.fi << " " << x.sec;
    os << " ]";
 
    return os;
}

template <typename T>
ostream& operator << (ostream& os, vector<T>tmp){
    os << "[";
    for(auto x : tmp) os << " " << x;
    os << " ]";
 
    return os;
}

template <typename T>
ostream& operator << (ostream& os, set<T>tmp){
    os << "[";
    for(auto x : tmp) os << " " << x;
    os << " ]";
 
    return os;
}
 
template <typename T>
ostream& operator << (ostream& os, multiset<T>tmp){
    os << "[";
    for(auto x : tmp) os << " " << x;
    os << " ]";
 
    return os;
}

const ll MOD = 998244353;
const ll N = 2e5;
const ll INF = 2e18;

// modulo operations
void add(ll &a, ll b) { a = (a + b) % MOD; }
void sub(ll &a, ll b) { a -= b; while(a < 0) a += MOD; a %= MOD; }
void mul(ll &a, ll b) { a = (a * b) % MOD; }

ll expo(ll a, ll b) {
    ll ans = 1;
    while(b > 0){
        if(b & 1) mul(ans, a);
        mul(a, a);
        b /= 2;
    }

    return ans;
}

ll x[N + 5], y[N + 5];
char d[N + 5];

int32_t main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int tc = 1;
    // cin >> tc;
    for(;tc--;){
        ll n; cin >> n;
        for(int i = 1; i <= n; i++) cin >> x[i] >> y[i] >> d[i];

        auto conv = [&](char cur){
            if(cur == 'N') return 0;
            if(cur == 'S') return 1;
            if(cur == 'W') return 2;
            if(cur == 'E') return 3;
        };

        
        map<ll, set<pii>> sub[4], plus[4], hori[4], verti[4];
        map<pii, char> dir;
        map<pii, ll> id;
        
        auto dist = [&](pii a, pii b){
            return abs(a.fi - b.fi) + abs(a.sec - b.sec);
        };
        
        priority_queue<pair<ll, pair<pii, pii>>> pq;
        auto upd = [&](pii a){
            char cur = dir[a];
            ll Y = a.fi, X = a.sec;
            if(cur == 'N'){
                auto cur = verti[conv('S')][X].lower_bound({Y, X});
                if(cur != verti[conv('S')][X].begin() && !verti[conv('S')][X].empty()){
                    --cur;
                    ll cost = dist({Y, X}, *(cur));
                    pq.push({-cost, {{Y, X}, *(cur)}});
                }
                cur = plus[conv('E')][X + Y].lower_bound({Y, X});
                if(cur != plus[conv('E')][X + Y].begin() && !plus[conv('E')][X + Y].empty()){
                    --cur;
                    ll cost = dist({Y, X}, *(cur));
                    pq.push({-cost, {{Y, X}, *(cur)}});
                }
                cur = sub[conv('W')][X - Y].lower_bound({Y, X});
                if(cur != sub[conv('W')][X - Y].begin() && !sub[conv('W')][X - Y].empty()){
                    --cur;
                    ll cost = dist({Y, X}, *(cur));
                    pq.push({-cost, {{Y, X}, *(cur)}});
                }
            }
            if(cur == 'S'){
                auto cur = verti[conv('N')][X].upper_bound({Y, X});
                if(cur != verti[conv('N')][X].end() && !verti[conv('N')][X].empty()){
                    ll cost = dist({Y, X}, *(cur));
                    pq.push({-cost, {{Y, X}, *(cur)}});
                }
                cur = plus[conv('E')][X + Y].upper_bound({Y, X});
                if(cur != plus[conv('E')][X + Y].end() && !plus[conv('E')][X + Y].empty()){
                    ll cost = dist({Y, X}, *(cur));
                    pq.push({-cost, {{Y, X}, *(cur)}});
                }
                cur = sub[conv('W')][X - Y].upper_bound({Y, X});
                if(cur != sub[conv('W')][X - Y].end() && !sub[conv('W')][X - Y].empty()){
                    ll cost = dist({Y, X}, *(cur));
                    pq.push({-cost, {{Y, X}, *(cur)}});
                }
            }
            if(cur == 'W'){
                auto cur = hori[conv('E')][Y].lower_bound({Y, X});
                if(cur != verti[conv('E')][Y].begin() && !verti[conv('E')][Y].empty()){
                    --cur;
                    ll cost = dist({Y, X}, *(cur));
                    pq.push({-cost, {{Y, X}, *(cur)}});
                }
                cur = sub[conv('S')][X - Y].lower_bound({Y, X});
                if(cur != sub[conv('S')][X - Y].begin() && !sub[conv('S')][X - Y].empty()){
                    --cur;
                    ll cost = dist({Y, X}, *(cur));
                    pq.push({-cost, {{Y, X}, *(cur)}});
                }
                cur = plus[conv('N')][X + Y].upper_bound({Y, X});
                if(cur != plus[conv('N')][X + Y].end() && !plus[conv('N')][X + Y].empty()){
                    ll cost = dist({Y, X}, *(cur));
                    pq.push({-cost, {{Y, X}, *(cur)}});
                }
            }
            if(cur == 'E'){
                auto cur = hori[conv('W')][Y].upper_bound({Y, X});
                if(cur != hori[conv('W')][Y].end() && !hori[conv('W')][Y].empty()){
                    ll cost = dist({Y, X}, *(cur));
                    pq.push({-cost, {{Y, X}, *(cur)}});
                }
                cur = sub[conv('N')][X - Y].upper_bound({Y, X});
                if(cur != sub[conv('N')][X - Y].end() && !sub[conv('N')][X - Y].empty()){
                    ll cost = dist({Y, X}, *(cur));
                    pq.push({-cost, {{Y, X}, *(cur)}});
                }

                cur = plus[conv('S')][X + Y].lower_bound({Y, X});
                if(cur != plus[conv('S')][X + Y].begin() && !plus[conv('S')][X + Y].empty()){
                    --cur;
                    ll cost = dist({Y, X}, *(cur));
                    pq.push({-cost, {{Y, X}, *(cur)}});
                }
            }
        };

        auto ins = [&](pii a){
            ll Y = a.fi, X = a.sec;
            char cur = dir[a];
            sub[conv(cur)][X - Y].insert({Y, X});
            plus[conv(cur)][X + Y].insert({Y, X});
            hori[conv(cur)][Y].insert({Y, X});
            verti[conv(cur)][X].insert({Y, X});
        };

        map<pii, bool> vis;
        auto del = [&](pii a){
            if(vis[a]) return;
            vis[a] = 1;
            ll Y = a.fi, X = a.sec;
            char cur = dir[a];
            sub[conv(cur)][X - Y].erase({Y, X});
            plus[conv(cur)][X + Y].erase({Y, X});
            hori[conv(cur)][Y].erase({Y, X});
            verti[conv(cur)][X].erase({Y, X});
        };

        for(int i = 1; i <= n; i++){
            id[{y[i], x[i]}] = i;
            dir[{y[i], x[i]}] = d[i];
            ins({y[i], x[i]});
        }

        // generate
        map<pii, ll> dp;
        for(int i = 1; i <= n; i++){
            upd({y[i], x[i]});
            // cout << y[i] << " " << x[i] << "\n";
            dp[{y[i], x[i]}] = INF;
        }

        for(;!pq.empty();){
            auto [cost, A] = pq.top(); pq.pop();
            cost *= -1;
            if(dp[A.fi] >= cost && dp[A.sec] >= cost){
                dp[A.fi] = cost, dp[A.sec] = cost;
                continue;
            }
            else{
                if(dp[A.fi] >= cost) upd(A.fi);
                else del(A.fi);
                if(dp[A.sec] >= cost) upd(A.sec);
                else del(A.sec);
            }
        }

        vector<ll> v;
        for(auto &[now, time] : dp){
            if(time == INF){
                v.push_back(id[now]);
            }
        }

        for(auto &x : v) cout << x << "\n";
    }   
}

/*

*/

Compilation message (stderr)

Main.cpp: In lambda function:
Main.cpp:100:9: warning: control reaches end of non-void function [-Wreturn-type]
  100 |         };
      |         ^

• 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