Submission #1080438

#	Time	Username	Problem	Language	Result	Execution time	Memory
1080438		oscar1f	Naval battle (CEOI24_battle)	C++17	46 / 100	2188 ms	1048576 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; //oues

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

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

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