Submission #1063143

#	Time	Username	Problem	Language	Result	Execution time	Memory
1063143		Dan4Life	Naval battle (CEOI24_battle)	C++17	46 / 100	3071 ms	402484 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define sz(a) (int)a.size()
#define all(a) begin(a), end(a)
using ll = long long;
using vi = vector<int>;
using ar2 = array<int,2>;
using ar3 = array<int,3>;
const int INF = (int)2e9;
const int mxN = (int)2e5+10;

struct Ship{
    int r, c, i;
    char d;
};

int n;
Ship a[mxN];
int collided[mxN];
priority_queue<ar3,vector<ar3>,greater<ar3>> pq;

bool sameAxis(char a, char b){
    if(a=='N' and b=='S') return 1;
    if(a=='S' and b=='N') return 1;
    if(a=='E' and b=='W') return 1;
    if(a=='W' and b=='E') return 1;
    return 0;
}

int main(){
    cin >> n;
    fill(collided,collided+n,INF);
    for(int i = 0; i < n; i++){
        cin >> a[i].c >> a[i].r >> a[i].d;
        a[i].i = i;
    }
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            if(i==j) continue;
            if(a[i].d==a[j].d) continue;
            int tim = INF;
            if(sameAxis(a[i].d,a[j].d)){
                if(a[i].d=='S'){
                    if(a[i].c==a[j].c and a[i].r<a[j].r)
                        tim = (a[j].r-a[i].r)/2;
                }
                else if(a[i].d=='E'){
                    if(a[i].r==a[j].r and a[i].c<a[j].c)
                        tim = (a[j].c-a[i].c)/2;
                }
            }
            else{
                if(a[i].d=='N' or a[i].d=='S'){
                    bool leftDiag = 0;
                    if(a[i].d=='S' and a[j].d=='E') leftDiag = 1;
                    if(a[i].d=='N' and a[j].d=='W') leftDiag = 1;
                    if(leftDiag){
                        if(a[i].r+a[i].c==a[j].r+a[j].c){
                            if(a[i].d=='S' and a[i].c>a[j].c)
                                tim = a[i].c-a[j].c;
                            else if(a[i].d=='N' and a[i].c<a[j].c)
                                tim = a[j].c-a[i].c;
                        }
                    }
                    else{
                        if(a[i].r-a[i].c==a[j].r-a[j].c){
                            if(a[i].d=='S' and a[i].c<a[j].c)
                                tim = a[j].c-a[i].c;
                            else if(a[i].d=='N' and a[i].c>a[j].c)
                                tim = a[i].c-a[j].c;
                        }
                    }
                }
            }
            if(tim!=INF) pq.push({tim,i,j});
        }
    }
    while(sz(pq)){
        auto [T,i,j] = pq.top(); pq.pop();
        if(collided[i]<T or collided[j]<T) continue;
        collided[i]=collided[j]=T;
    }
    for(int i = 0; i < n; i++)
        if(collided[i]==INF) cout << i+1 << "\n";
}

• 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