关于刚刚结束的 THUPC J(大模拟)
  • 板块灌水区
  • 楼主donghanwen1225
  • 当前回复9
  • 已保存回复9
  • 发布时间2022/3/12 16:06
  • 上次更新2023/10/28 06:46:09
查看原帖
关于刚刚结束的 THUPC J(大模拟)
153687
donghanwen1225楼主2022/3/12 16:06

RT,孩子调了 2h 没整出来

最后盯着代码看了 1h 也没发现什么错误。求问,这题是有什么隐蔽的细节吗?

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int n,ok=1,cnt1,cnt2,e1,e2,bj1[21],bj2[21];
struct seg
{
	int l,r,x;
} s1[1000001],s2[1000001],n1[1000001],n2[1000001];
bool cmpp(seg a1,seg a2){return a1.x<a2.x;}
bool cmp(seg a1,seg a2){return a1.l<a2.l;}
bool check(int op1,seg s1,int op2,seg s2)
{
	// s1 是纵向线段,s2 是横向线段 
	if(s1.x<s2.l||s1.x>s2.r) return 0;
	if(s2.x<s1.l||s2.x>s1.r) return 0;
	return 1;
}
void findt()
{
	if(!ok) return;
	for(int i=1;i<=7;i++)
		for(int j=1;j<=8;j++)
			if(n2[j].r==n1[i].x&&n1[i].l<n2[j].x&&n1[i].r>n2[j].x)
			{
				int flag=1;
				for(int ii=1;ii<=7;ii++)
					if(ii!=i)
						if(check(2,n2[j],1,n1[ii])){flag=0;break;}
				for(int ii=1;ii<=8;ii++)
					if(ii!=j)
						if(check(2,n2[ii],1,n1[i])){flag=0;break;}
				if(flag){bj1[i]=1;bj2[j]=1;return;}
			}
	ok=0;
//	printf("#1\n");
}
void findh()
{
	if(!ok) return;
	for(int i=1;i<=7;i++)
		for(int j1=1;j1<=8;j1++)
			for(int j2=1;j2<=8;j2++)
			{
				if(bj1[i]||bj2[j1]||bj2[j2]) continue;
				if(j1==j2) continue;
				if(n2[j1].l!=n2[j2].l||n2[j1].r!=n2[j2].r||n2[j1].x==n2[j2].x) continue;
				if(n1[i].l==min(n2[j1].x,n2[j2].x)&&n1[i].r==max(n2[j1].x,n2[j2].x)&&n2[j1].l<n1[i].x&&n1[i].x<n2[j1].r)
				{
					int flag=1;
					for(int ii=1;ii<=7;ii++)
						if(ii!=i)
							if(check(2,n2[j1],1,n1[ii])||check(2,n2[j2],1,n1[ii])){flag=0;break;}
					for(int ii=1;ii<=8;ii++)
						if(ii!=j1&&ii!=j2)
							if(check(2,n2[ii],1,n1[i])){flag=0;break;}
					if(flag){bj1[i]=1;bj2[j1]=1;bj2[j2]=1;return;}
				}
			}
	ok=0;
//	printf("#2\n");
}
void findu()
{
	if(!ok) return;
	for(int i=1;i<=7;i++)
		for(int j1=1;j1<=8;j1++)
			for(int j2=1;j2<=8;j2++)
			{
				if(bj1[i]||bj2[j1]||bj2[j2]) continue;
				if(j1==j2) continue;
				if(n2[j1].l!=n2[j2].l||n2[j1].r!=n2[j2].r||n2[j1].x==n2[j2].x) continue;
				if(n1[i].l==min(n2[j1].x,n2[j2].x)&&n1[i].r==max(n2[j1].x,n2[j2].x)&&n2[j1].l==n1[i].x)
				{
					int flag=1;
					for(int ii=1;ii<=7;ii++)
						if(ii!=i)
							if(check(2,n2[j1],1,n1[ii])||check(2,n2[j2],1,n1[ii])){flag=0;break;}
					for(int ii=1;ii<=8;ii++)
						if(ii!=j1&&ii!=j2)
							if(check(2,n2[ii],1,n1[i])){flag=0;break;}
					if(flag){bj1[i]=1;bj2[j1]=1;bj2[j2]=1;return;}
				}
			}
	ok=0;
//	printf("#3\n");
}
void findc()
{
	if(!ok) return;
	for(int i1=1;i1<=7;i1++)
		for(int i2=1;i2<=7;i2++)
			for(int j=1;j<=8;j++)
			{
				if(bj1[i1]||bj1[i2]||bj2[j]) continue;
				if(i1==i2) continue;
				if(n1[i1].l!=n1[i2].l||n1[i1].r!=n1[i2].r||n1[i1].x==n1[i2].x) continue;
				if(n2[j].l==min(n1[i1].x,n1[i2].x)&&n2[j].r==max(n1[i1].x,n1[i2].x)&&n1[i1].l==n2[j].x)
				{
					int flag=1;
					for(int ii=1;ii<=7;ii++)
						if(ii!=i1&&ii!=i2)
							if(check(2,n2[j],1,n1[ii])){flag=0;break;}
					for(int ii=1;ii<=8;ii++)
						if(ii!=j)
							if(check(2,n2[ii],1,n1[i1])||check(2,n2[ii],1,n1[i2])){flag=0;break;}
					if(flag){bj1[i1]=1;bj1[i2]=1;bj2[j]=1;return;}
				}
			}
	ok=0;
//	printf("#4\n");
}
void findp()
{
	if(!ok) return;
	for(int i1=1;i1<=7;i1++)
		for(int i2=1;i2<=7;i2++)
			for(int j1=1;j1<=8;j1++)
				for(int j2=1;j2<=8;j2++)
				{
					if(bj1[i1]||bj1[i2]||bj2[j1]||bj2[j2]) continue;
					if(i1==i2||j1==j2) continue;
					if(n1[i1].l!=n1[i2].l||n1[i1].r!=n1[i2].r||n1[i1].x==n1[i2].x) continue;
					if(n2[j1].r!=n2[j2].r||n2[j1].l==n2[j2].l||n2[j1].x==n2[j2].x) continue;
					if(min(n2[j1].x,n2[j2].x)==n1[i1].l&&max(n2[j1].x,n2[j2].x)==n1[i1].r&&max(n1[i1].x,n1[i2].x)==n2[j1].r)
					{
						seg S1=n1[i1],S2=n1[i2],S3=n2[j1],S4=n2[j2];
						if(S1.x>S2.x) swap(S1,S2);
						if(S3.x>S4.x) swap(S3,S4);
						if(S3.l<S4.l&&S1.x==S4.l)
						{
							int flag=1;
							for(int ii=1;ii<=7;ii++)
								if(ii!=i1&&ii!=i2)
									if(check(2,n2[j1],1,n1[ii])||check(2,n2[j2],1,n1[ii])){flag=0;break;}
							for(int ii=1;ii<=8;ii++)
								if(ii!=j1&&ii!=j2)
									if(check(2,n2[ii],1,n1[i1])||check(2,n2[ii],1,n1[i2])){flag=0;break;}
							if(flag){bj1[i1]=1;bj1[i2]=1;bj2[j1]=1;bj2[j2]=1;return;}
						}
					}
				}
	ok=0;
}
int main()
{
	ios::sync_with_stdio(false);
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		int op,l,r,x;
		cin>>op>>l>>r>>x;
		if(op==0) s1[++cnt1]={l,r,x};
		else s2[++cnt2]={l,r,x};
	}
	sort(s1+1,s1+1+cnt1,cmpp);sort(s2+1,s2+1+cnt2,cmpp);
	for(int l=1,r=1;r<=cnt1;l=r+1)
	{
		r=l;
		while(s1[r+1].x==s1[l].x&&r+1<=cnt1) r++;
		sort(s1+l,s1+1+r,cmp);
		seg cur=s1[l];
		for(int j=l+1;j<=r;j++)
		{
			if(s1[j].l<=cur.r)
				cur.r=s1[j].r;
			else
			{
				n1[++e1]=cur;
				cur=s1[j];
			}
		}
		n1[++e1]=cur;
		if(r==cnt1) break;
	}
	for(int l=1,r=1;r<=cnt2;l=r+1)
	{
		r=l;
		while(s2[r+1].x==s2[l].x&&r+1<=cnt2) r++;
		sort(s2+l,s2+1+r,cmp);
		seg cur=s2[l];
		for(int j=l+1;j<=r;j++)
		{
			if(s2[j].l<=cur.r)
				cur.r=s2[j].r;
			else
			{
				n2[++e2]=cur;
				cur=s2[j];
			}
		}
		n2[++e2]=cur;
		if(r==cnt2) break;
	}
	if(e1!=7||e2!=8) ok=0;
	findc();findp();findu();findh();findt();
	cout<<(ok==1?"Yes":"No");
	return 0;
}
/*
17
0 1 2 100
0 1 2 -100
0 2 9 90
1 75 90 5
1 65 70 4
1 65 70 6
0 4 6 68
1 50 60 8
1 50 60 20
0 8 20 50
1 52 58 12
1 54 58 16
0 12 16 58
0 12 16 54
1 -100 -99 1
1 -99 -89 1
1 -95 100 1
*/
2022/3/12 16:06
加载中...