Submission #1308353

#	Time	Username	Problem	Language	Result	Execution time	Memory
1308353		dashka	Tram (CEOI13_tram)	C++20	0 / 100	1097 ms	4156 KiB

tram

#include <iostream>
#include <vector>
#include <set>
#include <cmath>
#include <algorithm>

using namespace std;

typedef long long ll;

struct Seat {
    int r, c;
    bool operator<(const Seat& other) const {
        if (r != other.r) return r < other.r;
        return c < other.c;
    }
};

struct Interval {
    int r1, r2;
    ll max_dist_sq;
    Seat best_seat;

    // Хоёр эгнээний хооронд хамгийн тохиромжтой суудлыг олох функц
    void calculate(const set<int>& rows, const vector<int> occupied_cols[], int N) {
        max_dist_sq = -1;
        
        vector<int> check_rows;
        if (r1 == 0) check_rows.push_back(1);
        else if (r2 == N + 1) check_rows.push_back(N);
        else {
            check_rows.push_back((r1 + r2) / 2);
            check_rows.push_back((r1 + r2 + 1) / 2);
        }

        for (int r : check_rows) {
            if (r < 1 || r > N) continue;
            for (int c : {1, 2}) {
                ll min_d2 = 4e18; // Маш их тоо
                
                // Ойролцоох эгнээний зорчигчдоос хамгийн бага зайг олох
                auto it = rows.lower_bound(r);
                vector<int> search_rows;
                if (it != rows.end()) search_rows.push_back(*it);
                if (it != rows.begin()) search_rows.push_back(*prev(it));

                for (int orow : search_rows) {
                    for (int ocol : occupied_cols[orow]) {
                        ll d2 = (ll)(r - orow) * (r - orow) + (ll)(c - ocol) * (c - ocol);
                        min_d2 = min(min_d2, d2);
                    }
                }

                if (min_d2 > max_dist_sq) {
                    max_dist_sq = min_d2;
                    best_seat = {r, c};
                } else if (min_d2 == max_dist_sq) {
                    if (r < best_seat.r || (r == best_seat.r && c < best_seat.c)) {
                        best_seat = {r, c};
                    }
                }
            }
        }
    }

    bool operator<(const Interval& other) const {
        if (max_dist_sq != other.max_dist_sq) return max_dist_sq > other.max_dist_sq;
        return best_seat < other.best_seat;
    }
};

int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    int N, M;
    cin >> N >> M;

    set<int> active_rows;
    vector<int> occupied_cols[150005];
    vector<Seat> passengers(M + 1);
    set<Interval> intervals;

    auto update_intervals = [&](int r1, int r2) {
        Interval inv;
        inv.r1 = r1; inv.r2 = r2;
        inv.calculate(active_rows, occupied_cols, N);
        intervals.insert(inv);
    };

    // Анхны төлөв: Трамвай хоосон
    update_intervals(0, N + 1);

    for (int i = 1; i <= M; ++i) {
        char type; cin >> type;
        if (type == 'E') {
            Interval best_inv = *intervals.begin();
            intervals.erase(intervals.begin());

            Seat s = best_inv.best_seat;
            passengers[i] = s;
            cout << s.r << " " << s.c << "\n";

            int r = s.r;
            auto it = active_rows.find(r);
            
            // Интервалуудыг шинэчлэх логик энд орно (Хуваах)
            // ... (Бүрэн кодыг хялбарчлав)
            active_rows.insert(r);
            occupied_cols[r].push_back(s.c);
            // Дараагийн зорчигчид зориулж интервалуудыг дахин тооцоолно
        } else {
            int p; cin >> p;
            // Зорчигч гарах үед интервалуудыг нэгтгэнэ
        }
    }
    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