제출 #640208

#제출 시각아이디문제언어결과실행 시간메모리
640208colazcyMatching (COCI20_matching)C++17
18 / 110
54 ms80364 KiB
#include <cstdio> #include <cassert> #include <cstdlib> #include <vector> #include <set> #define let const auto #define rep(name,beg,end) for(auto lim_##name = end,name = beg;name <= lim_##name;name++) #define per(name,beg,end) for(auto lim_##name = end,name = beg;name >= lim_##name;name--) #define repn(lim) for(auto REPN_lIM = lim,REPN = 1;REPN <= REPN_lIM;REPN++) #define debug(...) fprintf(stderr,__VA_ARGS__) #define trace() debug("line : %d, Function : %s\n",__LINE__,__FUNCTION__) using ci = const int; constexpr int maxn = 1e5 + 100; struct Seg{ #define ls (x << 1) #define rs (x << 1 | 1) static const int M = 100000; std::set<int> s[maxn << 2]; void ins(ci a,ci b,ci v,ci l = 1,ci r = M,ci x = 1){ if(a <= l && b >= r){ s[x].insert(v); return; } let mid = (l + r) >> 1; if(a <= mid)ins(a,b,v,l,mid,ls); if(b > mid)ins(a,b,v,mid + 1,r,rs); } bool query(ci p,ci a,ci b,ci l = 1,ci r = M,ci x = 1){ let it = s[x].lower_bound(a); if(it != s[x].end() && *it <= b)return true; if(l == r)return false; let mid = (l + r) >> 1; if(p <= mid)return query(p,a,b,l,mid,ls); return query(p,a,b,mid + 1,r,rs); } #undef ls #undef rs }; struct Point{ int x,y; }p[maxn]; int n; std::vector<std::pair<int,int>> ans; [[noreturn]] void nosol(){ std::puts("NE"); std::exit(0); } Seg seg_row,seg_col; void match(ci a,ci b){ if(p[a].x == p[b].x){ let l = std::min(p[a].y,p[b].y); let r = std::max(p[a].y,p[b].y); if(seg_row.query(p[a].x,l,r))nosol(); seg_col.ins(l,r,p[a].x); } if(p[a].y == p[b].y){ let l = std::min(p[a].x,p[b].x); let r = std::max(p[a].x,p[b].x); if(seg_col.query(p[a].y,l,r))nosol(); seg_row.ins(l,r,p[a].y); } ans.emplace_back(a,b); } Seg copy_row,copy_col; bool chk(ci a,ci b){ if(p[a].x == p[b].x){ let l = std::min(p[a].y,p[b].y); let r = std::max(p[a].y,p[b].y); if(copy_row.query(p[a].x,l,r))return false; copy_col.ins(l,r,p[a].x); } if(p[a].y == p[b].y){ let l = std::min(p[a].x,p[b].x); let r = std::max(p[a].x,p[b].x); if(copy_col.query(p[a].y,l,r))return false; copy_row.ins(l,r,p[a].y); } return true; } std::vector<int> row[maxn],col[maxn]; int main(){ // #ifndef ONLINE_JUDGE // std::freopen("fufu.in","r",stdin); // #endif std::scanf("%d",&n); rep(i,1,n)std::scanf("%d %d",&p[i].x,&p[i].y); std::vector<int> now; rep(i,1,n)now.push_back(i); while(!now.empty()){ for(let i : now) row[p[i].y].push_back(i), col[p[i].x].push_back(i); std::vector<int> nxt; for(let i : now){ if(row[p[i].y].size() == 1 && col[p[i].x].size() == 1)nosol(); if(row[p[i].y].size() == 1){ let s = col[p[i].x].front(),t = col[p[i].x].back(); match(s,t); for(let i : now) if(i != s && i != t)nxt.push_back(i); goto con; } if(col[p[i].x].size() == 1){ let s = row[p[i].y].front(),t = row[p[i].y].back(); match(s,t); for(let i : now) if(i != s && i != t)nxt.push_back(i); goto con; } } { copy_row = seg_row; copy_col = seg_col; bool flg = true; rep(i,1,maxn - 1){ // debug("i = %d %d\n",i,(int)row[i].size()); // assert(row[i].size() == 0 || row[i].size() == 2); if(row[i].empty())continue; if(!chk(row[i].front(),row[i].back())){ flg = false; break; } } if(flg){ rep(i,1,maxn - 1){ if(row[i].empty())continue; match(row[i].front(),row[i].back()); } goto bre; } } { copy_row = seg_row; copy_col = seg_col; bool flg = true; rep(i,1,maxn - 1){ // assert(col[i].size() == 0 || col[i].size() == 2); if(col[i].empty())continue; if(!chk(col[i].front(),col[i].back())){ flg = false; break; } } if(flg){ rep(i,1,maxn - 1){ if(col[i].empty())continue; match(col[i].front(),col[i].back()); } goto bre; } } nosol(); bre: break; con: for(let i : now) row[p[i].y].clear(), col[p[i].x].clear(); now = nxt; continue; } std::puts("DA"); for(let &pir : ans)std::printf("%d %d\n",pir.first,pir.second); return 0; }

컴파일 시 표준 에러 (stderr) 메시지

matching.cpp: In function 'int main()':
matching.cpp:88:15: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   88 |     std::scanf("%d",&n);
      |     ~~~~~~~~~~^~~~~~~~~
matching.cpp:89:25: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   89 |     rep(i,1,n)std::scanf("%d %d",&p[i].x,&p[i].y);
      |               ~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
#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...