// https://dk-gl.eu/zap-checker // Checkerka do zadania Zapobiegliwy Student // XXXI OI - etap 1 // By Mikołaj Zabłocki: https://github.com/dominik-korsa // Kompatybilna z Tosterem: // https://github.com/MikolajKolek/toster #include #include #include #include using namespace std; struct Selection { int mainId; int backupId; }; enum EventType { MainBegin = 0, MainEnd = 1, BackupBegin = 2, BackupEnd = 3, }; struct Event { int pos; EventType type; Selection* selection; inline bool isBegin() const { return type == MainBegin || type == BackupBegin; } }; bool operator<(const Event &lhs, const Event &rhs) { if (lhs.pos == rhs.pos) return !lhs.isBegin() && rhs.isBegin(); return lhs.pos < rhs.pos; } int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); // Parsing input int n; cin >> n; vector> ranges(n); for (auto &[a, b]: ranges) cin >> a >> b; // end int k; cin >> k; vector events; events.reserve(4 * k); vector selections(k); for (auto &selection: selections) { cin >> selection.mainId >> selection.backupId; --selection.mainId; --selection.backupId; if (selection.mainId < 0 || selection.mainId >= n) { cout << "I W odpowiedzi podano nieistniejacy wyklad podstawowy #" << selection.mainId+1 << endl; exit(0); } if (selection.backupId < 0 || selection.backupId >= n) { cout << "I W odpowiedzi podano nieistniejacy wyklad zapasowy #" << selection.backupId+1 << endl; exit(0); } if (selection.mainId == selection.backupId) { cout << "I Wyklad #" << selection.mainId+1 << " jest zapasowy dla samego siebie"; exit(0); } auto &mainRange = ranges[selection.mainId]; auto &backupRange = ranges[selection.backupId]; events.push_back({ mainRange.first, MainBegin, &selection }); events.push_back({ mainRange.second, MainEnd, &selection }); events.push_back({ backupRange.first, BackupBegin, &selection }); events.push_back({ backupRange.second, BackupEnd, &selection }); } sort(events.begin(), events.end()); Selection* openMain = nullptr; unordered_set openBackups; for (auto &event: events) { switch (event.type) { case MainBegin: { if (openMain != nullptr) { if (openMain->mainId == event.selection->mainId) { cout << "I Wyklad podstawowy #" << event.selection->mainId+1 << " zostal wybrany wiecej niz raz" << endl; exit(0); } cout << "I Wyklady podstawowe #" << event.selection->mainId+1 << " i #" << openMain->mainId+1 << " koliduja ze soba" << endl; exit(0); } for (auto &backupSelection: openBackups) { if (event.selection->mainId != backupSelection->mainId) { cout << "I Wyklad zapasowy #" << backupSelection->backupId+1 << " (dla wykladu podstawowego #" << backupSelection->mainId+1 << ") koliduje z wykladem podstawowym #" << event.selection->mainId+1 << endl; exit(0); } } openMain = event.selection; break; } case MainEnd: { openMain = nullptr; break; } case BackupBegin: { if (openMain != nullptr && openMain->mainId != event.selection->mainId) { cout << "I Wyklad zapasowy #" << event.selection->backupId+1 << " (dla wykladu podstawowego #" << event.selection->mainId+1 << ") koliduje z wykladem podstawowym #" << openMain->mainId+1 << endl; exit(0); } openBackups.insert(event.selection); break; } case BackupEnd: { openBackups.erase(event.selection); break; } } } cout << "C" << endl; return 0; }