Submission #1363708

#	Time	Username	Problem	Language	Result	Execution time	Memory
1363708		Aviansh	Naval battle (CEOI24_battle)	C++20	46 / 100	3108 ms	790732 KiB

Main

#include <bits/stdc++.h>

using namespace std;

struct ship{
    int x;
    int y;
    char c;
};

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin >> n;
    ship arr[n];
    for(int i = 0;i<n;i++){
        cin >> arr[i].x;
        cin >> arr[i].y;
        cin >> arr[i].c;
    }
    vector<array<int,3>> colls;
    //{time,a,b}
    auto reachtim = [&] (array<int,2> pt, ship s){
        if(s.y==pt[1]){
            if(s.c=='W'){
                if(s.x>=pt[0]){
                    return s.x-pt[0];
                }
            }
            else if(s.c=='E'){
                if(s.x<=pt[0]){
                    return pt[0]-s.x;
                }
            }
        }
        if(s.x==pt[0]){
            if(s.c=='N'){
                if(s.y>=pt[1]){
                    return s.y-pt[1];
                }
            }
            else if(s.c=='S'){
                if(s.y<=pt[1]){
                    return pt[1]-s.y;
                }
            }
        }
        return -1;
    };
    for(int i = 0;i<n;i++){
        for(int j = i+1;j<n;j++){
            //check when i and j collide if ever
            if(arr[i].c==arr[j].c){
                //never collide as same direction
                continue;
            }
            int tim = -1;
            ship a = arr[i];
            ship b = arr[j];
            if(a.c=='N'){
                if(b.c=='S'){
                    if(a.x==b.x){
                        if(a.y>b.y){
                            //may collide if parity
                            if(a.y%2==b.y%2){
                                //collide
                                tim=(a.y-b.y)/2;
                                colls.push_back({tim,i,j});
                                continue;
                            }
                        }
                    }
                }
            }
            if(a.c=='E'){
                if(b.c=='W'){
                    if(a.y==b.y){
                        if(a.x<b.x){
                            if(a.x%2==b.x%2){
                                tim=(b.x-a.x)/2;
                                colls.push_back({tim,i,j});
                                continue;
                            }
                        }
                    }
                }
            }
            swap(a,b);
            if(a.c=='N'){
                if(b.c=='S'){
                    if(a.x==b.x){
                        if(a.y>b.y){
                            //may collide if parity
                            if(a.y%2==b.y%2){
                                //collide
                                tim=(a.y-b.y)/2;
                                colls.push_back({tim,i,j});
                                continue;
                            }
                        }
                    }
                }
            }
            if(a.c=='E'){
                if(b.c=='W'){
                    if(a.y==b.y){
                        if(a.x<b.x){
                            if(a.x%2==b.x%2){
                                tim=(b.x-a.x)/2;
                                colls.push_back({tim,i,j});
                                continue;
                            }
                        }
                    }
                }
            }

            //hor/ver handled
            array<int,2> col1 = {max(a.x,b.x),max(a.y,b.y)};
            array<int,2> col2 = {max(a.x,b.x),min(a.y,b.y)};
            array<int,2> col3 = {min(a.x,b.x),max(a.y,b.y)};
            array<int,2> col4 = {min(a.x,b.x),min(a.y,b.y)};
            if(reachtim(col1,a)==reachtim(col1,b)&&reachtim(col1,b)>0){
                tim=reachtim(col1,b);
                colls.push_back({tim,i,j});
                continue;
            }
            if(reachtim(col2,a)==reachtim(col2,b)&&reachtim(col2,b)>0){
                tim=reachtim(col2,b);
                colls.push_back({tim,i,j});
                continue;
            }
            if(reachtim(col3,a)==reachtim(col3,b)&&reachtim(col3,b)>0){
                tim=reachtim(col3,b);
                colls.push_back({tim,i,j});
                continue;
            }
            if(reachtim(col4,a)==reachtim(col4,b)&&reachtim(col4,b)>0){
                tim=reachtim(col4,b);
                colls.push_back({tim,i,j});
                continue;
            }
        }
    }
    int des[n];
    fill(des,des+n,2e9);
    sort(colls.begin(),colls.end());
    int tim = -1;
    for(array<int,3>a:colls){
        if(min(des[a[1]],des[a[2]])<a[0]){
            //do nothing
            continue;
        }
        else{
            des[a[1]]=a[0];
            des[a[2]]=a[0];
        }
    }
    for(int i = 0;i<n;i++){
        if(des[i]==2e9){
            cout << i+1 << "\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