Submission #1083565

#TimeUsernameProblemLanguageResultExecution timeMemory
1083565serifefedartarMatching (COCI20_matching)C++17
18 / 110
2 ms2908 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 int x[MAXN], y[MAXN]; set<pair<int,int>> active; vector<pair<int,int>> ans, P[MAXN]; void check() { 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()) return ; cout << "DA\n"; for (auto u : ans) cout << u.f << " " << u.s << "\n"; exit(0); } signed main() { fast; int N; cin >> N; for (int i = 0; i < N; i++) { cin >> x[i] >> y[i]; P[x[i]].push_back({y[i], i+1}); } check(); active.clear(); ans.clear(); for (int i = 0; i < MAXN; i++) P[i].clear(); for (int i = 0; i < N; i++) P[y[i]].push_back({x[i], i+1}); check(); cout << "NE\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...