QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#403051#6746. Merge the Rectanglesaltaires1WA 52ms6428kbC++142.8kb2024-05-01 19:58:192024-05-01 19:58:20

Judging History

你现在查看的是最新测评结果

  • [2024-05-01 19:58:20]
  • 评测
  • 测评结果:WA
  • 用时:52ms
  • 内存:6428kb
  • [2024-05-01 19:58:19]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;

const int maxn=1600;

set<pair<int,int>> shu[maxn];
set<pair<int,int>> heng[maxn];

string zifu[maxn];

int main(){
	//freopen("5.txt","r",stdin);
	//freopen("144.out","w",stdout);
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n-1;i++){
		string s;
		cin>>s;
		s=' '+s;
		pair<int,int> temp={-1,-1};
		for(int j=1;j<=m;j++){
			if(s[j]=='1'){
				if(temp.first==-1){
					temp={j,j};
				}
				else{
					temp.first=j;
				}
			}
			else{
				if(temp.first!=-1){
					heng[i].insert(temp);
				}
				temp.first=-1;
			}
			if(j==m){
				if(temp.first!=-1){
					heng[i].insert(temp);
				}
			}
		}
	}
	for(int i=1;i<=n;i++){
		string temp;
		cin>>temp;
		zifu[i]=' '+temp;
	}
	for(int j=1;j<=m-1;j++){
		pair<int,int> temp={-1,-1};
		for(int i=1;i<=n;i++){
			if(zifu[i][j]=='1'){
				if(temp.first==-1){
					temp={i,i};
				}
				else{
					temp.first=i;
				}
			}
			else{
				if(temp.first!=-1){
					shu[j].insert(temp);
				}
				temp.first=-1;
			}
			if(i==n){
				if(temp.first!=-1){
					shu[j].insert(temp);
				}
			}
		}
	}
	int judge=0;

	for(int j=1;j<=m-1;j++){
		for(auto it : shu[j]){ //找到这样一条线段
			int down=it.first;
			auto iter=heng[down].lower_bound({j+1,0});
			if(iter==heng[down].end()){
				continue;
			}
			if(it.second>j){
				continue;
			}
			int right=it.first;
			iter=shu[right].lower_bound({down+1,0});
			if(iter==shu[right].end()){
				continue;
			}
			if(iter->second>down){
				continue;
			}
			int up=iter->second;
			if(up<=it.second){
				continue;
			}
			up--;
			iter=heng[up].lower_bound({right+1,0});
			int left=iter->second;
			if(left!=j+1){
				continue;
			}
			judge=1;
		}
	}
	for(int i=1;i<=n-1;i++){
		vector<pair<int,int>> chucun;
		for(auto temp : heng[i]){
			int l=temp.second;
			int r=temp.first;
			l=m+1-l;
			r=m+1-r;
			chucun.push_back({l,r});
		}
		heng[i].clear();
		for(auto temp:chucun){
			heng[i].insert(temp);
		}
	}
	for(int j=1;j<=(m-1)/2;j++){
		swap(shu[j],shu[m-j]);
	}
	for(int j=1;j<=m-1;j++){
		for(auto it : shu[j]){ //找到这样一条线段
			int down=it.first;
			auto iter=heng[down].lower_bound({j+1,0});
			if(iter==heng[down].end()){
				continue;
			}
			if(it.second>j){
				continue;
			}
			int right=it.first;
			iter=shu[right].lower_bound({down+1,0});
			if(iter==shu[right].end()){
				continue;
			}
			if(iter->second>down){
				continue;
			}
			int up=iter->second;
			if(up<=it.second){
				continue;
			}
			up--;
			iter=heng[up].lower_bound({right+1,0});
			int left=iter->second;
			if(left!=j+1){
				continue;
			}
			judge=1;
		}
	}
	if(judge==0){
		cout<<"YES"<<'\n';
	}
	else{
		cout<<"NO"<<'\n';
	}
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3964kb

input:

3 4
0000
0111
101
101
110

output:

YES

result:

ok answer is YES

Test #2:

score: 0
Accepted
time: 1ms
memory: 3936kb

input:

3 3
110
011
01
11
10

output:

NO

result:

ok answer is NO

Test #3:

score: 0
Accepted
time: 47ms
memory: 5956kb

input:

1500 1500
00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

YES

result:

ok answer is YES

Test #4:

score: 0
Accepted
time: 43ms
memory: 6096kb

input:

1500 1500
11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

output:

YES

result:

ok answer is YES

Test #5:

score: 0
Accepted
time: 46ms
memory: 6028kb

input:

1500 1500
11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

output:

YES

result:

ok answer is YES

Test #6:

score: 0
Accepted
time: 52ms
memory: 6036kb

input:

1500 1500
00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

YES

result:

ok answer is YES

Test #7:

score: 0
Accepted
time: 51ms
memory: 6100kb

input:

1500 1500
11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

output:

NO

result:

ok answer is NO

Test #8:

score: 0
Accepted
time: 51ms
memory: 6092kb

input:

1500 1500
11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

output:

NO

result:

ok answer is NO

Test #9:

score: 0
Accepted
time: 43ms
memory: 6100kb

input:

1500 1500
11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

output:

NO

result:

ok answer is NO

Test #10:

score: 0
Accepted
time: 49ms
memory: 6428kb

input:

1500 1500
11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

output:

YES

result:

ok answer is YES

Test #11:

score: -100
Wrong Answer
time: 51ms
memory: 6180kb

input:

1500 1500
11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

output:

NO

result:

wrong answer expected YES, found NO