#include<iostream>
#include<string.h>
#include<cstdlib>
#include<cstdio>
using namespace std;
void jh(int &a2,int &b2) {int c2;c2=a2;a2=b2;b2=c2;}
int main() {
int aa,ab,ba,bb,n;
cin>>aa>>ab>>ba>>bb>>n;
int x[n+10][4],y[n+10][4];
memset(x,0,sizeof(x));
memset(y,0,sizeof(y));
for(int i=1;i<=n;i++) {
for(int j=1;j<=4;j++) {
cin>>x[i][j];
}
}
for(int i=1;i<=n;i++) {
if(x[i][1]>x[i][3])jh(x[i][1],x[i][3]);
if(x[i][2]>x[i][4])jh(x[i][2],x[i][4]);
}
int ls[3000],hs[3000];
memset(ls,0,sizeof(ls));
memset(hs,0,sizeof(hs));
int lx,hx,l[3000],h[3000];
lx=1;hx=1;
for(int i=1;i<=n;i++) {
if(x[i][2]==x[i][4]) {
if(ls[x[i][1]]==0) {
l[lx]=x[i][1];
lx++;
}
ls[x[i][1]]++;
}
else {
if(hs[x[i][2]]==0) {
h[hx]=x[i][2];
hx++;
}
hs[x[i][2]]++;
}
}
int c1,j1,c2,j2,c11,j11,c12,j12;
for(int i1=1;i1<lx;i1++) {
c1=ls[l[i1]];
j1=i1-1;
while(j1>=0&&ls[l[j1]]>c1) {
ls[l[j1+1]]=ls[l[j1]];
j1--;
}
ls[l[j1+1]]=c1;
}
for(int i2=1;i2<hx;i2++) {
c2=hs[h[i2]];
j2=i2-1;
while(j1>=0&&hs[h[j2]]>c2) {
hs[h[j2+1]]=hs[h[j2]];
j2--;
}
hs[h[j2+1]]=c2;
}
for(int i11=1;i11<lx;i11++) {
c11=l[i11];
j11=i11-1;
while(j11>=0&&l[j11]>c11) {
l[j11+1]=l[j11];
j11--;
}
l[j11+1]=c11;
}
for(int i12=1;i12<hx;i12++) {
c12=h[i12];
j12=i12-1;
while(j11>=0&&h[j11]>c2) {
h[j12+1]=h[j12];
j12--;
}
h[j12+1]=c12;
}
for(int i=1;i<=ba;i++)cout<<l[i]<<" ";
cout<<endl;
for(int i=1;i<=bb;i++)cout<<h[i]<<" ";
return 0;
}
by chensj @ 2018-07-19 12:02:43
```cpp
#include<iostream>
#include<string.h>
#include<cstdlib>
#include<cstdio>
using namespace std;
void jh(int &a2,int &b2) {int c2;c2=a2;a2=b2;b2=c2;}
int main() {
int aa,ab,ba,bb,n;
cin>>aa>>ab>>ba>>bb>>n;
int x[n+10][4],y[n+10][4];
memset(x,0,sizeof(x));
memset(y,0,sizeof(y));
for(int i=1;i<=n;i++) {
for(int j=1;j<=4;j++) {
cin>>x[i][j];
}
}
for(int i=1;i<=n;i++) {
if(x[i][1]>x[i][3])jh(x[i][1],x[i][3]);
if(x[i][2]>x[i][4])jh(x[i][2],x[i][4]);
}
int ls[3000],hs[3000];
memset(ls,0,sizeof(ls));
memset(hs,0,sizeof(hs));
int lx,hx,l[3000],h[3000];
lx=1;hx=1;
for(int i=1;i<=n;i++) {
if(x[i][2]==x[i][4]) {
if(ls[x[i][1]]==0) {
l[lx]=x[i][1];
lx++;
}
ls[x[i][1]]++;
}
else {
if(hs[x[i][2]]==0) {
h[hx]=x[i][2];
hx++;
}
hs[x[i][2]]++;
}
}
int c1,j1,c2,j2,c11,j11,c12,j12;
for(int i1=1;i1<lx;i1++) {
c1=ls[l[i1]];
j1=i1-1;
while(j1>=0&&ls[l[j1]]>c1) {
ls[l[j1+1]]=ls[l[j1]];
j1--;
}
ls[l[j1+1]]=c1;
}
for(int i2=1;i2<hx;i2++) {
c2=hs[h[i2]];
j2=i2-1;
while(j1>=0&&hs[h[j2]]>c2) {
hs[h[j2+1]]=hs[h[j2]];
j2--;
}
hs[h[j2+1]]=c2;
}
for(int i11=1;i11<lx;i11++) {
c11=l[i11];
j11=i11-1;
while(j11>=0&&l[j11]>c11) {
l[j11+1]=l[j11];
j11--;
}
l[j11+1]=c11;
}
for(int i12=1;i12<hx;i12++) {
c12=h[i12];
j12=i12-1;
while(j11>=0&&h[j11]>c2) {
h[j12+1]=h[j12];
j12--;
}
h[j12+1]=c12;
}
for(int i=1;i<=ba;i++)cout<<l[i]<<" ";
cout<<endl;
for(int i=1;i<=bb;i++)cout<<h[i]<<" ";
return 0;
}
```
by chensj @ 2018-07-19 12:05:00
有必要那么麻烦吗……
Mine:
https://createsj.blog.luogu.org/solution-p1056
by Createsj @ 2018-07-19 12:29:36
老师不让我们用统排
by chensj @ 2018-07-19 12:31:56
@[创世菌](/space/show?uid=76717) 我是个新手......你的题解我看不懂,只看懂了一半
by chensj @ 2018-07-19 12:34:01
……
by Createsj @ 2018-07-19 13:21:12
@[csj2223829207](/space/show?uid=104198) 不用排序怎么做?
by Createsj @ 2018-07-19 13:22:04
只需要得到隔开交头接耳的同学最多的 k 条横向的通道和 l 条纵向的通道就可以了。
by Createsj @ 2018-07-19 13:22:51
@[创世菌](/space/show?uid=76717) 不是不用排序
是不用系统提供的函数排
是用那些插入,选择,快速,冒泡排序做的
by chensj @ 2018-07-19 16:03:37
@[csj2223829207](/space/show?uid=104198) 那就用冒泡呗~
by Createsj @ 2018-07-19 16:58:43