Submission #1273456

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

tram

#include <bits/stdc++.h>
using namespace std;

struct Seat {
    int r, c;
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, M;
    cin >> N >> M;

    vector<Seat> ans(M + 1);     // lưu seat của mỗi sự kiện E
    vector<bool> occupied(N + 1, false); // không đủ vì 2 cột
    vector<vector<bool>> taken(N + 1, vector<bool>(3, false)); // taken[r][c]

    for (int k = 1; k <= M; k++) {
        char type;
        cin >> type;
        if (type == 'E') {
            Seat best = {1, 1};
            double bestDist = -1;

            // nếu tram trống
            bool empty = true;
            for (int i = 1; i <= N; i++)
                for (int j = 1; j <= 2; j++)
                    if (taken[i][j]) empty = false;

            if (empty) {
                best = {1, 1};
            } else {
                // thử mọi ghế trống
                for (int i = 1; i <= N; i++) {
                    for (int j = 1; j <= 2; j++) {
                        if (taken[i][j]) continue;

                        // tính dist nhỏ nhất đến ghế có người
                        double mind = 1e18;
                        for (int r = 1; r <= N; r++) {
                            for (int c = 1; c <= 2; c++) {
                                if (taken[r][c]) {
                                    double d = sqrt((i - r) * (i - r) + (j - c) * (j - c));
                                    mind = min(mind, d);
                                }
                            }
                        }

                        // chọn ghế tốt hơn
                        if (mind > bestDist ||
                            (fabs(mind - bestDist) < 1e-9 && (i < best.r ||
                              (i == best.r && j < best.c)))) {
                            bestDist = mind;
                            best = {i, j};
                        }
                    }
                }
            }

            taken[best.r][best.c] = true;
            ans[k] = best;
            cout << best.r << " " << best.c << "\n";
        } else { // L
            int p;
            cin >> p;
            Seat s = ans[p];
            taken[s.r][s.c] = false;
        }
    }

    return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 15 / 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