Submission #1273296

#	Time	Username	Problem	Language	Result	Execution time	Memory
1273296		anhkhoa	Tram (CEOI13_tram)	C++17	0 / 100	1097 ms	11072 KiB

tram

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

struct Seat {
    int row, col;
};

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

int main() {
    int N, M;
    cin >> N >> M;
    
    vector<vector<bool>> occupied(N + 1, vector<bool>(3, false));
    vector<Seat> passenger_seat(M + 1);
    vector<bool> active(M + 1, false);
    
    int passenger_count = 0;
    
    for (int event_id = 1; event_id <= M; event_id++) {
        char type;
        cin >> type;
        
        if (type == 'E') {
            passenger_count++;
            int current_passenger = passenger_count;
            
            if (passenger_count == 1) {
                passenger_seat[current_passenger] = {1, 1};
                occupied[1][1] = true;
                cout << "1 1\n";
                active[current_passenger] = true;
                continue;
            }
            
            Seat best_seat = {0, 0};
            int best_min_dist = -1;
            
            // Duyệt qua tất cả ghế trống
            for (int r = 1; r <= N; r++) {
                for (int c = 1; c <= 2; c++) {
                    if (!occupied[r][c]) {
                        // Tính khoảng cách NHỎ NHẤT từ ghế (r,c) tới bất kỳ ghế occupied nào
                        int min_dist = 1000000000;
                        for (int rr = 1; rr <= N; rr++) {
                            for (int cc = 1; cc <= 2; cc++) {
                                if (occupied[rr][cc]) {
                                    int dist = squared_distance(r, c, rr, cc);
                                    if (dist < min_dist) {
                                        min_dist = dist;
                                    }
                                }
                            }
                        }
                        
                        // So sánh theo yêu cầu: min_dist lớn nhất, r nhỏ nhất, c nhỏ nhất
                        if (min_dist > best_min_dist ||
                            (min_dist == best_min_dist && r < best_seat.row) ||
                            (min_dist == best_min_dist && r == best_seat.row && c < best_seat.col)) {
                            best_min_dist = min_dist;
                            best_seat = {r, c};
                        }
                    }
                }
            }
            
            passenger_seat[current_passenger] = best_seat;
            occupied[best_seat.row][best_seat.col] = true;
            cout << best_seat.row << " " << best_seat.col << "\n";
            active[current_passenger] = true;
            
        } else { // 'L'
            int p;
            cin >> p;
            if (active[p]) {
                Seat seat = passenger_seat[p];
                occupied[seat.row][seat.col] = false;
                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