| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1080702 | oscar1f | Naval battle (CEOI24_battle) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
using namespace std;
#define int long long
struct intersect {
int distParc,premBat,deuzBat;
bool operator < (const intersect& autre) const {
return distParc>autre.distParc;
}
};
const int MAX_BAT=200*1000+5,INFINI=1000*1000*1000+5;
int nbBat;
pair<int,int> coord[MAX_BAT];
int direc[MAX_BAT],dateInter[MAX_BAT];
set<int> listeVal[4];
unordered_map<int,int> reNum[4];
vector<pair<int,int>> corres;
set<pair<int,int>> posBat[MAX_BAT][6];
priority_queue<intersect> possi;
vector<vector<bool>> pris={{false,true,true,false},
{true,false,false,true},
{false,true,false,true},
{false,false,true,true},
{true,true,false,false},
{true,false,true,false}};
vector<int> numHache={0,0,1,2,2,3};
vector<pair<int,int>> pente={{1,1},
{1,1},
{0,1},
{1,-1},
{1,-1},
{1,0}};
vector<pair<int,int>> combin={{1,0},
{1,0},
{1,0},
{1,0},
{1,0},
{0,1}};
int calcInter(int bat1,int bat2) {
int dist=0;
if (coord[bat1].first==coord[bat2].first) {
dist=abs(coord[bat1].second-coord[bat2].second)/2;
}
else if (coord[bat1].second==coord[bat2].second) {
dist=abs(coord[bat1].first-coord[bat2].first)/2;
}
else if (abs(coord[bat1].first-coord[bat2].first)==abs(coord[bat1].second-coord[bat2].second)) {
dist=abs(coord[bat1].first-coord[bat2].first);
}
else {
return INFINI;
}
if (coord[bat1].first+dist*corres[direc[bat1]].first==coord[bat2].first+dist*corres[direc[bat2]].first and
coord[bat1].second+dist*corres[direc[bat1]].second==coord[bat2].second+dist*corres[direc[bat2]].second) {
return dist;
}
return INFINI;
}
void init(int idSom,int idSens) {
int taille=posBat[idSom][idSens].size();
if (taille==0) {
return;
}
auto it=posBat[idSom][idSens].begin();
int bat1,bat2,dist;
for (int i=0;i<taille-1;i++) {
bat1=(*it).second;
it++;
bat2=(*it).second;
dist=calcInter(bat1,bat2);
if (dist!=INFINI) {
possi.push({dist,bat1,bat2});
}
}
}
void suppr(int idSom,int idSens,int batSup,int som) {
auto it=posBat[idSom][idSens].lower_bound({som,batSup});
if (it==posBat[idSom][idSens].end() or (*it)!={som,batSup}) {
return;
}
posBat[idSom][idSens].erase(it);
it=posBat[idSom][idSens].lower_bound({coord[batSup].first,batSup});
if (it==posBat[idSom][idSens].end() or it==posBat[idSom][idSens].begin()) {
return;
}
int bat1,bat2=(*it).second,dist;
it--;
bat1=(*it).second;
dist=calcInter()
dist=calcInter(bat1,bat2);
if (dist!=INFINI) {
possi.push({dist,bat1,bat2});
}
}
void calc(vector<int> numBat) {
int taille=numBat.size();
set<pair<int,int>> posBat;
for (int i:numBat) {
posBat.insert({coord[i].first,i});
}
priority_queue<pair<int,int>> possi;
auto it=posBat.begin();
int bat1,bat2,batSup;
for (int i=0;i<taille-1;i++) {
bat1=(*it).second;
it++;
bat2=(*it).second;
if (direc[bat1]==1 and direc[bat2]==2) {
possi.push({-(coord[bat2].first-coord[bat1].first),bat1});
}
}
while (!possi.empty()) {
batSup=possi.top().second;
possi.pop();
it=posBat.lower_bound({coord[batSup].first,batSup});
posBat.erase(it);
it=posBat.lower_bound({coord[batSup].first,batSup});
posBat.erase(it);
it=posBat.lower_bound({coord[batSup].first,batSup});
if (it!=posBat.end()) {
bat2=(*it).second;
if (it!=posBat.begin()) {
it--;
bat1=(*it).second;
if (direc[bat1]==1 and direc[bat2]==2) {
possi.push({-(coord[bat2].first-coord[bat1].first),bat1});
}
}
}
}
for (auto i:posBat) {
cout<<i.second<<"\n";
}
}
void maj(int batSup,int dist) {
dateInter[batSup]=dist;
for (int i=1;i<=nbBat;i++) {
for (int j=0;j<6;j++) {
if (pris[j][direc[i]]) {
suppr(reNum[numHache[j]][coord[i].first*pente[j].first+coord[i].second*pente[j].second],j,i,coord[i].first*combin[j].first+coord[i].second*combin[j].second);
}
}
}
}
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
corres={{0,-1},{1,0},{0,1},{-1,0}};
cin>>nbBat;
char carac;
for (int i=1;i<=nbBat;i++) {
cin>>coord[i].first>>coord[i].second>>carac;
if (carac=='N') {
direc[i]=0;
}
if (carac=='E') {
direc[i]=1;
}
if (carac=='S') {
direc[i]=2;
}
if (carac=='W') {
direc[i]=3;
}
listeVal[0].insert(coord[i].first+coord[i].second);
listeVal[1].insert(coord[i].second);
listeVal[2].insert(coord[i].first-coord[i].second);
listeVal[3].insert(coord[i].first);
dateInter[i]=INFINI;
}
int numDeCeType;
for (int i=0;i<4;i++) {
numDeCeType=0;
for (int j:listeVal[i]) {
reNum[i][j]=numDeCeType;
numDeCeType++;
}
}
for (int i=1;i<=nbBat;i++) {
for (int j=0;j<6;j++) {
if (pris[j][direc[i]]) {
posBat[reNum[numHache[j]][coord[i].first*pente[j].first+coord[i].second*pente[j].second]][j].insert({coord[i].first*combin[j].first+coord[i].second*combin[j].second,i});
}
}
}
for (int i=0;i<nbBat;i++) {
for (int j=0;j<6;j++) {
init(i,j);
}
}
int bat1,bat2,dist;
while (!possi.empty()) {
dist=possi.top().distParc;
bat1=possi.top().premBat;
bat2=possi.top().deuzBat;
possi.pop();
if (dateInter[bat1]>=dist and dateInter[bat2]>=dist) {
maj(bat1,dist);
maj(bat2,dist);
}
}
for (int i=1;i<=nbBat;i++) {
if (dateInter[i]==INFINI) {
cout<<i<<"\n";
}
}
return 0;
}