Submission #1308349

#	Time	Username	Problem	Language	Result	Execution time	Memory
1308349		dashka	Tram (CEOI13_tram)	C++20	0 / 100	1096 ms	980 KiB

tram

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int N, M;
    cin >> N >> M;
    
    // Баганын 1 болон 2-д эзлэгдсэн мөрүүдийг хадгална
    set<int> col[2]; // col[0] = багана 1, col[1] = багана 2
    map<int, pair<int, int>> passenger_seat;
    
    for (int event = 1; event <= M; event++) {
        char type;
        cin >> type;
        
        if (type == 'E') {
            int best_row = 1, best_col = 0;
            
            if (col[0].empty() && col[1].empty()) {
                best_row = 1;
                best_col = 0;
            } else {
                double max_dist = -1;
                
                // Candidate суудлуудыг шалгах
                set<pair<int, int>> candidates;
                
                // Эхний болон сүүлчийн мөр
                candidates.insert({1, 0});
                candidates.insert({1, 1});
                candidates.insert({N, 0});
                candidates.insert({N, 1});
                
                // Эзлэгдсэн суудлын хооронд
                for (int c = 0; c < 2; c++) {
                    if (!col[c].empty()) {
                        auto it = col[c].begin();
                        int prev = *it;
                        ++it;
                        while (it != col[c].end()) {
                            int curr = *it;
                            int mid = (prev + curr) / 2;
                            candidates.insert({mid, c});
                            if ((prev + curr) % 2 == 1) {
                                candidates.insert({mid + 1, c});
                            }
                            prev = curr;
                            ++it;
                        }
                    }
                }
                
                // Бүх candidate-уудыг шалгах
                for (auto [r, c] : candidates) {
                    if (r < 1 || r > N) continue;
                    if (col[c].count(r)) continue; // Эзлэгдсэн бол
                    
                    double min_dist = 1e18;
                    
                    // Өөрийн баганаас ойрхон эзлэгдсэн суудал
                    auto it = col[c].lower_bound(r);
                    if (it != col[c].end()) {
                        min_dist = min(min_dist, (double)abs(r - *it));
                    }
                    if (it != col[c].begin()) {
                        --it;
                        min_dist = min(min_dist, (double)abs(r - *it));
                    }
                    
                    // Нөгөө баганаас ойрхон эзлэгдсэн суудал
                    int other = 1 - c;
                    it = col[other].lower_bound(r);
                    if (it != col[other].end()) {
                        int dr = r - *it;
                        min_dist = min(min_dist, sqrt(dr * dr + 1.0));
                    }
                    if (it != col[other].begin()) {
                        --it;
                        int dr = r - *it;
                        min_dist = min(min_dist, sqrt(dr * dr + 1.0));
                    }
                    
                    // Хамгийн сайн суудлыг сонгох
                    if (min_dist > max_dist) {
                        max_dist = min_dist;
                        best_row = r;
                        best_col = c;
                    } else if (abs(min_dist - max_dist) < 1e-9) {
                        // Тэнцүү бол row, column-оор эрэмбэлэх
                        if (r < best_row || (r == best_row && c < best_col)) {
                            best_row = r;
                            best_col = c;
                        }
                    }
                }
            }
            
            col[best_col].insert(best_row);
            passenger_seat[event] = {best_row, best_col};
            cout << best_row << " " << (best_col + 1) << "\n";
            
        } else { // type == 'L'
            int P;
            cin >> P;
            
            auto [row, c] = passenger_seat[P];
            col[c].erase(row);
            passenger_seat.erase(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