oj.uz

Submission #640207

# Submission time Handle Problem Language Result Execution time Memory
640207 2022-09-14T01:44:53 Z colazcy Matching (COCI20_matching) C++17
5 / 110
 49 ms 80212 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()){
        // debug("now = \n");
        // for(let i : now)debug("%d ",i);
        // debug("\n");

        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;
            }
        }


        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 42 ms 80212 KB Output is correct
2 Correct 42 ms 80188 KB Output is correct

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 80212 KB Output is correct
2 Correct 42 ms 80188 KB Output is correct
3 Correct 42 ms 80180 KB Output is correct
4 Correct 49 ms 80176 KB Output is correct
5 Correct 45 ms 80204 KB Output is correct
6 Incorrect 46 ms 80196 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 80212 KB Output is correct
2 Correct 42 ms 80188 KB Output is correct
3 Correct 42 ms 80180 KB Output is correct
4 Correct 49 ms 80176 KB Output is correct
5 Correct 45 ms 80204 KB Output is correct
6 Incorrect 46 ms 80196 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 80212 KB Output is correct
2 Correct 42 ms 80188 KB Output is correct
3 Correct 42 ms 80180 KB Output is correct
4 Correct 49 ms 80176 KB Output is correct
5 Correct 45 ms 80204 KB Output is correct
6 Incorrect 46 ms 80196 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #5
0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 80212 KB Output is correct
2 Correct 42 ms 80188 KB Output is correct
3 Correct 42 ms 80180 KB Output is correct
4 Correct 49 ms 80176 KB Output is correct
5 Correct 45 ms 80204 KB Output is correct
6 Incorrect 46 ms 80196 KB Output isn't correct
7 Halted 0 ms 0 KB -