Submission #1080829

#	Time	Username	Problem	Language	Result	Execution time	Memory
1080829		anton	Naval battle (CEOI24_battle)	C++17	76 / 100	3025 ms	311336 KiB

Main

#include<bits/stdc++.h>

using namespace std;
#define int long long
#define pii pair<int, int>
#define pt complex<int>

const int INF = 1e18;

struct Event{
    int len;
    int lship_id, rship_id;
    int dim_id, dim_pos;
    bool operator<(const Event& b)const{
        if(len != b.len){
            return len<b.len;
        }
        if(lship_id != b.lship_id){
            return lship_id < b.lship_id;
        }
        if(rship_id != b.rship_id){
            return rship_id < b.rship_id;
        }
        if(dim_id != b.dim_id){
            return dim_id < b.dim_id;
        }
            
        return dim_pos < b.dim_pos;
    }
};

struct Ship{
    int id;
    pt pos;
    int dist_right = -1;
    char dir_letter;
    bool operator<(const Ship& b)const{
        return false;
    }
};


set<Event> lens;

struct Line{
    int dim_id, dim_pos;
    list<pair<int, Ship>> ships;
    map<int, list<pair<int, Ship>>::iterator> m;
    char go_left, go_right;
    void insert_event(list<pair<int, Ship>>::iterator a, list<pair<int, Ship>>::iterator b){
        lens.insert(Event{Event{b->first-a->first, a->second.id, b->second.id, dim_id, dim_pos}});
    }
    void erase_event(list<pair<int, Ship>>::iterator a, list<pair<int, Ship>>::iterator b){
        lens.erase(Event{Event{b->first-a->first, a->second.id, b->second.id, dim_id, dim_pos}});
    }
    
    void make_pair(list<pair<int, Ship>>::iterator a, list<pair<int, Ship>>::iterator b){
        if(b== ships.end()){
            return;
        }
        if(a->second.dir_letter == go_right){
            if(b->second.dir_letter == go_left){
                a->second.dist_right = b->first-a->first;
                insert_event(a, b);
            }
        }
    }
    void unmake_pair(list<pair<int, Ship>>::iterator a, list<pair<int, Ship>>::iterator b){
        if(b== ships.end()){
            return;
        }
        if(a->second.dir_letter == go_right){
            if(b->second.dir_letter == go_left){
                a->second.dist_right = -1;
                erase_event(a, b);
            }
        }
    }
    void build(vector<pair<int, Ship>> elems, char go_right_dir, char go_left_dir){
        go_right = go_right_dir;
        go_left=  go_left_dir;
        sort(elems.begin(), elems.end());
        ships = list<pair<int, Ship>>(elems.begin(), elems.end());
        auto it = ships.begin();

        for(; it!=ships.end();){
            if(it->second.dir_letter != go_right_dir && it->second.dir_letter != go_left_dir){
                it = ships.erase(it);
            }
            else{
                ++it;
            }
        }
        it = ships.begin();
        for(; it!=ships.end(); ++it){
            m[it->second.id]= it;
            auto next= it;
            ++next;
            make_pair(it, next);
        }
    }
    void erase(list<pair<int, Ship>>::iterator it){
        if(it!=ships.begin()){
            auto prev = it;
            --prev;
            unmake_pair(prev, it);
        } 
        if(it != ships.end()){
            auto next=  it;
            ++next;
            unmake_pair(it, next);
        }    
        auto next = ships.erase(it);
        if(next!=ships.begin()){
            auto prev= next;
            --prev;
            make_pair(prev, next);
        }
    }

    void erase(int ship_id){
        if(m.find(ship_id) == m.end()){
            return;
        }
        erase(m[ship_id]);
        m.erase(ship_id);
    }
};

vector<char> go_right = {'E', 'S', 'E', 'N', 'E', 'S'};
vector<char> go_left = {'W', 'N', 'S', 'W', 'N', 'W'};
vector<pt> coef_orth = {{0, 1}, {1, 0}, {1, 1}, {1, 1}, {1, -1}, {1, -1}};
vector<pt> coef_col = {{1, 0}, {0, 1}, {1, -1}, {1, -1}, {1, 1}, {1, 1}};

int dot(pt a, pt b){
    return (a*conj(b)).real();
}
pii get_pos(Ship s, int dim){
    return {dot(s.pos,coef_orth[dim]), dot(s.pos, coef_col[dim])}; 
}
vector<Ship> ships;
int N;


signed main(){
    cin>>N;
    for(int i = 0; i<N; i++){
        pii pos;
        cin>>pos.first>>pos.second;
        char dir;
        cin>>dir;
        ships.push_back(Ship{i, {pos.first, pos.second},-1, dir});
    }
    vector<map<int, Line>> dims(6);

    vector<vector<pii>> ship_coords(6, vector<pii> (N));
    for(int dim = 0; dim<6; dim++){
        map<int, vector<pair<int, Ship>>> categorized;
        for(auto ship: ships){
            pii dim_coord = get_pos(ship, dim);

            categorized[dim_coord.first].push_back({dim_coord.second, ship});
            ship_coords[dim][ship.id] = dim_coord;
        }
        for(auto e: categorized){
            dims[dim][e.first].dim_id = dim;
            dims[dim][e.first].dim_pos = e.first;
            dims[dim][e.first].build(e.second, go_right[dim], go_left[dim]);
        }
    }


    set<int> alive;
    for(int i = 0; i<N; i++){
        alive.insert(i);
    }

    
    while(lens.size()>0){
        int t= lens.begin()->len;
        vector<Event> cur_events;
        auto it= lens.begin();
        while(it!=lens.end() && it->len == t){
            cur_events.push_back(*it);
            ++it;
        }

        for(auto e: cur_events){
            vector<int> to_remove = {e.lship_id, e.rship_id};
            for(auto rem: to_remove){
                alive.erase(rem);
                for(int dim = 0; dim<6; dim++){
                    int dim_pos = ship_coords[dim][rem].first;
                    dims[dim][dim_pos].erase(rem);
                }
            }
        }
    }

    for(auto e: alive){
        cout<<e+1<<endl;
    }
}

• 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: 0 / 24