Submission #1134459

#	Time	Username	Problem	Language	Result	Execution time	Memory
1134459		iskhakkutbilim	Naval battle (CEOI24_battle)	C++20	46 / 100	3119 ms	791632 KiB

Main

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

#define ff first
#define ss second
#define all(a) a.begin(), a.end()
const int N = 1e6;
const int LOG = 20;
const int INF = 1e9 + 7;

struct navy{
    int x, y;
    char c;
};


pair<int, int> move(char c){
    if(c == 'S') return {-1, 0};
    if(c == 'W') return {0, 1};
    if(c == 'N') return {1, 0};
    return {0, -1};
}

/*
2
2 4 E 
6 0 S
*/

int intersect(navy a, navy b){
    if(a.c == 'N' && b.c == 'S' && b.y < a.y && a.x == b.x) return abs(b.y - a.y)/2;
    if(a.c == 'S' && b.c == 'N' && b.y > a.y && a.x == b.x) return abs(b.y - a.y)/2;
    if(a.c == 'W' && b.c == 'E' && a.y == b.y && a.x > b.x) return abs(b.x - a.x)/2;
    if(a.c == 'E' && b.c == 'W' && a.y == b.y && a.x < b.x) return abs(b.x - a.x)/2;
    
    if(a.c != 'E' and a.c != 'W') swap(a, b);
    if(abs(b.x - a.x) != abs(a.y - b.y) or abs(a.y - b.y)%2 != 0) return -1;
    if(a.c == 'E'){
        if(b.x > a.x){
            if(b.c == 'S' && b.y < a.y) return abs(b.x - a.x);
            if(b.c == 'N' && b.y > a.y) return abs(b.x - a.x);
        }
    }else if(a.c == 'W'){
        if(b.x < a.x){
            if(b.c == 'N' && b.y > a.y) return abs(b.x - a.x);
            if(b.c == 'S' && b.y < a.y) return abs(b.x - a.x);
        }
    }
    
    return -1;
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    
    int n; cin >> n;
    vector<navy> a(n);
    for(int i = 0;i < n; i++){
        cin >> a[i].x >> a[i].y >> a[i].c;
    }
    vector<int> used(n, 0);
    vector<array<int, 3> > pairs;
    for(int i = 0;i < n; i++){
        for(int j = 0;j < n; j++){
            if(i != j){
                int x = intersect(a[i], a[j]);
                if(x != -1){
                    pairs.push_back({i, j, x});
                }
            }
        }
    }
    sort(all(pairs), [&](auto A, auto B){
        return A[2] < B[2];
    });
    
    for(int i = 0;i < (int)pairs.size(); ){
        int j = i;
        vector<int> v;
        while(j < (int)pairs.size() && pairs[j][2] == pairs[i][2]){
            if(used[pairs[j][0]] or used[pairs[j][1]]){
                j++;
                continue;
            }
            v.push_back(pairs[j][0]);
            v.push_back(pairs[j][1]);
            j++;
        }
        for(auto x : v) used[x] = 1;
        i = j;
    }
    
    vector<int> answer;
    for(int i = 0;i < n; i++){
        if(!used[i]) answer.push_back(i+1);
    }
    for(auto x : answer) cout << x << '\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