Íŕçŕä ę ëó÷řčě đĺřĺíč˙ě Status: AC, problem DIP, contest ZFUN07. By tanakh (Hideyuki Tanaka), 2007-04-26 23:01:19.
#include <cstdio>
#include <memory.h>
#include <algorithm>
using namespace std;
 
#define MAXH 200
#define MAXW 200
 
#define MERGIN 3
 
typedef int img[MAXH+MERGIN*2][MAXW+MERGIN*2];
 
#define at(bd,x,y) (bd[(y)+MERGIN][(x)+MERGIN])
 
int w,h,q;
 
void clear(img i,int v)
{
  for (int y=0;y<MAXH+MERGIN*2;y++)
    for (int x=0;x<MAXW+MERGIN*2;x++)
      i[y][x]=v;
}
void cp(img s,img d)
{
  memcpy(d,s,sizeof(img));
}
 
inline int median(int *buf,int n)
{
  if (n==0) return -1;
  if (n&1){
    int half=(n-1)/2;
    for (int i=0;i<=half;i++){
      int minv=buf[i],minj=i;
      for (int j=i+1;j<n;j++)
        if (buf[j]<minv)
          minv=buf[j],minj=j;
      swap(buf[i],buf[minj]);
    }
    return buf[half];
  }
  else{
    int half=n/2;
    for (int i=0;i<=half;i++){
      int minv=buf[i],minj=i;
      for (int j=i+1;j<n;j++)
        if (buf[j]<minv)
          minv=buf[j],minj=j;
      swap(buf[i],buf[minj]);
    }
    return (buf[half-1]+buf[half])/2;
  }
}
 
inline int ssort(int *buf,int n)
{
  for (int i=0;i<n-1;i++){
    int minv=buf[i],minj=i;
    for (int j=i+1;j<n;j++)
      if (buf[j]<minv)
        minv=buf[j],minj=j;
    swap(buf[i],buf[minj]);
  }
}
 
void solve(img bd,img out)
{
  static img org;
  cp(bd,org);
 
  const int thh=16,thl=32;
  for (int y=0;y<h;y++){
    for (int x=0;x<w-1;x++){
      if (abs(at(bd,x,y)-at(bd,x+1,y))>thh)
        continue;
      if (y<h-1&&abs(at(bd,x,y)-at(bd,x,y+1))<=thh)
        continue;
      if (y>=1&&abs(at(bd,x,y)-at(bd,x,y-1))<=thh)
        continue;
      if (y<h-1&&abs(at(bd,x+1,y)-at(bd,x,y+1))<=thh)
        continue;
      if (y>=1&&abs(at(bd,x+1,y)-at(bd,x,y-1))<=thh)
        continue;
      
      int base=(at(bd,x,y)+at(bd,x+1,y))/2;
      int len=2;
      int skip=0;
      int tx=x+2;
      while(skip<=2&&tx<w){
        if (abs(at(bd,tx,y)-base)<=thh)
          skip=0;
        else
          skip++;
        tx++;
        len++;
      }
      if (len>=thl){
        int b1=at(bd,x,y),b2=at(bd,x+1,y);
        for (int cx=x+2;cx<tx-skip;cx++){
          if (abs(at(bd,cx,y)-base)<=thh)
            b1=b2,b2=at(bd,cx,y);
          else
            at(bd,cx,y)=(b1+b2)/2;
        }
        x=tx-1;
      }
    }
  }
  for (int x=0;x<w;x++){
    for (int y=0;y<h-1;y++){
      if (abs(at(bd,x,y)-at(bd,x,y+1))>thh)
        continue;
      if (x<w-1&&abs(at(bd,x,y)-at(bd,x+1,y))<=thh)
        continue;
      if (x>=1&&abs(at(bd,x,y)-at(bd,x-1,y))<=thh)
        continue;
      if (x<w-1&&abs(at(bd,x,y+1)-at(bd,x+1,y))<=thh)
        continue;
      if (x>=1&&abs(at(bd,x,y+1)-at(bd,x-1,y))<=thh)
        continue;
      
      int base=(at(bd,x,y)+at(bd,x,y+1))/2;
      int len=2;
      int skip=0;
      int ty=y+2;
      while(skip<=2&&ty<h){
        if (abs(at(bd,x,ty)-base)<=thh)
          skip=0;
        else
          skip++;
        ty++;
        len++;
      }
      if (len>=thl){
        int b1=at(bd,x,y),b2=at(bd,x,y+1);
        for (int cy=y+2;cy<ty-skip;cy++){
          if (abs(at(bd,x,cy)-base)<=thh)
            b1=b2,b2=at(bd,x,cy);
          else
            at(bd,x,cy)=(b1+b2)/2;
        }
        y=ty-1;
      }
    }
  }
  /*
  if (0){
    for (int y=0;y<h;y++)
      for (int x=0;x<w;x++)
        if (at(bd,x,y)==at(org,x,y))
          at(out,x,y)=at(bd,x,y);
        else
          at(out,x,y)=256;
  }
  else
    cp(bd,out);
  return;
   */
  
  static img med;
 
  for (int y=0;y<h;y++){
    for (int x=0;x<w;x++){
      static const int vect[18]={0,0, 0,1,1,0, 0,-1,-1,0, 1,1,-1,-1,1,-1,-1,1};
      int tmp[9],tmpc=0;
      for (int i=0;i<5;i++)
        tmp[tmpc++]=at(bd,x+vect[i*2],y+vect[i*2+1]);
      at(med,x,y)=median(tmp,tmpc);
    }
  }
 
  for (int y=0;y<h;y++){
    for (int x=0;x<w;x++){
      int tmp[9],tmpc=0;
      for (int dx=-1;dx<=1;dx++)
        for (int dy=-1;dy<=1;dy++)
          if (!(dx==0&&dy==0)){
            int nx=x+dx,ny=y+dy;
            if (nx>=0&&nx<w&&ny>=0&&ny<h)
              tmp[tmpc++]=at(bd,x+dx,y+dy);
          }
      ssort(tmp,tmpc);
      int mdif=tmp[tmpc-1]-tmp[0];
 
      bool b=false;
      
      if (mdif<32&&abs(at(bd,x,y)-tmp[tmpc/2])>mdif)
        b=true;
      if (tmpc==9&&
          (tmp[tmpc-2]-tmp[0]<32||
           tmp[tmpc-1]-tmp[1]<32)&&
          abs(at(bd,x,y)-tmp[tmpc/2])>32)
        b=true;
 
      if (b)
        at(bd,x,y)=at(med,x,y);
    }
  }
 
  static img f;
  clear(f,0);
  for (int y=0;y<h;y++){
    for (int x=0;x<w;x++){
      static const int vect[8]={0,1,1,0,0,-1,-1,0};
      int cnt=0,cnt2=0,cnt3=0;
      for (int i=0;i<4;i++){
        int nx=x+vect[i*2];
        int ny=y+vect[i*2+1];
        if (!(nx>=0&&nx<w&&ny>=0&&ny<h))
          continue;
        int tmp=at(bd,x,y)-at(bd,nx,ny);
        if (tmp>=92) cnt++;
        if (tmp<=-92) cnt--;
        if (tmp>=64) cnt2++;
        if (tmp<=-64) cnt2--;
        cnt3++;
      }
      if (cnt>=cnt3-1||cnt<=-(cnt3-1)||cnt2==cnt3||cnt2==-cnt3)
        at(f,x,y)=1;
    }
  }
  for (int y=0;y<h;y++)
    for (int x=0;x<w;x++)
      if (at(f,x,y))
        at(bd,x,y)=at(med,x,y);
 
  static img err;
  static int lev[512];
  memset(lev,0,sizeof(lev));
  for (int y=0;y<h;y++){
    for (int x=0;x<w;x++){
      int minest=256;
      for (int i=0;i<4;i++){
        static const int vect[8]={0,1,1,0,0,-1,-1,0};
        int nx=x+vect[i*2];
        int ny=y+vect[i*2+1];
        int mx=x+vect[i*2]*2;
        int my=y+vect[i*2+1]*2;
        if (!(mx>=0&&mx<w&&my>=0&&my<h))
          continue;
        int nn=at(bd,nx,ny);
        int mm=at(bd,mx,my);
        int est=nn+(nn-mm);
        int eee=abs(at(bd,x,y)-est);
 
        minest<?=eee;
      }
      for (int i=0;i<4;i++){
        static const int vect[8]={0,1,1,0, 1,1,1,-1};
        int nx=x+vect[i*2];
        int ny=y+vect[i*2+1];
        int mx=x-vect[i*2];
        int my=y-vect[i*2+1];
        if (!(nx>=0&&nx<w&&ny>=0&&ny<h))
          continue;
        if (!(mx>=0&&mx<w&&my>=0&&my<h))
          continue;
        int nn=at(bd,nx,ny);
        int mm=at(bd,mx,my);
        int est=(nn+mm)/2;
        int eee=abs(at(bd,x,y)-est);
 
        minest<?=eee;
      }
      at(err,x,y)=minest;
      lev[at(err,x,y)]++;
    }
  }
 
  int found=0;
  for (int y=0;y<h;y++)
    for (int x=0;x<w;x++)
      if (at(bd,x,y)!=at(org,x,y))
        found++;
 
  int th=512;
  int es=(w*h*q-found)/325,acc=0;
  for (int i=511;i>=0;i--){
    if (acc<=es) th=i;
    acc+=lev[i];
  }
 
  for (int y=0;y<h;y++){
    for (int x=0;x<w;x++){
      if (at(err,x,y)>=th)
        at(bd,x,y)=at(med,x,y);
      else
        at(bd,x,y)=at(bd,x,y);
    }
  }
  cp(bd,org);
 
  for (int y=0;y<h;y++){
    for (int x=0;x<w;x++){
      int tmp[9],tmpc=0;
      for (int dy=-1;dy<=1;dy++)
        for (int dx=-1;dx<=1;dx++){
          int nx=x+dx,ny=y+dy;
          if (nx>=0&&nx<w&&ny>=0&&ny<h)
            tmp[tmpc++]=at(bd,x+dx,y+dy);
        }
      at(med,x,y)=median(tmp,tmpc);
    }
  }
 
  for (int y=0;y<h;y++){
    for (int x=0;x<w;x++){
      int tmp[9],tmpc=0;
      for (int dx=-1;dx<=1;dx++)
        for (int dy=-1;dy<=1;dy++)
          if (!(dx==0&&dy==0)){
            int nx=x+dx,ny=y+dy;
            if (nx>=0&&nx<w&&ny>=0&&ny<h)
              tmp[tmpc++]=at(bd,x+dx,y+dy);
          }
      ssort(tmp,tmpc);
      int mdif=tmp[tmpc-1]-tmp[0];
 
      bool b=false;
      
      if (mdif<32&&abs(at(bd,x,y)-tmp[tmpc/2])>mdif)
        b=true;
      if ((tmp[tmpc-2]-tmp[0]<32||
           tmp[tmpc-1]-tmp[1]<32)&&
          abs(at(bd,x,y)-tmp[tmpc/2])>32)
        b=true;
 
      if (b){
        at(bd,x,y)=at(med,x,y);
        found++;
      }
    }
  }
 
  if (0){
    for (int y=0;y<h;y++)
      for (int x=0;x<w;x++)
        if (at(bd,x,y)==at(org,x,y))
          at(out,x,y)=at(bd,x,y);
        else
          at(out,x,y)=256;
  }
  else
    cp(bd,out);
}
 
int main()
{
  int cases;scanf("%d",&cases);
  while(cases--){
    scanf("%d%d%d",&q,&h,&w);
 
    static img bd;clear(bd,0);
    for (int y=0;y<h;y++)
      for (int x=0;x<w;x++)
        scanf("%d",&at(bd,x,y));
 
    img out;
    solve(bd,out);
 
    printf("%d %d\n",h,w);
    for (int y=0;y<h;y++){
      for (int x=0;x<w;x++)
        printf(" %03d",at(out,x,y));
      puts("");
    }
  }
  return 0;
}