Submission #1080452

#	Time	Username	Problem	Language	Result	Execution time	Memory
1080452		anton	Naval battle (CEOI24_battle)	C++17	6 / 100	1444 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{
        pt inter_pos = 0;

        if(a.dir == -b.dir && a.stable_cord() == b.stable_cord()){
            inter_pos = (a.pos+b.pos)/2LL;
        }
        else{
            inter_pos = a.stable_cord()+b.stable_cord();
        }
        int t = abs(a.pos-inter_pos);
        if(a.pos+t*a.dir == inter_pos && b.pos+t*b.dir == inter_pos){
            return {inter_pos, t};
        }
        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());

    for(int i = 0; i<inters.size(); i++){
        auto cur = inters[i];
        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;
        }
    }
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:80:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   80 |     for(int i = 0; i<inters.size(); i++){
      |                    ~^~~~~~~~~~~~~~

• 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