Submission #1273289

#	Time	Username	Problem	Language	Result	Execution time	Memory
1273289		anhkhoa	Tram (CEOI13_tram)	C++20	0 / 100	1096 ms	980 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, int c) : row(r), col(c) {}
    bool operator<(const Seat& other) const {
        if (row != other.row) return row < other.row;
        return col < other.col;
    }
};

struct Event {
    char type;
    int passenger_id;
};

struct FreeSegment {
    int start_row, end_row;
    int min_distance;
    Seat best_seat;
    
    FreeSegment(int s, int e, int dist, Seat seat) 
        : start_row(s), end_row(e), min_distance(dist), best_seat(seat) {}
    
    bool operator<(const FreeSegment& other) const {
        if (min_distance != other.min_distance) 
            return min_distance < other.min_distance;
        if (best_seat.row != other.best_seat.row) 
            return best_seat.row > other.best_seat.row;
        return best_seat.col > other.best_seat.col;
    }
};

int squared_distance(int r1, int c1, int r2, int c2) {
    int dr = r1 - r2;
    int dc = c1 - c2;
    return dr * dr + dc * dc;
}

int compute_min_distance(const Seat& seat, const set<Seat>& occupied) {
    if (occupied.empty()) return 1e9;
    
    int min_dist = 1e9;
    
    // Check nearby seats in both directions
    auto it = occupied.lower_bound(seat);
    
    // Check successor
    if (it != occupied.end()) {
        min_dist = min(min_dist, squared_distance(seat.row, seat.col, it->row, it->col));
    }
    
    // Check predecessor
    if (it != occupied.begin()) {
        --it;
        min_dist = min(min_dist, squared_distance(seat.row, seat.col, it->row, it->col));
    }
    
    // Also check same row but different column
    Seat other_col(seat.row, 3 - seat.col);
    it = occupied.find(other_col);
    if (it != occupied.end()) {
        min_dist = min(min_dist, 1); // distance = 1
    }
    
    return min_dist;
}

Seat find_best_seat(int start_row, int end_row, const set<Seat>& occupied) {
    Seat best_seat(0, 0);
    int max_min_dist = -1;
    
    for (int r = start_row; r <= end_row; r++) {
        for (int c = 1; c <= 2; c++) {
            Seat candidate(r, c);
            if (occupied.find(candidate) == occupied.end()) {
                int min_dist = compute_min_distance(candidate, occupied);
                if (min_dist > max_min_dist || 
                    (min_dist == max_min_dist && 
                     (r < best_seat.row || (r == best_seat.row && c < best_seat.col)))) {
                    max_min_dist = min_dist;
                    best_seat = candidate;
                }
            }
        }
    }
    
    return best_seat;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int N, M;
    cin >> N >> M;
    
    vector<Event> events(M);
    vector<Seat> passenger_seat(M + 1, Seat(0, 0)); // passenger_id -> seat
    set<Seat> occupied;
    set<int> occupied_rows;
    
    // Initialize boundaries
    occupied_rows.insert(0);
    occupied_rows.insert(N + 1);
    
    priority_queue<FreeSegment> segments;
    
    for (int i = 0; i < M; i++) {
        char type;
        cin >> type;
        
        if (type == 'E') {
            Seat chosen(0, 0);
            
            if (occupied.empty()) {
                // First passenger always gets (1, 1)
                chosen = Seat(1, 1);
            } else {
                // Find best seat by checking all free seats
                int max_min_dist = -1;
                
                // Check all rows and columns
                for (int r = 1; r <= N; r++) {
                    for (int c = 1; c <= 2; c++) {
                        Seat candidate(r, c);
                        if (occupied.find(candidate) == occupied.end()) {
                            int min_dist = compute_min_distance(candidate, occupied);
                            
                            if (min_dist > max_min_dist || 
                                (min_dist == max_min_dist && 
                                 (r < chosen.row || (r == chosen.row && c < chosen.col)))) {
                                max_min_dist = min_dist;
                                chosen = candidate;
                            }
                        }
                    }
                }
            }
            
            occupied.insert(chosen);
            occupied_rows.insert(chosen.row);
            passenger_seat[i + 1] = chosen;
            cout << chosen.row << " " << chosen.col << "\n";
            
        } else { // type == 'L'
            int passenger_id;
            cin >> passenger_id;
            Seat seat_to_free = passenger_seat[passenger_id];
            occupied.erase(seat_to_free);
            
            // Update occupied_rows if no other seats in this row are occupied
            bool row_still_occupied = false;
            for (int c = 1; c <= 2; c++) {
                if (occupied.find(Seat(seat_to_free.row, c)) != occupied.end()) {
                    row_still_occupied = true;
                    break;
                }
            }
            if (!row_still_occupied) {
                occupied_rows.erase(seat_to_free.row);
            }
        }
    }
    
    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