Submission #1083534

#TimeUsernameProblemLanguageResultExecution timeMemory
1083534serifefedartarMatching (COCI20_matching)C++17
11 / 110
2 ms2652 KiB
#include <bits/stdc++.h> using namespace std; #define fast ios::sync_with_stdio(0);cin.tie(0) typedef long long ll; #define f first #define s second #define LOGN 21 const ll MOD = 1e9 + 7; const ll MAXN = 1e5 + 100; #define int long long set<pair<int,int>> active; vector<pair<int,int>> ans, P[MAXN]; signed main() { fast; int N, x, y; cin >> N; for (int i = 0; i < N; i++) { cin >> x >> y; P[x].push_back({y, i+1}); } for (int i = 1; i < MAXN; i++) { if (P[i].size() == 2 && P[i][0].f == P[i][1].f) { ans.push_back({P[i][0].s, P[i][1].s}); P[i].clear(); } } for (int i = 1; i < MAXN; i++) { if (P[i].size() == 2) { int x1 = P[i][0].f, x2 = P[i][1].f; auto u = active.lower_bound({x1, 0}); auto v = active.lower_bound({x2, 1e9}); if (u == v) ans.push_back({P[i][0].s, P[i][1].s}); else { auto P1 = active.lower_bound({x1, 0}); auto P2 = active.lower_bound({x2, 0}); if (P1 != active.end() && (*P1).f == x1) { ans.push_back({P[i][0].s, (*P1).s}); active.erase(P1); } else active.insert({x1, P[i][0].s}); if (P2 != active.end() && (*P2).f == x2) { ans.push_back({P[i][1].s, (*P2).s}); active.erase(P2); } else active.insert({x2, P[i][1].s}); } } else if (P[i].size() == 1) { int x1 = P[i][0].f; auto P1 = active.lower_bound({x1, 0}); if (P1 != active.end() && (*P1).f == x1) { ans.push_back({P[i][0].s, (*P1).s}); active.erase(P1); } else active.insert({x1, P[i][0].s}); } } if (active.size()) cout << "NE\n"; else { cout << "DA\n"; for (auto u : ans) cout << u.f << " " << u.s << "\n"; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...