Submission #640225

#	Time	Username	Problem	Language	Result	Execution time	Memory
640225		colazcy	Matching (COCI20_matching)	C++17	110 / 110	2354 ms	84364 KiB

matching

#include <cstdio>
#include <cassert>
#include <cstdlib>
#include <vector>
#include <set>
#include <algorithm>
#include <queue>
#include <utility>
#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);
}

bool vis[maxn];
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);
    }
    vis[a] = vis[b] = 1;
    ans.emplace_back(a,b);
}
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(seg_row.query(p[a].x,l,r))return false;
    }
    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))return false;
    }
    return true;
}

struct Rect{
    int a,b,c,d;
};

std::vector<Rect> rect;
std::vector<int> row[maxn],col[maxn];

std::vector<int> G[maxn];
int deg[maxn];
void addedge(ci u,ci v){
    G[u].push_back(v);
    G[v].push_back(u);
    deg[u]++;
    deg[v]++;
}
void topo(){
    std::queue<int> q;
    rep(i,1,n)
        if(!deg[i])nosol();
    rep(i,1,n)
        if(deg[i] == 1)q.push(i);
    while(!q.empty()){
        let u = q.front(); q.pop();
        for(let v : G[u]){
            if(vis[v])continue;
            if(!vis[u])match(u,v);
            if(--deg[v] == 1)q.push(v);
        }
    }
}

std::vector<int> stk;
void dfs(const int u){
    if(vis[u])return;
    vis[u] = 1;
    stk.push_back(u);
    for(let v : G[u])dfs(v);
}
std::vector<std::pair<std::vector<std::pair<int,int>>,std::vector<std::pair<int,int>>>> fuck;

int main(){
    std::scanf("%d",&n);
    rep(i,1,n)std::scanf("%d %d",&p[i].x,&p[i].y);
    rep(i,1,n)
        row[p[i].y].push_back(i),
        col[p[i].x].push_back(i);
    rep(i,0,maxn - 1)
        if(row[i].size() == 2)
            addedge(row[i].front(),row[i].back());
    rep(i,0,maxn - 1)
        if(col[i].size() == 2)
            addedge(col[i].front(),col[i].back());
    topo();
    rep(i,1,n)
        if(!vis[i]){
            stk.clear();
            dfs(i);
            for(let s : stk)
                if(!deg[s])nosol();
            std::vector<std::pair<int,int>> A,B;
            A.reserve(stk.size() >> 1);
            B.reserve(stk.size() >> 1);
            for(size_t i = 1;i < stk.size();i += 2)A.emplace_back(stk[i - 1],stk[i]);

            for(size_t i = 2;i < stk.size();i += 2)B.emplace_back(stk[i - 1],stk[i]);
            B.emplace_back(stk.front(),stk.back());
            fuck.emplace_back(std::move(A),std::move(B));
        }

    std::set<int> s;
    for(size_t i = 0;i < fuck.size();i++)s.insert(i);
    while(!s.empty()){
        bool flg = false;
        for(auto it = s.begin();it != s.end();){
            let i = *it;
            let &pir = fuck[i];
            bool fA = true,fB = true;
            for(let &p : pir.first)
                if(!chk(p.first,p.second)){
                    fA = false;
                    break;
                }
            for(let &p : pir.second)
                if(!chk(p.first,p.second)){
                    fB = false;
                    break;
                }
            if(!fA && !fB)nosol();
            if(fA && fB){
                it++;
                continue;
            }
            flg = true;
            if(fA)
                for(let &p : pir.first)match(p.first,p.second);
            if(fB)
                for(let &p : pir.second)match(p.first,p.second);
            it = s.erase(it);
        }
            
        if(!flg){
            let it = s.begin();
            let i = *it;
            let &pir = fuck[i];
            for(let &p : pir.first)match(p.first,p.second);
            s.erase(it);
        }
    }
    std::puts("DA");
    for(let &pir : ans)std::printf("%d %d\n",pir.first,pir.second);
    assert(ans.size() == n / 2);
    return 0;
}

Compilation message (stderr)

In file included from /usr/include/c++/10/cassert:44,
                 from matching.cpp:2:
matching.cpp: In function 'int main()':
matching.cpp:197:23: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  197 |     assert(ans.size() == n / 2);
      |            ~~~~~~~~~~~^~~~~~~~
matching.cpp:128:15: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  128 |     std::scanf("%d",&n);
      |     ~~~~~~~~~~^~~~~~~~~
matching.cpp:129:25: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  129 |     rep(i,1,n)std::scanf("%d %d",&p[i].x,&p[i].y);
      |               ~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 6 / 6
• Subtask 3: 7 / 7
• Subtask 4: 40 / 40
• Subtask 5: 52 / 52