#include <bits/stdc++.h> using namespace std; using pii=pair<int, int>; priority_queue<array<int, 6>, vector<array<int, 6>>, greater<array<int, 6>>> pq; vector<int> X, Y; struct nodo{ int ind, l, r; bool aperta; nodo(int i, int left, bool a){ ind=i, l=left, aperta=a, r=-1; } }; void pop(vector<nodo> &v, int ind, int diagType, int diagInd){ if(v[ind].l==-1 && v[ind].r==-1){ return; }else if(v[ind].l==-1){ int nextNodeInd=v[ind].r; v[nextNodeInd].l=-1; return; }else if(v[ind].r==-1){ int prevNodeInd=v[ind].l; v[prevNodeInd].r=-1; return; }else{ int prevNodeInd=v[ind].l, nextNodeInd=v[ind].r; v[prevNodeInd].r=nextNodeInd; v[nextNodeInd].l=prevNodeInd; if(v[prevNodeInd].aperta && !v[nextNodeInd].aperta){ array<int, 6> scontro; int i1=v[prevNodeInd].ind, i2=v[nextNodeInd].ind; int time; if(diagType<4) time=abs(X[i2]-X[i1]); //abs non servirebbe ma better safe than sorry else if(diagType==4) time=abs(X[i2]-X[i1])/2; else if(diagType==5) time=abs(Y[i2]-Y[i1])/2; scontro={time, i1, i2, diagType, diagInd, prevNodeInd}; pq.push(scontro); } } } void pop2(vector<nodo> &v, int ind1, int ind2, int diagType, int diagInd){ if(v[ind1].l==-1 && v[ind2].r==-1){ return; }else if(v[ind1].l==-1){ int nextNodeInd=v[ind2].r; v[nextNodeInd].l=-1; return; }else if(v[ind2].r==-1){ int prevNodeInd=v[ind1].l; v[prevNodeInd].r=-1; return; }else{ int prevNodeInd=v[ind1].l, nextNodeInd=v[ind2].r; v[prevNodeInd].r=nextNodeInd; v[nextNodeInd].l=prevNodeInd; if(v[prevNodeInd].aperta && !v[nextNodeInd].aperta){ array<int, 6> scontro; int i1=v[prevNodeInd].ind, i2=v[nextNodeInd].ind; int time; if(diagType<4) time=abs(X[i2]-X[i1]); //abs non servirebbe ma better safe than sorry else if(diagType==4) time=abs(X[i2]-X[i1])/2; else if(diagType==5) time=abs(Y[i2]-Y[i1])/2; scontro={time, i1, i2, diagType, diagInd, prevNodeInd}; pq.push(scontro); } } } int findDiagInd(int diagType, int x, int y){ if(diagType==0 || diagType==3) return x+y; if(diagType==1 || diagType==2) return x-y; if(diagType==4) return y; if(diagType==5) return x; } vector<int> affonda(int N, vector<char> D){ vector<array<int, 4>> navi(N); vector<bool> isAlive(N, true); map<pair<int, int>, int> sea; for(int i=0; i<N; i++){ if(sea.find({X[i], Y[i]})==sea.end()) sea[{X[i], Y[i]}]=i; else{ isAlive[sea[{X[i], Y[i]}]]=false; isAlive[i]=false; } } for(int i=0; i<N; i++) navi[i]={X[i], Y[i], D[i], i}; sort(navi.begin(), navi.end()); vector<map<int, vector<nodo>>> diagonali(6); /* 0 -> SE 1 -> SW 2 -> NE 3 -> NW 4 -> horizontal 5 -> vertical*/ for(int i=0; i<N; i++){ int xAtt=navi[i][0], yAtt=navi[i][1], dAtt=navi[i][2], indAtt=navi[i][3]; if(dAtt=='S'){ vector<int> possibleDiagonals={0, 1, 5}; //SE, SW, vertical for(int diagAtt : possibleDiagonals){ bool aperta=true; if(diagAtt==0) aperta=false; int diagInd=findDiagInd(diagAtt, xAtt, yAtt); if(!diagonali[diagAtt][diagInd].empty()) diagonali[diagAtt][diagInd][diagonali[diagAtt][diagInd].size()-1].r=diagonali[diagAtt][diagInd].size(); diagonali[diagAtt][diagInd].push_back(nodo(indAtt, diagonali[diagAtt][diagInd].size()-1, aperta)); } }if(dAtt=='E'){ vector<int> possibleDiagonals={0, 2, 4}; //SE, NE, horizontal for(int diagAtt : possibleDiagonals){ bool aperta=true; int diagInd=findDiagInd(diagAtt, xAtt, yAtt); if(!diagonali[diagAtt][diagInd].empty()) diagonali[diagAtt][diagInd][diagonali[diagAtt][diagInd].size()-1].r=diagonali[diagAtt][diagInd].size(); diagonali[diagAtt][diagInd].push_back(nodo(indAtt, diagonali[diagAtt][diagInd].size()-1, aperta)); } }if(dAtt=='N'){ vector<int> possibleDiagonals={2, 3, 5}; //NE, NW, vertical for(int diagAtt : possibleDiagonals){ bool aperta=false; if(diagAtt==3) aperta=true; int diagInd=findDiagInd(diagAtt, xAtt, yAtt); if(!diagonali[diagAtt][diagInd].empty()) diagonali[diagAtt][diagInd][diagonali[diagAtt][diagInd].size()-1].r=diagonali[diagAtt][diagInd].size(); diagonali[diagAtt][diagInd].push_back(nodo(indAtt, diagonali[diagAtt][diagInd].size()-1, aperta)); } }if(dAtt=='W'){ vector<int> possibleDiagonals={1, 3, 4}; //SW, NW, horizontal for(int diagAtt : possibleDiagonals){ bool aperta=false; int diagInd=findDiagInd(diagAtt, xAtt, yAtt); if(!diagonali[diagAtt][diagInd].empty()) diagonali[diagAtt][diagInd][diagonali[diagAtt][diagInd].size()-1].r=diagonali[diagAtt][diagInd].size(); diagonali[diagAtt][diagInd].push_back(nodo(indAtt, diagonali[diagAtt][diagInd].size()-1, aperta)); } } } for(int diagAtt=0; diagAtt<6; diagAtt++){ for(auto const& p : diagonali[diagAtt]){ vector<nodo> currDiag=p.second; for(int i=1; i<currDiag.size(); i++){ if(currDiag[i-1].aperta && !currDiag[i].aperta){ array<int, 6> scontro; int i1=currDiag[i-1].ind, i2=currDiag[i].ind; int time; if(diagAtt<4) time=abs(X[i2]-X[i1]); //abs non servirebbe ma better safe than sorry else if(diagAtt==4) time=abs(X[i2]-X[i1])/2; else if(diagAtt==5) time=abs(Y[i2]-Y[i1])/2; scontro={time, i1, i2, diagAtt, p.first, i-1}; pq.push(scontro); } } } } set<int> toKill; int lastTime=1; while(!pq.empty()){ array<int, 6> scontro=pq.top(); int currTime=scontro[0], nave1=scontro[1], nave2=scontro[2], diagType=scontro[3], diagInd=scontro[4], indDaRimuovere=scontro[5]; pq.pop(); if(currTime!=lastTime){ for(int shipToKill : toKill) isAlive[shipToKill]=false; toKill.erase(toKill.begin(), toKill.end()); lastTime=currTime; } if(isAlive[nave1]!=isAlive[nave2]){ if(isAlive[nave1]) indDaRimuovere=diagonali[diagType][diagInd][indDaRimuovere].r; //se la prima nave è ancora in vita, allora devo rimuovere la seconda pop(diagonali[diagType][diagInd], indDaRimuovere, diagType, diagInd); }else{ if(isAlive[nave1]){ toKill.insert(nave1); toKill.insert(nave2); } pop2(diagonali[diagType][diagInd], indDaRimuovere, indDaRimuovere+1, diagType, diagInd); } } for(int shipToKill : toKill) isAlive[shipToKill]=false; vector<int> ans; for(int i=0; i<N; i++) if(isAlive[i]) ans.push_back(i+1); return ans; } int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); int N; cin >>N; X.resize(N); Y.resize(N); vector<char> D(N); for(int i=0; i<N; i++) cin >>X[i] >>Y[i] >>D[i]; vector<int> ans=affonda(N, D); for(int i=0; i<ans.size(); i++) cout <<ans[i] <<'\n'; }

Main.cpp: In function 'int findDiagInd(int, int, int)':
Main.cpp:80:1: warning: control reaches end of non-void function [-Wreturn-type]
   80 | }
      | ^