Submission #1193038

#	Time	Username	Problem	Language	Result	Execution time	Memory
1193038		Unforgettablepl	Naval battle (CEOI24_battle)	C++20	100 / 100	1344 ms	156724 KiB

Main

#pragma GCC optimize("Ofast","unroll-loops")
#include <bits/stdc++.h>
using namespace std;

#define int long long

enum direction{
    north,
    south,
    east,
    west,
};

enum slant{
    diff,
    sum,
    headon,
};

struct ship{
    int x,y;
    direction d;
};

int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int N;
    cin >> N;
    vector<ship> ships(N+1);
    vector shipLookup(4,vector<map<int,set<pair<int,int>>>>(3)); 
    for(int i=1;i<=N;i++){
        char d;
        cin >> ships[i].x >> ships[i].y >> d;
        switch(d){
            case 'S': ships[i].d = north; break;
            case 'N': ships[i].d = south; break;
            case 'E': ships[i].d = east; break;
            case 'W': ships[i].d = west; break;
        }
        shipLookup[ships[i].d][diff][ships[i].x-ships[i].y].emplace(ships[i].x,i);
        shipLookup[ships[i].d][sum][ships[i].x+ships[i].y].emplace(ships[i].x,i);
        if(ships[i].d == north or ships[i].d==south){
            shipLookup[ships[i].d][headon][ships[i].x].emplace(ships[i].y,i);
        } else {
            shipLookup[ships[i].d][headon][ships[i].y].emplace(ships[i].x,i);
        }
    }
    priority_queue<pair<int,int>> pq;

    auto getCollision = [&](ship boat){
        pair<int,vector<int>> ans = {1e12,{}};
        auto addJustAfter = [&](direction d,slant s){
            pair<int,int> q;
            int idx,l;
            if(s==diff){
                idx = boat.x-boat.y;
                l=boat.x;
            }
            if(s==sum){
                idx = boat.x + boat.y;
                l = boat.x;
            }
            if(s==headon){
                if(d==north or d==south){
                    idx = boat.x;
                    l = boat.y;
                } else {
                    idx = boat.y;
                    l = boat.x;
                }
            }
            auto iter = shipLookup[d][s][idx].upper_bound({l,0ll});
            if(iter!=shipLookup[d][s][idx].end()){
                q.second = iter->second;
                q.first = (abs(boat.x-ships[q.second].x)+abs(boat.y-ships[q.second].y))/2ll;
                if(q.first<ans.first){ans.second.clear();ans.first=q.first;}
                if(q.first==ans.first)ans.second.emplace_back(q.second);
            }
        };
        auto addJustBefore = [&](direction d,slant s){
            pair<int,int> q;
            int idx,l;
            if(s==diff){
                idx = boat.x-boat.y;
                l=boat.x;
            }
            if(s==sum){
                idx = boat.x + boat.y;
                l = boat.x;
            }
            if(s==headon){
                if(d==north or d==south){
                    idx = boat.x;
                    l = boat.y;
                } else {
                    idx = boat.y;
                    l = boat.x;
                }
            }
            auto iter = shipLookup[d][s][idx].upper_bound({l,0ll});
            if(iter!=shipLookup[d][s][idx].begin()){
                iter--;
                q.second = iter->second;
                q.first = (abs(boat.x-ships[q.second].x)+abs(boat.y-ships[q.second].y))/2ll;
                if(q.first<ans.first){ans.second.clear();ans.first=q.first;}
                if(q.first==ans.first)ans.second.emplace_back(q.second);
            }
        };
        if(boat.d==north){
            addJustAfter(west,diff);
            addJustBefore(east,sum);
            addJustAfter(south,headon);
        }
        if(boat.d==south){
            addJustAfter(west,sum);
            addJustBefore(east,diff);
            addJustBefore(north,headon);
        }
        if(boat.d==east){
            addJustAfter(south,diff);
            addJustAfter(north,sum);
            addJustAfter(west,headon);
        }
        if(boat.d==west){
            addJustBefore(south,sum);
            addJustBefore(north,diff);
            addJustBefore(east,headon);
        }
        return ans;
    };
    auto eraseShip = [&](int i){
        shipLookup[ships[i].d][diff][ships[i].x-ships[i].y].erase({ships[i].x,i});
        shipLookup[ships[i].d][sum][ships[i].x+ships[i].y].erase({ships[i].x,i});
        if(ships[i].d == north or ships[i].d==south){
            shipLookup[ships[i].d][headon][ships[i].x].erase({ships[i].y,i});
        } else {
            shipLookup[ships[i].d][headon][ships[i].y].erase({ships[i].x,i});
        }
    };
    vector<bool> visited(N+1);
    function<bool(int,int)> dfs = [&](int x,int tim){
        visited[x]=true;
        eraseShip(x);        
        while(true){
            auto t = getCollision(ships[x]);
            if(t.first>=tim){
                return true;
            }
            bool works = false;
            for(int&i:t.second)if(dfs(i,t.first)){
                works=true;
            }
            if(works){
                return false;
            }
        }
    };
    for(int i=1;i<=N;i++)if(!visited[i]){
        if(dfs(i,1e10)){
            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