Submission #1231130

#	Time	Username	Problem	Language	Result	Execution time	Memory
1231130		alexander707070	Naval battle (CEOI24_battle)	C++20	100 / 100	1697 ms	178176 KiB

Main

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

const int inf=2e9;

struct ship{
    int x,y,id;
    int type;
}s[MAXN];

/*
 1
4X2
 3

*/

int n;
unordered_map< int , set<pair<int,int> > > raz[5],sum[5],xs[5],ys[5];
priority_queue< pair<int,int> , vector< pair<int,int> > , greater< pair<int,int> > > q;

char c;

int tim[MAXN];
vector<int> opt[MAXN];

bool dead[MAXN];

void add(int i){
    xs[s[i].type][s[i].x].insert({s[i].y,i});
    ys[s[i].type][s[i].y].insert({s[i].x,i});

    sum[s[i].type][s[i].x+s[i].y].insert({s[i].x-s[i].y,i});
    raz[s[i].type][s[i].x-s[i].y].insert({s[i].x+s[i].y,i});
}

void rem(int i){
    xs[s[i].type][s[i].x].erase({s[i].y,i});
    ys[s[i].type][s[i].y].erase({s[i].x,i});

    sum[s[i].type][s[i].x+s[i].y].erase({s[i].x-s[i].y,i});
    raz[s[i].type][s[i].x-s[i].y].erase({s[i].x+s[i].y,i});
}

void check(int x,int y){
    int curr=max(abs(s[x].x-s[y].x),abs(s[x].y-s[y].y));
    if( abs(s[x].type-s[y].type)==2 )curr/=2;

    if(curr<tim[x]){
        tim[x]=curr; opt[x]={y};
    }else if(curr==tim[x]){
        opt[x].push_back(y);
    }
}

void calculate(int i){
    tim[i]=inf; opt[i]={};

    if(s[i].type==1){
        auto it=xs[3][s[i].x].lower_bound({s[i].y,0});
        
        if(it!=xs[3][s[i].x].end()){
            auto p=*it;
            check(i,p.second);
        }

        it=raz[4][s[i].x-s[i].y].lower_bound({s[i].x+s[i].y,0});

        if(it!=raz[4][s[i].x-s[i].y].end()){
            auto p=*it;
            check(i,p.second);
        }

        it=sum[2][s[i].x+s[i].y].lower_bound({s[i].x-s[i].y,0});

        if(it!=sum[2][s[i].x+s[i].y].begin()){
            it--; auto p=*it;
            check(i,p.second);
        }

    }else if(s[i].type==3){

        auto it=xs[1][s[i].x].lower_bound({s[i].y,0});
        
        if(it!=xs[1][s[i].x].begin()){
            it--; auto p=*it;
            check(i,p.second);
        }

        it=raz[2][s[i].x-s[i].y].lower_bound({s[i].x+s[i].y,0});

        if(it!=raz[2][s[i].x-s[i].y].begin()){
            it--; auto p=*it;
            check(i,p.second);
        }

        it=sum[4][s[i].x+s[i].y].lower_bound({s[i].x-s[i].y,0});

        if(it!=sum[4][s[i].x+s[i].y].end()){
            auto p=*it;
            check(i,p.second);
        }
    }else if(s[i].type==2){
        auto it=ys[4][s[i].y].lower_bound({s[i].x,0});
        
        if(it!=ys[4][s[i].y].end()){
            auto p=*it;
            check(i,p.second);
        }

        it=raz[3][s[i].x-s[i].y].lower_bound({s[i].x+s[i].y,0});

        if(it!=raz[3][s[i].x-s[i].y].end()){
            auto p=*it;
            check(i,p.second);
        }

        it=sum[1][s[i].x+s[i].y].lower_bound({s[i].x-s[i].y,0});

        if(it!=sum[1][s[i].x+s[i].y].end()){
            auto p=*it;
            check(i,p.second);
        }
    }else if(s[i].type==4){
        auto it=ys[2][s[i].y].lower_bound({s[i].x,0});
        
        if(it!=ys[2][s[i].y].begin()){
            it--; auto p=*it;
            check(i,p.second);
        }

        it=raz[1][s[i].x-s[i].y].lower_bound({s[i].x+s[i].y,0});

        if(it!=raz[1][s[i].x-s[i].y].begin()){
            it--; auto p=*it;
            check(i,p.second);
        }

        it=sum[3][s[i].x+s[i].y].lower_bound({s[i].x-s[i].y,0});
        if(it!=sum[3][s[i].x+s[i].y].begin()){
            it--; auto p=*it;
            check(i,p.second);
        }
    }
}

int main(){

    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin>>n;

    for(int i=1;i<=n;i++){
        cin>>s[i].x>>s[i].y>>c;
        s[i].id=i;

        if(c=='N')s[i].type=3;
        if(c=='E')s[i].type=2;
        if(c=='S')s[i].type=1;
        if(c=='W')s[i].type=4;

        add(i);
    }

    for(int i=1;i<=n;i++){
        calculate(i);
        q.push({tim[i],i});
    }

    while(!q.empty()){
        auto p=q.top();
        q.pop();

        if(dead[p.second] or p.first==inf)continue;
        
        calculate(p.second);

        if(tim[p.second]!=p.first){
            q.push({tim[p.second],p.second});
            continue;
        }

        dead[p.second]=true;
        rem(p.second);
        
        for(int i:opt[p.second]){
            dead[i]=true;
            rem(i);
        }

        for(int i:opt[p.second]){
            add(i);
            calculate(i);

            for(int f:opt[i]){
                calculate(f);
                q.push({tim[f],f});
            }

            rem(i);
        }

        add(p.second);
        calculate(p.second);

        for(int f:opt[p.second]){
            calculate(f);
            q.push({tim[f],f});
        }

        rem(p.second);
    }

    for(int i=1;i<=n;i++){
        if(!dead[i])cout<<i<<"\n";
    }

    return 0;
}

• 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