Submission #1222457

#	Time	Username	Problem	Language	Result	Execution time	Memory
1222457		ElenaBM	Naval battle (CEOI24_battle)	C++20	6 / 100	3026 ms	790704 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define x first
#define y second

int main(){
    int N;
    cin>> N; 
    vector<pair<pair<int,int>, char>> sh(N);
    for (int i = 0; i< N; ++i){
        cin>> sh[i].x.x >> sh[i].x.y >> sh[i].y;
    }
    vector<pair<int,int>>dir(20);
    dir[0] = make_pair(1, 0);
    dir['N' -'E'] = make_pair(0, -1);
    dir['S'- 'E'] = make_pair(0, 1);
    dir['W' - 'E'] = make_pair(-1, 0);
    priority_queue<pair<int, pair<int,int>>> choque; 
    for (int i = 0; i< N; ++i){
        for (int j = i+1; j < N; ++j){
            if (sh[i].y == sh[j].y) continue;
            if (dir[sh[i].y - 'E'].x == 0 and dir[sh[j].y - 'E'].x == 0){
                if (sh[i].x.x == sh[j].x.x){
                    int mov = abs(sh[i].x.y - sh[j].x.y)/2;
                    choque.push({-mov, {i, j}});
                }
            }
            else if (dir[sh[i].y - 'E'].y == 0 and dir[sh[j].y - 'E'].y == 0){
                if (sh[i].x.y == sh[j].x.y){
                    int mov = abs(sh[i].x.x - sh[j].x.x)/2;
                    choque.push({-mov, {i, j}});
                }
            }
            else{
                int n1 = (sh[j].x.x - sh[i].x.x)/(dir[sh[i].y-'E'].x - dir[sh[j].y -'E'].x);
                int n2 = (sh[j].x.y - sh[i].x.y)/(dir[sh[i].y-'E'].y - dir[sh[j].y -'E'].y);
                if (n1 == n2 and n1 > 0) choque.push({-n1, {i,j}});
            }

        }
    }
    vector<int>used(N, 0);
    while (!choque.empty()){
        pair<int, pair<int,int>> act= choque.top();
        choque.pop();
        if (used[act.y.x] or used[act.y.y]){ 
            if (used[act.y.x] == -act.x) used[act.y.y] = -act.x;
            if (used[act.y.y] == -act.x) used[act.y.x] = -act.x;
        }
        else{
            used[act.y.x] = -act.x;
            used[act.y.y] = -act.x;
        }
    }
    for (int i = 0; i< N; ++i){
        if (!used[i]) cout<< i+1 << '\n';
    }
    return 0;
}

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