Submission #1080804

#	Time	Username	Problem	Language	Result	Execution time	Memory
1080804		Arturgo	Naval battle (CEOI24_battle)	C++14	0 / 100	996 ms	193304 KiB

Main

#include <bits/stdc++.h>
#define int long long
using namespace std;

struct Point {
    int x, y, dir;
};

int NORD = 0, OUEST = 1, SUD = 2, EST = 3;
map<char, int> to_dir = {{'N', NORD}, {'W', OUEST}, {'S', SUD}, {'E', EST}};
vector<Point> dirs = {{0, -1, NORD}, {-1, 0, OUEST}, {0, 1, SUD}, {1, 0, EST}};

pair<int, int> rotate(pair<int, int> pt) {
    return {pt.first + pt.second, pt.second - pt.first};
}

struct Collision {
    int id1, id2, temps;
};

bool operator < (const Collision& a, const Collision& b) {
    return a.temps > b.temps;
}

int nbPoints;
vector<Point> points;
vector<bool> estEnVie;

struct Point1D {
    int id, pos, sens;
};

bool operator < (const Point1D& a, const Point1D& b) {
    return a.pos < b.pos;
}

struct Diagonale {
    Collision suiv_collision;
    priority_queue<Collision> collisions;

    list<Point1D> elems;
    map<int, list<Point1D>::iterator> its;

    void etudie(const Point1D& a, const Point1D& b) {
        if(a.sens > b.sens) {
            collisions.push({a.id, b.id, b.pos - a.pos});
        } 
    }

    void update() {
        while(!collisions.empty()) {
            Collision col = collisions.top();

            if(estEnVie[col.id1] && estEnVie[col.id2]) break;
            else collisions.pop();
        }

        if(collisions.empty()) suiv_collision = {-1, -1, -1};
        else suiv_collision = collisions.top();
    }

    void init() {
        vector<Point1D> elemsVec(elems.begin(), elems.end());
        sort(elemsVec.begin(), elemsVec.end());
        elems = list<Point1D>(elemsVec.begin(), elemsVec.end());

        for(auto it = elems.begin();it != elems.end();it++) {
            its[it->id] = it;
            if(next(it) != elems.end()) {
                etudie(*it, *next(it));
            }
        }

        update();
    }

    void supprimer(int id) {
        auto it = its[id];
        auto itSuiv = elems.erase(it);
        
        if(itSuiv != elems.begin() && itSuiv != elems.end()) {
            auto itPrec = prev(itSuiv);
            etudie(*itPrec, *itSuiv);
        }

        update();
    }
};

vector<vector<Diagonale*>> diagonales;
vector<map<int, Diagonale*>> directions(6);

void ajoute(int dir, int coord1, int coord2, int id, int sens) {
    if(!directions[dir].count(coord1)) directions[dir][coord1] = new Diagonale{};
    directions[dir][coord1]->elems.push_back({id, coord2, sens});
    diagonales[id].push_back(directions[dir][coord1]);
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin >> nbPoints;
    estEnVie = vector<bool>(nbPoints, true);
    diagonales = vector<vector<Diagonale*>>(nbPoints);

    for(int iPoint = 0;iPoint < nbPoints;iPoint++) {
        int x, y; char type;
        cin >> x >> y >> type;
        points.push_back({x, y, to_dir[type]});
    }

    for(int iPoint = 0;iPoint < nbPoints;iPoint++) {
        Point& p = points[iPoint];

        pair<int, int> coords = {p.x, p.y};
        pair<int, int> dir = {dirs[p.dir].x, dirs[p.dir].y};
        
        if(dir.first != 0) ajoute(4, coords.second, coords.first, iPoint, dir.first);
        if(dir.second != 0) ajoute(5, coords.first, coords.second, iPoint, dir.second);

        if(p.dir == NORD || p.dir == OUEST) {
            ajoute(0, coords.first + coords.second, coords.second - coords.first, iPoint, (p.dir == NORD)?-1:1);
        }
        if(p.dir == EST || p.dir == NORD) {
            ajoute(1, coords.second - coords.first, coords.first + coords.second, iPoint, (p.dir == NORD)?-1:1);
        }

        if(p.dir == SUD || p.dir == OUEST) {
            ajoute(2, coords.first + coords.second, coords.second - coords.first, iPoint, (p.dir == SUD)?1:-1);
        }
        if(p.dir == EST || p.dir == SUD) {
            ajoute(3, coords.second - coords.first, coords.first + coords.second, iPoint, (p.dir == SUD)?1:-1);
        }
    }

    priority_queue<Collision> collisions;
    for(int dir = 0;dir < 6;dir++) {
        for(auto it = directions[dir].begin();it != directions[dir].end();it++) {
            it->second->init();
            if(it->second->suiv_collision.temps != -1) {
                collisions.push(it->second->suiv_collision);
            }
        }
    }

    while(!collisions.empty()) {
        vector<int> aSupprimer;
        
        int temps = collisions.top().temps;
        //cerr << "time: " << temps << endl;
        while(!collisions.empty() && collisions.top().temps == temps) {
            Collision col = collisions.top();
            collisions.pop();

            if(estEnVie[col.id1] && estEnVie[col.id2]) {
                //cerr << col.id1 + 1 << " " << col.id2 + 1 << endl;
                aSupprimer.push_back(col.id1);
                aSupprimer.push_back(col.id2);
            }
        }

        sort(aSupprimer.begin(), aSupprimer.end());
        aSupprimer.erase(unique(aSupprimer.begin(), aSupprimer.end()), aSupprimer.end());

        for(int id : aSupprimer) {
            //cerr << 1 + id << " ";
            estEnVie[id] = false;

            for(Diagonale* diag : diagonales[id]) {
                diag->supprimer(id);
            }
        }
        //cerr << endl;

        for(int id : aSupprimer) {
            for(Diagonale* diag : diagonales[id]) {
                if(diag->suiv_collision.temps != -1) {
                    collisions.push(diag->suiv_collision);
                }
            }
        }

        while(!collisions.empty()) {
            Collision col = collisions.top();
            if(estEnVie[col.id1] && estEnVie[col.id2]) break;
            else collisions.pop();
        }
    }

    for(int dir = 0;dir < 6;dir++) {
        for(auto it = directions[dir].begin();it != directions[dir].end();it++) {
            delete it->second;
        }
    }

    for(int iPoint = 0;iPoint < nbPoints;iPoint++) {
        if(estEnVie[iPoint]) {
            cout << iPoint + 1 << " ";
        }
    }
    cout << endl;
    
    return 0;
}

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