Submission #1273457

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

tram

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

struct Seat {
    int row, col;
};

struct Candidate {
    long long dist2; // lưu bình phương khoảng cách để so sánh
    int row, col;
    int L, R; // interval boundaries (occupied rows around)
    bool operator<(const Candidate& o) const {
        if (dist2 != o.dist2) return dist2 < o.dist2; // max-heap
        if (row != o.row) return row > o.row;
        return col > o.col;
    }
};

int N, M;
vector<Seat> answer; // lưu ghế đã chọn cho mỗi event E
vector<bool> isEnter; // đánh dấu sự kiện nào là E
vector<vector<bool>> taken; // taken[row][col]

priority_queue<Candidate> pq;
set<int> occRows;

bool validCandidate(const Candidate& c) {
    if (c.row < 1 || c.row > N) return false;
    if (taken[c.row][c.col]) return false;
    // kiểm tra interval còn hợp lệ
    auto itL = occRows.lower_bound(c.L);
    if (itL == occRows.end() || *itL != c.L) return false;
    auto itR = occRows.lower_bound(c.R);
    if (itR == occRows.end() || *itR != c.R) return false;
    return true;
}

// thêm ứng viên cho interval (L,R)
void addInterval(int L, int R) {
    if (L > R) return;
    int mid = (L + R) / 2;
    // ta thử cả 2 cột
    for (int col = 1; col <= 2; col++) {
        long long dL = 1LL*(mid-L)*(mid-L) + (col==1?0:1);
        long long dR = 1LL*(R-mid)*(R-mid) + (col==2?0:1);
        long long mind = min(dL, dR);
        Candidate c = {mind, mid, col, L, R};
        pq.push(c);
    }
}

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

    cin >> N >> M;
    answer.resize(M+1);
    isEnter.resize(M+1);
    taken.assign(N+1, vector<bool>(3,false));

    for (int k = 1; k <= M; k++) {
        char t;
        cin >> t;
        if (t == 'E') {
            isEnter[k] = true;

            Seat chosen;
            if (occRows.empty()) {
                chosen = {1,1};
            } else {
                // lấy ứng viên hợp lệ nhất
                while (!pq.empty() && !validCandidate(pq.top())) pq.pop();
                Candidate best = pq.top(); pq.pop();
                chosen = {best.row, best.col};
            }

            taken[chosen.row][chosen.col] = true;
            answer[k] = chosen;
            cout << chosen.row << " " << chosen.col << "\n";

            // cập nhật occRows và intervals
            if (!occRows.count(chosen.row)) {
                // lần đầu có người ở row này
                auto it = occRows.insert(chosen.row).first;
                int L = (it==occRows.begin()?1:*prev(it));
                int R = (next(it)==occRows.end()?N:*next(it));
                // thêm interval trái
                if (it != occRows.begin()) addInterval(L, chosen.row);
                // thêm interval phải
                if (next(it) != occRows.end()) addInterval(chosen.row, R);
                // nếu biên
                if (it == occRows.begin()) addInterval(1, chosen.row);
                if (next(it) == occRows.end()) addInterval(chosen.row, N);
            }
        } else { // L
            int p; cin >> p;
            Seat s = answer[p];
            taken[s.row][s.col] = false;

            // nếu cả 2 ghế hàng đó trống thì xóa row khỏi occRows
            if (!taken[s.row][1] && !taken[s.row][2]) {
                auto it = occRows.find(s.row);
                int L = (it==occRows.begin()?1:*prev(it));
                int R = (next(it)==occRows.end()?N:*next(it));
                occRows.erase(it);
                // merge interval
                addInterval(L,R);
            }
        }
    }

    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