Submission #1273291

#	Time	Username	Problem	Language	Result	Execution time	Memory
1273291		anhkhoa	Tram (CEOI13_tram)	C++20	0 / 100	1096 ms	940 KiB

tram

#include <iostream>
#include <vector>
#include <set>
#include <map>
#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;
    }
};

// For maintaining gaps between occupied rows
struct Gap {
    int start, end; // row numbers
    int size() const { return end - start - 1; }
    bool operator<(const Gap& other) const {
        if (size() != other.size()) return size() > other.size();
        return start < other.start;
    }
};

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

int min_dist_to_occupied(const Seat& s, const set<Seat>& occupied) {
    int min_dist = 1e9;
    
    // Check same row, different column
    Seat other_col(s.row, 3 - s.col);
    if (occupied.find(other_col) != occupied.end()) {
        min_dist = min(min_dist, 1);
    }
    
    // Find nearest occupied seats using binary search
    auto it = occupied.lower_bound(s);
    
    // Check next occupied seats
    if (it != occupied.end()) {
        min_dist = min(min_dist, squared_dist(s.row, s.col, it->row, it->col));
    }
    
    // Check previous occupied seats
    if (it != occupied.begin()) {
        --it;
        min_dist = min(min_dist, squared_dist(s.row, s.col, it->row, it->col));
    }
    
    return min_dist;
}

Seat find_best_in_gap(int start_row, int end_row, const set<Seat>& occupied) {
    Seat best(0, 0);
    int best_dist = -1;
    
    // Only check boundary rows for efficiency
    vector<int> rows_to_check = {start_row + 1, end_row - 1, (start_row + end_row) / 2};
    
    for (int r : rows_to_check) {
        if (r <= start_row || r >= end_row) continue;
        for (int c = 1; c <= 2; c++) {
            Seat candidate(r, c);
            if (occupied.find(candidate) == occupied.end()) {
                int dist = min_dist_to_occupied(candidate, occupied);
                if (dist > best_dist || 
                   (dist == best_dist && (r < best.row || (r == best.row && c < best.col)))) {
                    best_dist = dist;
                    best = candidate;
                }
            }
        }
    }
    
    return best;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int N, M;
    cin >> N >> M;
    
    set<Seat> occupied;
    set<int> occupied_rows;
    map<int, int> enter_event_to_passenger;
    vector<Seat> passenger_seat(M + 1);
    int passenger_count = 0;
    
    // Add boundary rows
    occupied_rows.insert(0);
    occupied_rows.insert(N + 1);
    
    for (int event_id = 1; event_id <= M; event_id++) {
        char type;
        cin >> type;
        
        if (type == 'E') {
            passenger_count++;
            enter_event_to_passenger[event_id] = passenger_count;
            
            if (occupied.empty()) {
                // First passenger gets (1, 1)
                Seat seat(1, 1);
                occupied.insert(seat);
                occupied_rows.insert(1);
                passenger_seat[passenger_count] = seat;
                cout << "1 1\n";
                continue;
            }
            
            // Find best seat by checking gaps between occupied rows
            Seat best_seat(0, 0);
            int best_min_dist = -1;
            
            // Check all gaps
            auto it = occupied_rows.begin();
            int prev = *it;
            ++it;
            
            while (it != occupied_rows.end()) {
                int curr = *it;
                if (curr - prev > 1) {
                    // This is a gap of free rows
                    Seat candidate = find_best_in_gap(prev, curr, occupied);
                    int dist = min_dist_to_occupied(candidate, occupied);
                    
                    if (dist > best_min_dist || 
                       (dist == best_min_dist && 
                        (candidate.row < best_seat.row || 
                         (candidate.row == best_seat.row && candidate.col < best_seat.col)))) {
                        best_min_dist = dist;
                        best_seat = candidate;
                    }
                }
                prev = curr;
                ++it;
            }
            
            occupied.insert(best_seat);
            occupied_rows.insert(best_seat.row);
            passenger_seat[passenger_count] = best_seat;
            cout << best_seat.row << " " << best_seat.col << "\n";
            
        } else { // type == 'L'
            int enter_event;
            cin >> enter_event;
            int passenger_id = enter_event_to_passenger[enter_event];
            Seat seat = passenger_seat[passenger_id];
            
            occupied.erase(seat);
            
            // Check if row still has occupied seats
            bool row_still_occupied = false;
            Seat other_col(seat.row, 3 - seat.col);
            if (occupied.find(other_col) != occupied.end()) {
                row_still_occupied = true;
            }
            
            if (!row_still_occupied) {
                occupied_rows.erase(seat.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