QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#403051 | #6746. Merge the Rectangles | altaires1 | WA | 52ms | 6428kb | C++14 | 2.8kb | 2024-05-01 19:58:19 | 2024-05-01 19:58:20 |
Judging History
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';
}
}
详细
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