Submission #1273294

#	Time	Username	Problem	Language	Result	Execution time	Memory
1273294		anhkhoa	Tram (CEOI13_tram)	C++17	0 / 100	1096 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)); // occupied[r][c]
    vector<Seat> passenger_seat(M + 1); // passenger[i] = seat of passenger from event i
    vector<bool> active(M + 1, false); // whether passenger is still in tram
    
    int passenger_count = 0;
    
    for (int event_id = 1; event_id <= M; event_id++) {
        char type;
        cin >> type;
        
        if (type == 'E') {
            passenger_count++;
            
            if (passenger_count == 1) {
                // First passenger always gets (1, 1)
                passenger_seat[passenger_count] = {1, 1};
                occupied[1][1] = true;
                cout << "1 1\n";
                active[passenger_count] = true;
                continue;
            }
            
            // Find best seat by checking all free seats
            Seat best_seat = {0, 0};
            int best_min_dist = -1;
            
            for (int r = 1; r <= N; r++) {
                for (int c = 1; c <= 2; c++) {
                    if (!occupied[r][c]) {
                        // Calculate minimum distance to any occupied seat
                        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;
                                    }
                                }
                            }
                        }
                        
                        // Update best seat
                        if (min_dist > best_min_dist || 
                            (min_dist == best_min_dist && 
                             (r < best_seat.row || 
                              (r == best_seat.row && c < best_seat.col)))) {
                            best_min_dist = min_dist;
                            best_seat = {r, c};
                        }
                    }
                }
            }
            
            passenger_seat[passenger_count] = best_seat;
            occupied[best_seat.row][best_seat.col] = true;
            cout << best_seat.row << " " << best_seat.col << "\n";
            active[passenger_count] = true;
            
        } else { // type == '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