Submission #1134507

#	Time	Username	Problem	Language	Result	Execution time	Memory
1134507		iskhakkutbilim	Naval battle (CEOI24_battle)	C++20	76 / 100	576 ms	49824 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);
    if(n <= 5000){
    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';
    }else{
        map<int, vector<int> > diag;
        vector<array<int, 3> > E, S;
        for(int i = 0;i < n; i++){
            if(a[i].c == 'E') E.push_back({a[i].x, a[i].y, i});
            else if(a[i].c == 'S')S.push_back({a[i].x, a[i].y, i});
        }
        sort(all(E), [&](auto A, auto B){
            return A[1] < B[1];
        });
        sort(all(S), [&](auto A, auto B){
            return A[1] < B[1];
        });
        int i = 0, j = 0;
        vector<int> used(n, 0);
        for(; i < (int)E.size(); i++){
          //  cout << "new : " << " "<< E[i][0] << ' ' << E[i][1] << '\n';
         //   cout << '\n';
            while(j < (int)S.size() && E[i][1] > S[j][1]){
                diag[S[j][1]+S[j][0]].push_back(S[j][2]);
          //      cout << "here : " << S[j][0] << ' ' << S[j][1] << ", ";
                j++;
            }
         //   cout << '\n';
         int d = E[i][0] + E[i][1];
            int idx = -1;
            if(diag[d].empty() ==false) idx = diag[d].back();
           // cout << "founds : " << idx << '\n';
            if(idx != -1){
                if(intersect(a[E[i][2]], a[idx]) == -1) assert(false);
                used[E[i][2]] = 1;
                used[idx] = 1;
                diag[d].pop_back();
            }
        }
        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: 30 / 30
• Subtask 7: 0 / 24