Submission #1273292

#	Time	Username	Problem	Language	Result	Execution time	Memory
1273292		anhkhoa	Tram (CEOI13_tram)	C++20	0 / 100	1095 ms	6840 KiB

tram

#include <iostream>
#include <vector>
#include <set>
#include <queue>
#include <cmath>
#include <algorithm>
using namespace std;

struct Seat {
    int row, col;
    Seat(int r = 0, int c = 0) : row(r), col(c) {}
    bool operator<(const Seat& other) const {
        if (row != other.row) return row < other.row;
        return col < other.col;
    }
};

struct Candidate {
    int min_dist; // minimum squared distance to occupied seats
    Seat seat;
    
    Candidate(int d, Seat s) : min_dist(d), seat(s) {}
    
    bool operator<(const Candidate& other) const {
        if (min_dist != other.min_dist) return min_dist < other.min_dist;
        if (seat.row != other.seat.row) return seat.row > other.seat.row;
        return seat.col > other.seat.col;
    }
};

int squared_dist(int r1, int c1, int r2, int c2) {
    return (r1 - r2) * (r1 - r2) + (c1 - c2) * (c1 - c2);
}

class TramSeating {
private:
    int N;
    set<Seat> occupied;
    priority_queue<Candidate> candidate_heap;
    
    void update_candidates_after_enter(const Seat& new_seat) {
        // Check all adjacent free seats to update their min distances
        for (int dr = -1; dr <= 1; dr++) {
            for (int dc = -1; dc <= 1; dc++) {
                if (dr == 0 && dc == 0) continue;
                
                int r = new_seat.row + dr;
                int c = new_seat.col + dc;
                
                if (r >= 1 && r <= N && c >= 1 && c <= 2) {
                    Seat neighbor(r, c);
                    if (occupied.find(neighbor) == occupied.end()) {
                        int new_dist = squared_dist(r, c, new_seat.row, new_seat.col);
                        update_seat_distance(neighbor, new_dist);
                    }
                }
            }
        }
    }
    
    void update_seat_distance(const Seat& seat, int new_dist) {
        // We'd need to update the heap, but since we can't efficiently update,
        // we'll use a lazy approach: push new candidate and ignore outdated ones
        candidate_heap.push(Candidate(new_dist, seat));
    }
    
    int calculate_min_distance(const Seat& seat) {
        if (occupied.empty()) return 1e9;
        
        int min_dist = 1e9;
        
        // Check all occupied seats (this is O(M) but M <= 30,000)
        for (const Seat& occ : occupied) {
            int dist = squared_dist(seat.row, seat.col, occ.row, occ.col);
            if (dist < min_dist) {
                min_dist = dist;
            }
            if (min_dist == 1) break; // Can't get smaller
        }
        
        return min_dist;
    }

public:
    TramSeating(int n) : N(n) {}
    
    Seat add_passenger() {
        if (occupied.empty()) {
            Seat new_seat(1, 1);
            occupied.insert(new_seat);
            // Initialize heap with all seats
            initialize_heap();
            return new_seat;
        }
        
        // Find best seat using heap (lazy deletion)
        while (true) {
            Candidate best = candidate_heap.top();
            candidate_heap.pop();
            
            // Check if seat is still free and distance is still valid
            if (occupied.find(best.seat) != occupied.end()) continue;
            
            int actual_dist = calculate_min_distance(best.seat);
            if (actual_dist == best.min_dist) {
                // This candidate is valid
                occupied.insert(best.seat);
                update_candidates_after_enter(best.seat);
                return best.seat;
            } else {
                // Push updated candidate
                candidate_heap.push(Candidate(actual_dist, best.seat));
            }
        }
    }
    
    void remove_passenger(const Seat& seat) {
        occupied.erase(seat);
        // When removing, we need to update distances of nearby seats
        // For simplicity, we'll just push them back to heap with recalculated distances
        update_candidates_after_leave(seat);
    }
    
    void update_candidates_after_leave(const Seat& removed_seat) {
        // Update all seats in nearby rows
        for (int r = max(1, removed_seat.row - 2); r <= min(N, removed_seat.row + 2); r++) {
            for (int c = 1; c <= 2; c++) {
                Seat seat(r, c);
                if (occupied.find(seat) == occupied.end()) {
                    int dist = calculate_min_distance(seat);
                    candidate_heap.push(Candidate(dist, seat));
                }
            }
        }
    }
    
    void initialize_heap() {
        for (int r = 1; r <= N; r++) {
            for (int c = 1; c <= 2; c++) {
                Seat seat(r, c);
                if (occupied.find(seat) == occupied.end()) {
                    int dist = calculate_min_distance(seat);
                    candidate_heap.push(Candidate(dist, seat));
                }
            }
        }
    }
};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int N, M;
    cin >> N >> M;
    
    TramSeating tram(N);
    vector<Seat> passenger_seat(M + 1);
    vector<bool> active(M + 1, false);
    int passenger_id = 0;
    
    for (int event_id = 1; event_id <= M; event_id++) {
        char type;
        cin >> type;
        
        if (type == 'E') {
            passenger_id++;
            Seat seat = tram.add_passenger();
            passenger_seat[passenger_id] = seat;
            active[passenger_id] = true;
            cout << seat.row << " " << seat.col << "\n";
        } else { // 'L'
            int p;
            cin >> p;
            if (active[p]) {
                tram.remove_passenger(passenger_seat[p]);
                active[p] = false;
            }
        }
    }
    
    return 0;
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 15
• Subtask 3: 0 / 10
• Subtask 4: 0 / 10
• Subtask 5: 0 / 10
• Subtask 6: 0 / 10
• Subtask 7: 0 / 15
• Subtask 8: 0 / 20