제출 #1080891

#제출 시각아이디문제언어결과실행 시간메모리
1080891ArturgoNaval battle (CEOI24_battle)C++14
100 / 100
1136 ms170972 KiB
#include <bits/stdc++.h> #define int long long using namespace std; struct Point { int x, y; char dir; }; 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; priority_queue<Collision> collisions; struct Point1D { int id, pos, sens; }; bool operator < (const Point1D& a, const Point1D& b) { return a.pos < b.pos; } struct Diagonale { 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 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)); } } } 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); } } }; 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); points = vector<Point>(nbPoints); for(int iPoint = 0;iPoint < nbPoints;iPoint++) { Point& p = points[iPoint]; cin >> p.x >> p.y >> p.dir; if(p.dir == 'W' || p.dir == 'E') ajoute(4, p.y, p.x, iPoint, (p.dir == 'W')?-1:1); if(p.dir == 'N' || p.dir == 'S') ajoute(5, p.x, p.y, iPoint, (p.dir == 'N')?-1:1); if(p.dir == 'N' || p.dir == 'W') ajoute(0, p.x + p.y, p.y - p.x, iPoint, (p.dir == 'N')?-1:1); if(p.dir == 'S' || p.dir == 'E') ajoute(2, p.x + p.y, p.y - p.x, iPoint, (p.dir == 'S')?1:-1); if(p.dir == 'E' || p.dir == 'N') ajoute(1, p.y - p.x, p.x + p.y, iPoint, (p.dir == 'N')?-1:1); if(p.dir == 'W' || p.dir == 'S') ajoute(3, p.y - p.x, p.x + p.y, iPoint, (p.dir == 'S')?1:-1); } for(int dir = 0;dir < 6;dir++) { for(auto diag : directions[dir]) { diag.second->init(); } } while(!collisions.empty()) { vector<int> aSupprimer; int temps = collisions.top().temps; while(!collisions.empty() && collisions.top().temps == temps) { Collision col = collisions.top(); collisions.pop(); if(estEnVie[col.id1] && estEnVie[col.id2]) { 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) { estEnVie[id] = false; for(Diagonale* diag : diagonales[id]) { diag->supprimer(id); } } while(!collisions.empty()) { Collision col = collisions.top(); if(estEnVie[col.id1] && estEnVie[col.id2]) break; else collisions.pop(); } } for(int iPoint = 0;iPoint < nbPoints;iPoint++) { if(estEnVie[iPoint]) { cout << iPoint + 1 << " "; } } cout << endl; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...