Submission #1080481

#	Time	Username	Problem	Language	Result	Execution time	Memory
1080481		anton	Naval battle (CEOI24_battle)	C++17	30 / 100	466 ms	48612 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;
    char dir_letter;

    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], dir});
    }

    map<int, map<int, pair<int, char>>> diags;
    for(int i = 0; i<shipd.size(); i++){
        auto ship = shipd[i];
        diags[ship.pos.real() + ship.pos.imag()][ship.pos.real()-ship.pos.imag()] = {i, ship.dir_letter};
    }

    /*for(auto e: diags){
        cout<<e.first<<" ";
        for(auto ee: e.second){
            cout<<"( "<<ee.second.first<<" "<<ee.second.second<<" )"<<" ";
        }
        cout<<endl;
    }*/


    vector<int>res;

    for(auto diag: diags){
        vector<int> left_unmatched;
        for(auto ship: diag.second){
            if(ship.second.second =='E'){
                left_unmatched.push_back(ship.second.first);
            }
            else if(left_unmatched.size()>0){
                left_unmatched.pop_back();
            }
            else{
                res.push_back(ship.second.first);
            }
        }
        for(auto e: left_unmatched){
            res.push_back(e);
        }
    }
    /*for(int i = 0; i<N; i++){
        if(killed[i]== INF){
            cout<<i+1<<endl;
        }
    }*/

   for(auto e: res){
    cout<<e+1<<endl;
   }
}

Compilation message (stderr)

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

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