oj.uz

답안 #223483

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
223483 2020-04-15T10:05:48 Z shenxy Matching (COCI20_matching) C++11
58 / 110
 2500 ms 291000 KB 
#include <cstdio>
#include <algorithm>
#include <queue>
#define m ((s + e)>>1)
using namespace std;
typedef pair<int, int> ii;
typedef pair<ii, int> iii;
const int INF = 10000000;
ii lca(int s,int e,int l,int r,int pos){
    if (r<=m && m<pos) return ii(s,e);
    else if (pos<=m && m<l) return ii(s,e);
    if (pos<=m) return lca(s,m,l,r,pos);
    else return lca(m+1,e,l,r,pos);
}
struct minnode{
    int s,e;
    ii val=ii(INF, -1);
    minnode *l=nullptr,*r=nullptr;
    minnode (int _s,int _e){
        s=_s,e=_e;
    }
    bool inside(int i){
        return s<=i && i<=e;
    }
    void update(int i,ii j){
        if (s==e) val=j;
        else{
            if (i<=m){
                if (l==nullptr) l=new minnode(i,i);
                else if (!l->inside(i)){
                    minnode *temp=l;
                    ii child=lca(s,e,l->s,l->e,i);
                    l=new minnode(child.first,child.second);
                    if (temp->e<=(l->s+l->e)>>1) l->l=temp;
                    else l->r=temp;
                }
                l->update(i,j);
            }
            else{
                if (r==nullptr) r=new minnode(i,i);
                else if (!r->inside(i)){
                    minnode *temp=r;
                    ii child=lca(s,e,r->s,r->e,i);
                    r=new minnode(child.first,child.second);
                    if (temp->e<=(r->s+r->e)>>1) r->l=temp;
                    else r->r=temp;
                }
                r->update(i,j);
            }
            val=min((l==nullptr)?ii(INF,-1):l->val,(r==nullptr)?ii(INF,-1):r->val);
        }
    }
    ii query(int i,int j){
        if (i<=s && e<=j) return val;
        else if (j<=m) return (l==nullptr)?ii(INF,-1):l->query(i,j);
        else if (m<i) return (r==nullptr)?ii(INF,-1):r->query(i,j);
        else return min((l==nullptr)?ii(INF,-1):l->query(i,m),(r==nullptr)?ii(INF,-1):r->query(m+1,j));
    }
    minnode* clone(){
        minnode* res=new minnode(s,e);
        res->val=val;
        res->l=(l==nullptr)?nullptr:l->clone();
        res->r=(r==nullptr)?nullptr:r->clone();
        return res;
    }
};
struct minnode2d{
    int s,e;
    minnode *val=new minnode(1,100000);
    minnode2d *l=nullptr,*r=nullptr;
    minnode2d (int _s,int _e){
        s=_s,e=_e;
    }
    bool inside(int i){
        return s<=i && i<=e;
    }
    void update(int i,int j,ii k){
        if (s==e) val->update(j,k);
        else{
            if (i<=m){
                if (l==nullptr) l=new minnode2d(i,i);
                else if (!l->inside(i)){
                    minnode2d *temp=l;
                    ii child=lca(s,e,l->s,l->e,i);
                    l=new minnode2d(child.first,child.second);
                    if (temp->e<=(l->s+l->e)>>1) l->l=temp;
                    else l->r=temp;
                    l->val=temp->val->clone();
                }
                l->update(i,j,k);
            }
            else{
                if (r==nullptr) r=new minnode2d(i,i);
                else if (!r->inside(i)){
                    minnode2d *temp=r;
                    ii child=lca(s,e,r->s,r->e,i);
                    r=new minnode2d(child.first,child.second);
                    if (temp->e<=(r->s+r->e)>>1) r->l=temp;
                    else r->r=temp;
                    r->val=temp->val->clone();
                }
                r->update(i,j,k);
            }
            val->update(j,min((l==nullptr)?ii(INF,-1):l->val->query(j,j),(r==nullptr)?ii(INF,-1):r->val->query(j,j)));
        }
    }
    ii query(int i,int j,int i2,int j2){
        if (i<=s && e<=j) return val->query(i2,j2);
        else if (j<=m) return (l==nullptr)?ii(INF,-1):l->query(i,j,i2,j2);
        else if (m<i) return (r==nullptr)?ii(INF,-1):r->query(i,j,i2,j2);
        else return min((l==nullptr)?ii(INF,-1):l->query(i,m,i2,j2),(r==nullptr)?ii(INF,-1):r->query(m+1,j,i2,j2));
    }
};
struct maxnode{
    int s,e;
    ii val=ii(0,-1);
    maxnode *l=nullptr,*r=nullptr;
    maxnode (int _s,int _e){
        s=_s,e=_e;
    }
    bool inside(int i){
        return s<=i && i<=e;
    }
    void update(int i,ii j){
        if (s==e) val=j;
        else{
            if (i<=m){
                if (l==nullptr) l=new maxnode(i,i);
                else if (!l->inside(i)){
                    maxnode *temp=l;
                    ii child=lca(s,e,l->s,l->e,i);
                    l=new maxnode(child.first,child.second);
                    if (temp->e<=(l->s+l->e)>>1) l->l=temp;
                    else l->r=temp;
                }
                l->update(i,j);
            }
            else{
                if (r==nullptr) r=new maxnode(i,i);
                else if (!r->inside(i)){
                    maxnode *temp=r;
                    ii child=lca(s,e,r->s,r->e,i);
                    r=new maxnode(child.first,child.second);
                    if (temp->e<=(r->s+r->e)>>1) r->l=temp;
                    else r->r=temp;
                }
                r->update(i,j);
            }
            val=max((l==nullptr)?ii(0,-1):l->val,(r==nullptr)?ii(0,-1):r->val);
        }
    }
    ii query(int i,int j){
        if (i<=s && e<=j) return val;
        else if (j<=m) return (l==nullptr)?ii(0,-1):l->query(i,j);
        else if (m<i) return (r==nullptr)?ii(0,-1):r->query(i,j);
        else return max((l==nullptr)?ii(0,-1):l->query(i,m),(r==nullptr)?ii(0,-1):r->query(m+1,j));
    }
    maxnode* clone(){
        maxnode* res=new maxnode(s,e);
        res->val=val;
        res->l=(l==nullptr)?nullptr:l->clone();
        res->r=(r==nullptr)?nullptr:r->clone();
        return res;
    }
};
struct maxnode2d{
    int s,e;
    maxnode *val=new maxnode(1,100000);
    maxnode2d *l=nullptr,*r=nullptr;
    maxnode2d (int _s,int _e){
        s=_s,e=_e;
    }
    bool inside(int i){
        return s<=i && i<=e;
    }
    void update(int i,int j,ii k){
        if (s==e) val->update(j,k);
        else{
            if (i<=m){
                if (l==nullptr) l=new maxnode2d(i,i);
                else if (!l->inside(i)){
                    maxnode2d *temp=l;
                    ii child=lca(s,e,l->s,l->e,i);
                    l=new maxnode2d(child.first,child.second);
                    if (temp->e<=(l->s+l->e)>>1) l->l=temp;
                    else l->r=temp;
                    l->val=temp->val->clone();
                }
                l->update(i,j,k);
            }
            else{
                if (r==nullptr) r=new maxnode2d(i,i);
                else if (!r->inside(i)){
                    maxnode2d *temp=r;
                    ii child=lca(s,e,r->s,r->e,i);
                    r=new maxnode2d(child.first,child.second);
                    if (temp->e<=(r->s+r->e)>>1) r->l=temp;
                    else r->r=temp;
                    r->val=temp->val->clone();
                }
                r->update(i,j,k);
            }
            val->update(j,max((l==nullptr)?ii(0,-1):l->val->query(j,j),(r==nullptr)?ii(0,-1):r->val->query(j,j)));
        }
    }
    ii query(int i,int j,int i2,int j2){
        if (i<=s && e<=j) return val->query(i2,j2);
        else if (j<=m) return (l==nullptr)?ii(0,-1):l->query(i,j,i2,j2);
        else if (m<i) return (r==nullptr)?ii(0,-1):r->query(i,j,i2,j2);
        else return max((l==nullptr)?ii(0,-1):l->query(i,m,i2,j2),(r==nullptr)?ii(0,-1):r->query(m+1,j,i2,j2));
    }
};
bool comp(const iii &a, const iii &b) {
	if (a.first.second != b.first.second) return a.first.second < b.first.second;
	return a < b;
}
int main() {
	int N;
	scanf("%d", &N);
	iii xy[N];
	ii pos[N];
	minnode2d *minx = new minnode2d(1, 100000), *miny = new minnode2d(1, 100000);
	maxnode2d *maxx = new maxnode2d(1, 100000), *maxy = new maxnode2d(1, 100000);
	for (int i = 0; i < N; ++i) scanf("%d %d", &pos[i].first, &pos[i].second), xy[i].first = pos[i], xy[i].second = i;
	sort(xy, xy + N);
	int xf[N], yf[N];
	xf[xy[0].second] = -1;
	for (int i = 1; i < N; ++i) {
		if (xy[i - 1].first.first == xy[i].first.first) xf[xy[i - 1].second] = xy[i].second, xf[xy[i].second] = xy[i - 1].second;
		else xf[xy[i].second] = -1;
	}
	sort(xy, xy + N, comp);
	yf[xy[0].second] = -1;
	for (int i = 1; i < N; ++i) {
		if (xy[i - 1].first.second == xy[i].first.second) yf[xy[i - 1].second] = xy[i].second, yf[xy[i].second] = xy[i - 1].second;
		else yf[xy[i].second] = -1;
	}
	queue<int> despo;
	for (int i = 0; i < N; ++i) {
		if (xf[i] == -1 && yf[i] == -1) {
			printf("NE");
			return 0;
		} else if (xf[i] == -1 || yf[i] == -1) despo.push(i);
		if (xf[i] != -1) minx -> update(pos[i].first, pos[i].second, ii(pos[xf[i]].second, i)), maxx -> update(pos[i].first, pos[i].second, ii(pos[xf[i]].second, i));
		if (yf[i] != -1) miny -> update(pos[i].first, pos[i].second, ii(pos[yf[i]].first, i)), maxy -> update(pos[i].first, pos[i].second, ii(pos[yf[i]].first, i));
	}
	vector<ii> pairs;
	bool settled[N];
	fill_n(settled, N, false);
	while (!despo.empty()) {
		int pt1 = despo.front(), pt2;
		despo.pop();
		if (settled[pt1]) continue;
		if (xf[pt1] != -1) {
			pt2 = xf[pt1];
			minx -> update(pos[pt1].first, pos[pt1].second, ii(INF, -1)), maxx -> update(pos[pt1].first, pos[pt1].second, ii(0, -1));
			minx -> update(pos[pt2].first, pos[pt2].second, ii(INF, -1)), maxx -> update(pos[pt2].first, pos[pt2].second, ii(0, -1));
			if (yf[pt2] != -1) {
				miny -> update(pos[pt2].first, pos[pt2].second, ii(INF, -1)), maxy -> update(pos[pt2].first, pos[pt2].second, ii(0, -1));
				miny -> update(pos[yf[pt2]].first, pos[yf[pt2]].second, ii(INF, -1)), maxy -> update(pos[yf[pt2]].first, pos[yf[pt2]].second, ii(0, -1));
				yf[yf[pt2]] = -1;
				if (xf[yf[pt2]] == -1) {
					printf("NE");
					return 0;
				} else despo.push(yf[pt2]);
			}
			ii qans = maxy -> query(1, pos[pt1].first - 1, min(pos[pt1].second, pos[pt2].second), max(pos[pt1].second, pos[pt2].second));
			while (qans.first > pos[pt1].first) {
				miny -> update(pos[qans.second].first, pos[qans.second].second, ii(INF, -1)), maxy -> update(pos[qans.second].first, pos[qans.second].second, ii(0, -1));
				yf[qans.second] = -1;
				if (xf[qans.second] == -1) {
					printf("NE");
					return 0;
				} else despo.push(qans.second);
				qans = maxy -> query(1, pos[pt1].first - 1, min(pos[pt1].second, pos[pt2].second), max(pos[pt1].second, pos[pt2].second));
			}
			qans = miny -> query(pos[pt1].first + 1, 100000, min(pos[pt1].second, pos[pt2].second), max(pos[pt1].second, pos[pt2].second));
			while (qans.first < pos[pt1].first) {
				miny -> update(pos[qans.second].first, pos[qans.second].second, ii(INF, -1)), maxy -> update(pos[qans.second].first, pos[qans.second].second, ii(0, -1));
				yf[qans.second] = -1;
				if (xf[qans.second] == -1) {
					printf("NE");
					return 0;
				} else despo.push(qans.second);
				qans = miny -> query(pos[pt1].first + 1, 100000, min(pos[pt1].second, pos[pt2].second), max(pos[pt1].second, pos[pt2].second));
			}
		} else {
			pt2 = yf[pt1];
			miny -> update(pos[pt1].first, pos[pt1].second, ii(INF, -1)), maxy -> update(pos[pt1].first, pos[pt1].second, ii(0, -1));
			miny -> update(pos[pt2].first, pos[pt2].second, ii(INF, -1)), maxy -> update(pos[pt2].first, pos[pt2].second, ii(0, -1));
			if (xf[pt2] != -1) {
				minx -> update(pos[pt2].first, pos[pt2].second, ii(INF, -1)), maxx -> update(pos[pt2].first, pos[pt2].second, ii(0, -1));
				minx -> update(pos[xf[pt2]].first, pos[xf[pt2]].second, ii(INF, -1)), maxx -> update(pos[xf[pt2]].first, pos[xf[pt2]].second, ii(0, -1));
				xf[xf[pt2]] = -1;
				if (yf[xf[pt2]] == -1) {
					printf("NE");
					return 0;
				} else despo.push(xf[pt2]);
			}
			ii qans = maxx -> query(min(pos[pt1].first, pos[pt2].first), max(pos[pt1].first, pos[pt2].first), 1, pos[pt1].second - 1);
			while (qans.first > pos[pt1].second) {
				minx -> update(pos[qans.second].first, pos[qans.second].second, ii(INF, -1)), maxx -> update(pos[qans.second].first, pos[qans.second].second, ii(0, -1));
				xf[qans.second] = -1;
				if (yf[qans.second] == -1) {
					printf("NE");
					return 0;
				} else despo.push(qans.second);
				qans = maxx -> query(min(pos[pt1].first, pos[pt2].first), max(pos[pt1].first, pos[pt2].first), 1, pos[pt1].second - 1);
			}
			qans = minx -> query(min(pos[pt1].first, pos[pt2].first), max(pos[pt1].first, pos[pt2].first), pos[pt1].second + 1, 100000);
			while (qans.first < pos[pt1].second) {
				minx -> update(pos[qans.second].first, pos[qans.second].second, ii(INF, -1)), maxx -> update(pos[qans.second].first, pos[qans.second].second, ii(0, -1));
				xf[qans.second] = -1;
				if (yf[qans.second] == -1) {
					printf("NE");
					return 0;
				} else despo.push(qans.second);
				qans = minx -> query(min(pos[pt1].first, pos[pt2].first), max(pos[pt1].first, pos[pt2].first), pos[pt1].second + 1, 100000);
			}
		}
		pairs.push_back(ii(pt1, pt2));
		settled[pt1] = settled[pt2] = true;
	}
	for (int i = 0; i < N; ++i) {
		if (!settled[i]) pairs.push_back(ii(i, xf[i])), settled[i] = settled[xf[i]] = true;
	}
	printf("DA\n");
	for (ii i: pairs) printf("%d %d\n", i.first + 1, i.second + 1);
}

Compilation message

matching.cpp: In function 'int main()':
matching.cpp:219:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &N);
  ~~~~~^~~~~~~~~~
matching.cpp:224:97: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for (int i = 0; i < N; ++i) scanf("%d %d", &pos[i].first, &pos[i].second), xy[i].first = pos[i], xy[i].second = i;
                              ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~
matching.cpp:248:7: warning: argument 1 range [18446744071562067968, 18446744073709551615] exceeds maximum object size 9223372036854775807 [-Walloc-size-larger-than=]
  bool settled[N];
       ^~~~~~~
matching.cpp:248:7: note: in a call to built-in allocation function 'void* __builtin_alloca_with_align(long unsigned int, long unsigned int)'

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct

Subtask #2
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 4 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 4 ms 256 KB Output is correct

Subtask #3
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 4 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 4 ms 256 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 5 ms 384 KB Output is correct
11 Correct 5 ms 384 KB Output is correct
12 Correct 5 ms 384 KB Output is correct

Subtask #4
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 4 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 4 ms 256 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 5 ms 384 KB Output is correct
11 Correct 5 ms 384 KB Output is correct
12 Correct 5 ms 384 KB Output is correct
13 Correct 39 ms 6444 KB Output is correct
14 Correct 40 ms 6520 KB Output is correct
15 Correct 44 ms 6520 KB Output is correct
16 Correct 40 ms 6392 KB Output is correct
17 Correct 41 ms 6392 KB Output is correct
18 Correct 37 ms 6520 KB Output is correct
19 Correct 39 ms 6520 KB Output is correct
20 Correct 35 ms 6392 KB Output is correct
21 Correct 34 ms 6392 KB Output is correct
22 Correct 34 ms 6400 KB Output is correct
23 Correct 64 ms 7800 KB Output is correct
24 Correct 66 ms 7800 KB Output is correct

Subtask #5
0 / 52.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 4 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 4 ms 256 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 5 ms 384 KB Output is correct
11 Correct 5 ms 384 KB Output is correct
12 Correct 5 ms 384 KB Output is correct
13 Correct 39 ms 6444 KB Output is correct
14 Correct 40 ms 6520 KB Output is correct
15 Correct 44 ms 6520 KB Output is correct
16 Correct 40 ms 6392 KB Output is correct
17 Correct 41 ms 6392 KB Output is correct
18 Correct 37 ms 6520 KB Output is correct
19 Correct 39 ms 6520 KB Output is correct
20 Correct 35 ms 6392 KB Output is correct
21 Correct 34 ms 6392 KB Output is correct
22 Correct 34 ms 6400 KB Output is correct
23 Correct 64 ms 7800 KB Output is correct
24 Correct 66 ms 7800 KB Output is correct
25 Execution timed out 2596 ms 291000 KB Time limit exceeded
26 Halted 0 ms 0 KB -