oj.uz

Submission #640208

# Submission time Handle Problem Language Result Execution time Memory
640208 2022-09-14T01:48:44 Z colazcy Matching (COCI20_matching) C++17
18 / 110
 54 ms 80364 KB 
#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;
}

Compilation message

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);
      |               ~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 80204 KB Output is correct
2 Correct 43 ms 80136 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 80204 KB Output is correct
2 Correct 43 ms 80136 KB Output is correct
3 Correct 45 ms 80204 KB Output is correct
4 Correct 44 ms 80152 KB Output is correct
5 Correct 43 ms 80200 KB Output is correct
6 Correct 50 ms 80192 KB Output is correct
7 Correct 35 ms 80196 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 80204 KB Output is correct
2 Correct 43 ms 80136 KB Output is correct
3 Correct 45 ms 80204 KB Output is correct
4 Correct 44 ms 80152 KB Output is correct
5 Correct 43 ms 80200 KB Output is correct
6 Correct 50 ms 80192 KB Output is correct
7 Correct 35 ms 80196 KB Output is correct
8 Correct 46 ms 80184 KB Output is correct
9 Correct 40 ms 80212 KB Output is correct
10 Correct 42 ms 80204 KB Output is correct
11 Correct 38 ms 80196 KB Output is correct
12 Correct 54 ms 80192 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 80204 KB Output is correct
2 Correct 43 ms 80136 KB Output is correct
3 Correct 45 ms 80204 KB Output is correct
4 Correct 44 ms 80152 KB Output is correct
5 Correct 43 ms 80200 KB Output is correct
6 Correct 50 ms 80192 KB Output is correct
7 Correct 35 ms 80196 KB Output is correct
8 Correct 46 ms 80184 KB Output is correct
9 Correct 40 ms 80212 KB Output is correct
10 Correct 42 ms 80204 KB Output is correct
11 Correct 38 ms 80196 KB Output is correct
12 Correct 54 ms 80192 KB Output is correct
13 Incorrect 53 ms 80364 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #5
0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 80204 KB Output is correct
2 Correct 43 ms 80136 KB Output is correct
3 Correct 45 ms 80204 KB Output is correct
4 Correct 44 ms 80152 KB Output is correct
5 Correct 43 ms 80200 KB Output is correct
6 Correct 50 ms 80192 KB Output is correct
7 Correct 35 ms 80196 KB Output is correct
8 Correct 46 ms 80184 KB Output is correct
9 Correct 40 ms 80212 KB Output is correct
10 Correct 42 ms 80204 KB Output is correct
11 Correct 38 ms 80196 KB Output is correct
12 Correct 54 ms 80192 KB Output is correct
13 Incorrect 53 ms 80364 KB Output isn't correct
14 Halted 0 ms 0 KB -