Submission #1080507

#	Time	Username	Problem	Language	Result	Execution time	Memory
1080507		oscar1f	Naval battle (CEOI24_battle)	C++17	76 / 100	309 ms	50056 KiB

Main

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

#define int long long

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];
vector<tuple<int,int,int>> intersect;
vector<pair<int,int>> corres; 

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 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";
    }
}

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;
    if (nbBat<=5000+5) {
        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;
            }
            dateInter[i]=INFINI;
        }
        int dist,bat1,bat2;
        for (int i=1;i<=nbBat;i++) {
            for (int j=i+1;j<=nbBat;j++) {
                dist=calcInter(i,j);
                if (dist!=INFINI) {
                    intersect.push_back(make_tuple(dist,i,j));
                }
            }
        }
        sort(intersect.begin(),intersect.end());
        for (auto i:intersect) {
            dist=get<0>(i);
            bat1=get<1>(i);
            bat2=get<2>(i);
            if (dateInter[bat1]>=dist and dateInter[bat2]>=dist) {
                dateInter[bat1]=dist;
                dateInter[bat2]=dist;
            }
        }
        for (int i=1;i<=nbBat;i++) {
            if (dateInter[i]==INFINI) {
                cout<<i<<"\n";
            }
        }
        return 0;
    }
    char carac;
    vector<pair<int,int>> diagTri;
    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;
        }
        diagTri.push_back({coord[i].first+coord[i].second,i});
    }
    sort(diagTri.begin(),diagTri.end());
    vector<int> enCours;
    int dern=-1;
    for (auto i:diagTri) {
        if (dern==i.first) {
            enCours.push_back(i.second);
        }
        else {
            calc(enCours);
            enCours.clear();
            enCours.push_back(i.second);
            dern=i.first;
        }
    }
    calc(enCours);
    return 0;
}
 

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