吐槽:t1数据有些水了
瞎搞的勾史模拟,能过大样例,过不了自己造的数据
#include<stdio.h> #include<string.h> #include<algorithm> using namespace std; typedef long long ll; const ll Maxn=1e2; ll t,n,m; struct Node{ll b[Maxn+10];}a[Maxn+10]; ll now_l; bool cmp(Node x,Node y){return x.b[now_l]<y.b[now_l];} ll max(ll x,ll y){return x>y?x:y;} ll min(ll x,ll y){return x<y?x:y;} bool slove(ll l,ll r,ll now_d){ if(l==r||now_d==m) return true; now_l=now_d; sort(a+l,a+1+r,cmp); ll max1,min1,max2,min2,max3,min3,kk,l1=0,l2=0,l3=0; max1=max2=max3=0ll; min1=min2=min3=4ll; for(ll i=l;i<=r;i++){ kk=a[i].b[now_d+1]; if(a[i].b[now_d]==1) max1=max(max1,kk),min1=min(min1,kk); if(a[i].b[now_d]==2) max2=max(max2,kk),min2=min(min2,kk); if(a[i].b[now_d]==3) max3=max(max3,kk),min3=min(min3,kk); if(a[i].b[now_d]==1&&a[i-1].b[now_d]!=1) l1=i; if(a[i].b[now_d]==2&&a[i-1].b[now_d]!=2) l2=i; if(a[i].b[now_d]==3&&a[i-1].b[now_d]!=3) l3=i; } if(max1>0){ if(min2<4) if(max1>min2) return false; if(min3<4) if(max1>min3) return false; } if(max2>0&&min3<4) if(max2>min3) return false; bool f1=true,f2=true,f3=true; if(l1!=0){ if(l2!=0) f1=slove(l1,l2-1,now_d+1); else if(l3!=0) f1=slove(l1,l3-1,now_d+1); else f1=slove(l1,r,now_d+1); } if(l2!=0){ if(l1==0) f1=slove(l,l2-1,now_d+1); if(l3!=0) f2=slove(l2,l3-1,now_d+1); else f2=slove(l2,r,now_d+1); } if(l3!=0) f3=slove(l3,r,now_d+1); return f1&&f2&&f3; } int main(){ // freopen("t1.in","r",stdin); // freopen("jzjh.out","w",stdout); scanf("%lld",&t); for(ll i0=1;i0<=t;i0++){ scanf("%lld%lld",&n,&m); for(ll i=1;i<=n;i++) for(ll i1=1;i1<=m;i1++) scanf("%lld",&a[i].b[i1]); // for(ll i=1;i<=n;i++){ // for(ll i1=1;i1<=m;i1++) // printf("%lld ",a[i].b[i1]); // printf("\n"); // } if(slove(1,n,1)) printf("YES\n"); else printf("NO\n"); for(ll i=1;i<=n;i++) for(ll i1=1;i1<=m;i1++) a[i].b[i1]=0; now_l=n=m=0; } }
1
5 3
3 3 2
3 3 1
3 3 3
1 2 3
1 2 1
这组数据显然输出NO,但是
全部评论
(1) 回帖