Submission #1231115

#	Time	Username	Problem	Language	Result	Execution time	Memory
1231115		alexander707070	Naval battle (CEOI24_battle)	C++20	46 / 100	3100 ms	133952 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];
char c;

int tim[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;

    tim[x]=min(tim[x],curr);
}

bool calc(){
    for(int i=1;i<=n;i++)tim[i]=inf;

    for(int i=1;i<=n;i++){
        if(dead[i])continue;

        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 mins=inf;
    for(int i=1;i<=n;i++){
        mins=min(mins,tim[i]);
    }

    if(mins==inf)return false;

    for(int i=1;i<=n;i++){
        if(tim[i]!=mins)continue;

        dead[i]=true;
        rem(i);
    }

    return true;
}

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);
    }

    while(calc());

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