제출 #1080447

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1080447		anton	Naval battle (CEOI24_battle)	C++17	6 / 100	1788 ms	1048576 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;


int nz(int a){
    if(a==0){
        return 1;
    }
    else{
        return 0;
    }
}
struct Ship{
    pt pos;
    pt dir;

    pt stable_cord(){
        return {pos.real()*nz(dir.real()), pos.imag()*nz(dir.imag())};
    }
};

map<char, pt> dirs ={{'E', {1, 0}}, {'W', {-1, 0}}, {'S', {0, 1}}, {'N', {0, -1}}};



pair<pt, int> intersect(Ship a, Ship b){
    if(a.dir == b.dir){
        return {0, INF};
    }
    else{
        if(a.dir == -b.dir && a.stable_cord() == b.stable_cord()){
            return {(a.pos+b.pos)/2LL, abs(a.pos-b.pos)};
        }
        else{
            pt inter_pos = a.stable_cord()+b.stable_cord();
            if(abs(a.pos-inter_pos) == abs(b.pos-inter_pos)){
                int t = abs(a.pos-inter_pos);
                if(a.pos+t*a.dir == b.pos + t*b.dir){
                    return {inter_pos, t};
                }
                return {0, INF};
            }
            return {0, INF};
        }
    }
}
int N;
signed main(){
    cin>>N;


    vector<Ship> shipd;
    for(int i = 0; i<N; i++){
        pii pos;
        cin>>pos.first>>pos.second;
        char dir;
        cin>>dir;
        shipd.push_back(Ship{{pos.first, pos.second}, dirs[dir]});
    }

    /*auto cmp = [&](pair<pt, int>& a, pair<pt, int>& b){
        return a.second>b.second;
    };*/
    vector<pair<int, pii>> inters;

    vector<int> killed(N, INF);
    int nb_alive= N;
    for(int i = 0; i<N; i++){
        for(int j = i+1; j<N; j++){
            inters.push_back({-intersect(shipd[i], shipd[j]).second, {i, j}});
        }
    }
    sort(inters.begin(), inters.end());

    while(inters.size()>0 && inters.back().first!=-INF){
        auto cur = inters.back();
        inters.pop_back();
        cur.first *= -1;

        int t=  cur.first;

        if(killed[cur.second.first]>=t &&killed[cur.second.second]>= t){
            //cout<<cur.first<<" "<<cur.second.first+1<<" "<<cur.second.second+1<<endl;
            killed[cur.second.first]= t;
            killed[cur.second.second]= t;
            nb_alive -=2;
        }
    }

    for(int i = 0; i<N; i++){
        if(killed[i]== INF){
            cout<<i+1<<endl;
        }
    }
}

• Subtask 0: 0 / 0
• Subtask 1: 6 / 6
• Subtask 2: 0 / 12
• Subtask 3: 0 / 8
• Subtask 4: 0 / 11
• Subtask 5: 0 / 9
• Subtask 6: 0 / 30
• Subtask 7: 0 / 24