Submission #1040482

#	Time	Username	Problem	Language	Result	Execution time	Memory
1040482		isaachew	Naval battle (CEOI24_battle)	C++17	100 / 100	1106 ms	103608 KiB

Main

#include <bits/stdc++.h>
/*
 40 points: see which pairs of ships can collide, sim those collisions (simultaneously if on same timestep)
 30 points: ships will collide iff they are on the same diagonal
 If a ship gets sunk, lines are updated
 */
std::map<int,std::map<int,std::pair<int,int>>> nediag,nwdiag,sediag,swdiag;//only "right-facing" ships will work
//type 1 faces forward, type -1 faces backwards
std::map<int,std::map<int,std::pair<int,int>>> horizls,vertls;//only East/South ships will work
std::map<int,std::vector<std::pair<int,int>>> collisions;// time, collisions
void setcolls(std::map<int,std::pair<int,int>>& cmap){
    std::pair<int,std::pair<int,int>> lasts={0,{0,0}};
    for(std::pair<int,std::pair<int,int>> ship:cmap){
        if(lasts.second.second==1&&ship.second.second==-1){
            collisions[(ship.first-lasts.first)/2].push_back({lasts.second.first,ship.second.first});
        }
        lasts=ship;
    }
}
void setmap(std::map<int,std::map<int,std::pair<int,int>>>& cmap){
    for(std::pair<int,std::map<int,std::pair<int,int>>> mp:cmap){
        setcolls(mp.second);
    }
}
void remship(std::map<int,std::pair<int,int>>& cmap,int index){//remove that ship
    cmap.erase(index);
    auto nextship=cmap.lower_bound(index);
    
    if(nextship!=cmap.begin()){
        auto prevship=nextship;
        prevship--;//is ship to left of removed
        if(prevship->second.second==1&&nextship->second.second==-1){
            collisions[(nextship->first-prevship->first)/2].push_back({prevship->second.first,nextship->second.first});
        }
    }
}
int main(){
    int n;
    std::cin>>n;
    std::vector<std::pair<std::pair<int,int>,char>> ships;
    std::vector<int> status(n,1);
    for(int i=0;i<n;i++){
        int x,y;
        char c;
        std::cin>>x>>y;
        std::cin>>c;
        ships.push_back({{x,y},c});
        switch(c){
            case 'E':
                nediag[x-y][x+y]={i,1};
                sediag[x+y][x-y]={i,1};
                horizls[y][x]={i,1};
                break;
            case 'W':
                nwdiag[x+y][x-y]={i,-1};
                swdiag[x-y][x+y]={i,-1};
                horizls[y][x]={i,-1};
                break;
            case 'N':
                nwdiag[x+y][x-y]={i,1};
                nediag[x-y][x+y]={i,-1};
                vertls[x][y]={i,-1};
                break;
            case 'S':
                swdiag[x-y][x+y]={i,1};
                sediag[x+y][x-y]={i,-1};
                vertls[x][y]={i,1};
                break;
        }
    }
    setmap(nediag);
    setmap(nwdiag);
    setmap(sediag);
    setmap(swdiag);
    setmap(horizls);
    setmap(vertls);
    auto cstart=collisions.begin();
    while(cstart!=collisions.end()){
        std::vector<std::pair<int,int>> colls=cstart->second;
        std::set<int> todel;
        for(std::pair<int,int> coll:colls){
            if(status[coll.first]==1&&status[coll.second]==1){
                todel.insert(coll.first);
                todel.insert(coll.second);
            }
        }
        for(int i:todel){
            int x=ships[i].first.first;
            int y=ships[i].first.second;
            switch(ships[i].second){
                case 'E':
                    remship(nediag[x-y],x+y);
                    remship(sediag[x+y],x-y);
                    remship(horizls[y],x);
                    break;
                case 'W':
                    remship(nwdiag[x+y],x-y);
                    remship(swdiag[x-y],x+y);
                    remship(horizls[y],x);
                    break;
                case 'N':
                    remship(nwdiag[x+y],x-y);
                    remship(nediag[x-y],x+y);
                    remship(vertls[x],y);
                    break;
                case 'S':
                    remship(swdiag[x-y],x+y);
                    remship(sediag[x+y],x-y);
                    remship(vertls[x],y);
                    break;
            }
            status[i]=0;
        }
        cstart=collisions.erase(cstart);
    }
    for(int i=0;i<n;i++){
        if(status[i])std::cout<<i+1<<'\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