oj.uz

Submission #640224

# Submission time Handle Problem Language Result Execution time Memory
640224 2022-09-14T03:21:02 Z colazcy Matching (COCI20_matching) C++17
110 / 110
 2144 ms 85424 KB 
#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(){
// #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);
    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::vector<bool> vis(fuck.size(),false);
    int cnt = 0;
    while(cnt != (int)fuck.size()){
        bool flg = false;
        for(size_t i = 0;i < fuck.size();i++)
            if(!vis[i]){
                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)continue;
                flg = true;
                vis[i] = true;
                cnt++;
                if(fA)
                    for(let &p : pir.first)match(p.first,p.second);
                if(fB)
                    for(let &p : pir.second)match(p.first,p.second);
            }
            
        if(!flg){
            for(size_t i = 0;i < fuck.size();i++)
                if(!vis[i]){
                    let &pir = fuck[i];
                    vis[i] = true;
                    cnt++;
                    for(let &p : pir.first)match(p.first,p.second);
                    break;               
                }
        }
    }
    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

In file included from /usr/include/c++/10/cassert:44,
                 from matching.cpp:2:
matching.cpp: In function 'int main()':
matching.cpp:201: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]
  201 |     assert(ans.size() == n / 2);
      |            ~~~~~~~~~~~^~~~~~~~
matching.cpp:131:15: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  131 |     std::scanf("%d",&n);
      |     ~~~~~~~~~~^~~~~~~~~
matching.cpp:132:25: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  132 |     rep(i,1,n)std::scanf("%d %d",&p[i].x,&p[i].y);
      |               ~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 44884 KB Output is correct
2 Correct 21 ms 44928 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 44884 KB Output is correct
2 Correct 21 ms 44928 KB Output is correct
3 Correct 22 ms 44868 KB Output is correct
4 Correct 21 ms 44964 KB Output is correct
5 Correct 22 ms 44896 KB Output is correct
6 Correct 24 ms 44852 KB Output is correct
7 Correct 23 ms 44840 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 44884 KB Output is correct
2 Correct 21 ms 44928 KB Output is correct
3 Correct 22 ms 44868 KB Output is correct
4 Correct 21 ms 44964 KB Output is correct
5 Correct 22 ms 44896 KB Output is correct
6 Correct 24 ms 44852 KB Output is correct
7 Correct 23 ms 44840 KB Output is correct
8 Correct 25 ms 44948 KB Output is correct
9 Correct 21 ms 44900 KB Output is correct
10 Correct 21 ms 44904 KB Output is correct
11 Correct 24 ms 44968 KB Output is correct
12 Correct 25 ms 44952 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 44884 KB Output is correct
2 Correct 21 ms 44928 KB Output is correct
3 Correct 22 ms 44868 KB Output is correct
4 Correct 21 ms 44964 KB Output is correct
5 Correct 22 ms 44896 KB Output is correct
6 Correct 24 ms 44852 KB Output is correct
7 Correct 23 ms 44840 KB Output is correct
8 Correct 25 ms 44948 KB Output is correct
9 Correct 21 ms 44900 KB Output is correct
10 Correct 21 ms 44904 KB Output is correct
11 Correct 24 ms 44968 KB Output is correct
12 Correct 25 ms 44952 KB Output is correct
13 Correct 40 ms 45508 KB Output is correct
14 Correct 38 ms 45532 KB Output is correct
15 Correct 40 ms 45516 KB Output is correct
16 Correct 37 ms 45440 KB Output is correct
17 Correct 32 ms 45492 KB Output is correct
18 Correct 39 ms 45560 KB Output is correct
19 Correct 38 ms 45664 KB Output is correct
20 Correct 42 ms 45516 KB Output is correct
21 Correct 22 ms 45064 KB Output is correct
22 Correct 25 ms 45080 KB Output is correct
23 Correct 27 ms 45616 KB Output is correct
24 Correct 24 ms 45524 KB Output is correct

Subtask #5
52.0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 44884 KB Output is correct
2 Correct 21 ms 44928 KB Output is correct
3 Correct 22 ms 44868 KB Output is correct
4 Correct 21 ms 44964 KB Output is correct
5 Correct 22 ms 44896 KB Output is correct
6 Correct 24 ms 44852 KB Output is correct
7 Correct 23 ms 44840 KB Output is correct
8 Correct 25 ms 44948 KB Output is correct
9 Correct 21 ms 44900 KB Output is correct
10 Correct 21 ms 44904 KB Output is correct
11 Correct 24 ms 44968 KB Output is correct
12 Correct 25 ms 44952 KB Output is correct
13 Correct 40 ms 45508 KB Output is correct
14 Correct 38 ms 45532 KB Output is correct
15 Correct 40 ms 45516 KB Output is correct
16 Correct 37 ms 45440 KB Output is correct
17 Correct 32 ms 45492 KB Output is correct
18 Correct 39 ms 45560 KB Output is correct
19 Correct 38 ms 45664 KB Output is correct
20 Correct 42 ms 45516 KB Output is correct
21 Correct 22 ms 45064 KB Output is correct
22 Correct 25 ms 45080 KB Output is correct
23 Correct 27 ms 45616 KB Output is correct
24 Correct 24 ms 45524 KB Output is correct
25 Correct 1720 ms 67448 KB Output is correct
26 Correct 665 ms 67512 KB Output is correct
27 Correct 2144 ms 67544 KB Output is correct
28 Correct 1799 ms 67524 KB Output is correct
29 Correct 551 ms 58548 KB Output is correct
30 Correct 574 ms 58392 KB Output is correct
31 Correct 528 ms 61568 KB Output is correct
32 Correct 531 ms 60924 KB Output is correct
33 Correct 73 ms 52684 KB Output is correct
34 Correct 83 ms 54344 KB Output is correct
35 Correct 74 ms 52616 KB Output is correct
36 Correct 407 ms 85424 KB Output is correct
37 Correct 1099 ms 71924 KB Output is correct
38 Correct 647 ms 71184 KB Output is correct