Submission #1227182

#	Time	Username	Problem	Language	Result	Execution time	Memory
1227182		just	Naval battle (CEOI24_battle)	C++20	0 / 100	305 ms	41112 KiB

Main

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

#define int long long
#define vec vector
#define all(x) (x).begin(), (x).end()

#define X first
#define Y second

using pii = pair<int, int>;

pii operator+(const pii &a, const pii &b) {
    return {a.X + b.X, a.Y + b.Y};
}

pii operator-(const pii &a, const pii &b) {
    return {a.X - b.X, a.Y - b.Y};
}

pii operator*(const pii &a, const int &b) {
    return {a.X * b, a.Y * b};
}

pii operator-(const pii &a) {
    return {-a.X, -a.Y};
}

int xdist(const pii &a, const pii &b) {
    return abs(a.X - b.X);
}

int ydist(const pii &a, const pii &b) {
    return abs(a.Y - b.Y);
}

int x_intercept(const pii &a) {
    return a.X + a.Y;
}

int y_intercept(const pii &a) {
    return a.X - a.Y;
}

ostream &operator<<(ostream &os, const pii &p) {
    os << "(" << p.X << ", " << p.Y << ")";
    return os;
}

int collide(pair<pii, pii> a, pair<pii, pii> b) {
    auto posa = a.X;
    auto posb = b.X;
    
    auto dira = a.Y;
    auto dirb = b.Y;
    
    int disty = ydist(posa, posb);
    int distx = xdist(posa, posb);
    
    if (dira == dirb) return INT_MAX;
    if (dira == -dirb) {
        if (distx == 0 || disty == 0) {
            int dist = max(distx, disty);
            int time = dist / 2;
            if (posa + dira * time == posb + dirb * time) {
                return time;
            }
        }
        
        return INT_MAX;
    }
    
    
    if (distx == disty) {
        int dist = distx;
        int time = dist;
        if (posa + dira * time == posb + dirb * time) {
            return time;
        }
    }
    
    return INT_MAX;
}

signed main() {
    int n; cin >> n;
    vec<pair<pii, pii>> a(n);
    for (int i = 0; i < n; i++) {
        int x, y;
        char c;
        cin >> x >> y >> c;
        pii dir;
        if (c == 'N') dir = { 0, -1};
        if (c == 'S') dir = { 0,  1};
        if (c == 'E') dir = { 1,  0};
        if (c == 'W') dir = {-1,  0};
        
        a[i] = {{x, y}, dir};
    }
    
    // map<int, vec<int>> y_diag, x_diag, x_line, y_line;
    
    // for (int i = 0; i < n; i++) {
    //     int x_int = abs(x_intercept(a[i].X));
    //     int y_int = abs(y_intercept(a[i].X));
        
    //     int x = a[i].X.X;
    //     int y = a[i].X.Y;
        
    //     x_diag[x_int].push_back(i);
    //     y_diag[y_int].push_back(i);
    //     x_line[x].push_back(i);
    //     y_line[y].push_back(i);
        
    //     // cerr << i + 1 << " " << x << " " << y << " " << x_int << " " << y_int << endl;
    // }
    
    // vec<pair<int, pair<int, int>>> pairs;
    // for (auto &group: {x_line, y_line, x_diag, y_diag}) {
    //     for (auto &[_, v]: group) {
    //         for (int i = 0; i < v.size(); i++) {
    //             for (int j = i + 1; j < v.size(); j++) {
    //                 int time = collide(a[v[i]], a[v[j]]);
    //                 if (time != INT_MAX) {
    //                     pairs.push_back({
    //                         time,
    //                         {v[i], v[j]}
    //                     });
    //                 }
    //             }
    //         }
    //     }
    // }
    
    
    map<int, int> group_cnt;
    for (int i = 0; i < n; i++) {
        int x = a[i].X.X;
        int y = a[i].X.Y;
        
        int g = x + y;
        group_cnt[g]++;
    }
    
    map<int, vec<int>> groups;
    for (auto [g, cnt]: group_cnt) {
        groups[g].reserve(cnt);
    }
    
    for (int i = 0; i < n; i++) {
        int x = a[i].X.X;
        int y = a[i].X.Y;
        
        int g = x + y;
        groups[g].push_back(i);
    }
    
    const pii E = {1, 0};
    const pii S = {0, 1};
    
    vec<bool> hit(n, false);
    for (auto &[g, v]: groups) {
        int m = v.size();
        
        vec<tuple<pii, pii, int>> data;
        for (int i = 0; i < m; i++) {
            int idx = v[i];
            auto pos = a[idx].X;
            auto dir = a[idx].Y;
            
            data.push_back({pos, dir, idx});
            // cerr << g << ": " << idx + 1 << " " << pos << " " << dir << endl;
        }
        
        sort(all(data));
        
        stack<int> easts;
        for (auto [pos, dir, idx]: data) {
            if (dir == E) {
                easts.push(idx);
            } else {
                if (easts.empty()) {
                    continue;
                } else {
                    int last = easts.top();
                    easts.pop();
                    
                    hit[last] = true;
                    hit[idx] = true;
                }
            }
        }
    }
    
    for (int i = 0; i < n; i++) {
        if (!hit[i]) {
            cout << i + 1 << endl;
            return 0;
        }
    }
    
    
    
}

• Subtask 0: 0 / 0
• Subtask 1: 0 / 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