THUPC 2022 初赛 J 求助
  • 板块学术版
  • 楼主IYSY2009I
  • 当前回复4
  • 已保存回复4
  • 发布时间2022/3/12 16:05
  • 上次更新2023/10/28 06:46:10
查看原帖
THUPC 2022 初赛 J 求助
449457
IYSY2009I楼主2022/3/12 16:05

RT,样例都过不去

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int read(){
	int x=0,f=1;
	char c=getchar();
	while(c<'0'||c>'9'){
		if(c=='-') f=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9'){
		x=(x<<1)+(x<<3)+c-'0';
		c=getchar();
	}
	return x*f;
}
struct edge{
	int lx;
	int ly;
	int rx;
	int ry;
	int op;
};
edge a[100005];
edge h[100005];
edge w[100005];
bool cmp(edge x,edge y){
	if(x.op!=y.op) return x.op<y.op;
	if(x.op==0){
		if(x.lx!=y.lx) return x.lx<y.lx;
		return x.rx<y.rx;
	}
	if(x.op==1){
		if(x.ly!=y.ly) return x.ly<y.ly;
		return x.ry<y.ry;
	}
}
int _min(int x,int y){
	if(x<y) return x;
	return y;
}
int _max(int x,int y){
	if(x<y) return y;
	return x;
}
int main(){
	int n=read();
	for(int i=1;i<=n;i++){
		int op=read();
		if(!op){
			a[i].op=0;
			int l=read(),r=read(),y=read();
			if(l>r) swap(l,r);
			a[i].lx=l;
			a[i].ly=y;
			a[i].rx=r;
			a[i].ry=y;
		}
		if(op){
			a[i].op=1;
			int d=read(),u=read(),x=read();
			if(d>u) swap(d,u);
			a[i].lx=x;
			a[i].ly=d;
			a[i].rx=x;
			a[i].ry=u;
		}
	}
	sort(a+1,a+n+1,cmp);
	int hcnt=0,wcnt=0;
	cout<<endl;
	for(int i=2;i<=n;i++){
		if(a[i-1].op!=a[i].op){
			if(a[i-1].op){
				wcnt++;
				w[wcnt]=a[i-1];
			}
			if(!a[i-1].op){
				hcnt++;
				h[hcnt]=a[i-1];
			}
			continue;
		}
		if(!a[i].op){
			if(a[i].ly!=a[i-1].ly||a[i-1].rx<a[i].lx){
				hcnt++;
				h[hcnt]=a[i-1];
				continue;
			}
			a[i].lx=_min(a[i-1].lx,a[i].lx);
			a[i].rx=_max(a[i-1].rx,a[i].rx);
		}
		if(a[i].op){
			if(a[i].lx!=a[i-1].lx||a[i-1].ry<a[i].ly){
				wcnt++;
				w[wcnt]=a[i-1];
				continue;
			}
			a[i].ly=_min(a[i-1].ly,a[i].ly);
			a[i].ry=_max(a[i-1].ry,a[i].ry);
		}
	}
	if(a[n].op){
		wcnt++;
		w[wcnt]=a[n];
	}
	if(!a[n].op){
		hcnt++;
		h[hcnt]=a[n];
	}
	if(hcnt!=7||wcnt!=8){
		printf("No");
		return 0;
	}
	sort(h+1,h+8,cmp);
	sort(w+1,w+9,cmp);
	do{
		do{
			if(!(w[1].ly<h[1].ly&&h[1].ly==w[1].ry&&h[1].lx<w[1].lx&&w[1].lx<h[1].rx)) continue;
			if(!(w[2].ly==w[3].ly&&w[2].ly<h[2].ly&&h[2].ly<w[3].ry&&w[3].ry==w[2].ry&&w[2].lx==h[2].lx&&h[2].rx==w[3].lx)) continue;
			if(!(w[4].ly==w[5].ly&&w[4].ly==h[3].ly&&h[3].ly<w[6].ry&w[5].ry==w[4].ry&&w[4].lx==h[3].lx&&h[3].rx==w[5].lx)) continue;//6->w4,7->h3,8->w5 
			if(!(w[6].ly<h[5].ly&&h[5].ly==w[7].ly&&w[7].ly<w[6].ry&&w[6].ry==h[4].ry&&h[4].ly==w[7].ry&&w[6].lx==h[4].lx&&h[4].lx==h[5].lx&&h[5].lx<h[4].rx&&h[4].rx==h[5].rx&&h[5].rx==w[7].lx)) continue; //9->w6,10->h4,11->h5,12->w7
			if(!(w[8].ly==h[7].ly&&h[7].ly<w[8].ry&&w[8].ry==h[6].ly&&w[8].lx==h[6].lx&&h[6].lx==h[7].lx&&h[7].lx<h[6].rx&&h[6].rx==h[7].rx)) continue;
			printf("Yes");
			return 0;
		}while(next_permutation(h+1,h+8,cmp));
		sort(h+1,h+8,cmp);
	}while(next_permutation(w+1,w+9,cmp));
	printf("No");
	return 0;
}
2022/3/12 16:05
加载中...