結果

問題 No.5002 stick xor
ユーザー akakimidoriakakimidori
提出日時 2018-05-26 04:53:13
言語 C90
(gcc 11.4.0)
結果
WA  
実行時間 -
コード長 2,244 bytes
コンパイル時間 2,596 ms
実行使用メモリ 956 KB
スコア 0
最終ジャッジ日時 2018-05-26 04:53:19
ジャッジサーバーID
（参考情報） 		judge9 /
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 WA -
testcase_01 WA -
testcase_02 WA -
testcase_03 WA -
testcase_04 WA -
testcase_05 WA -
testcase_06 WA -
testcase_07 WA -
testcase_08 WA -
testcase_09 WA -
testcase_10 WA -
testcase_11 WA -
testcase_12 WA -
testcase_13 WA -
testcase_14 WA -
testcase_15 WA -
testcase_16 WA -
testcase_17 WA -
testcase_18 WA -
testcase_19 WA -
testcase_20 WA -
testcase_21 WA -
testcase_22 WA -
testcase_23 WA -
testcase_24 WA -
testcase_25 WA -
testcase_26 WA -
testcase_27 WA -
testcase_28 WA -
testcase_29 WA -
testcase_30 WA -
testcase_31 WA -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<stdio.h>
#include<stdlib.h>
#include<math.h>

typedef long long int int64;

#define MAX(a,b) ((a)>(b)?(a):(b))
#define MIN(a,b) ((a)<(b)?(a):(b))
#define ABS(a) ((a)>(0)?(a):-(a))

#define POS(i,j) ((i)*(n+1)+(j))

typedef struct length{
  int l;
  int index;
} len;

int cmp(const void *a,const void *b){
  return ((len *)a)->l-((len *)b)->l;
}

void flip(int l,char *s,int n,int a,int b,int dir){
  const int t='0'^'1';
  if(dir){
    int i;
    for(i=0;i<l;i++){
      int index=POS(a,b+i);
      s[index]=(char)(s[index]^t);
    }
  } else {
    int i;
    for(i=0;i<l;i++){
      int index=POS(a+i,b);
      s[index]=(char)(s[index]^t);
    }
  }
  return;
}

void func(int l,char *s,const int n,int *a){
  int max=-l-1;
  int i,j,k;
  for(i=0;i<n-l+1;i++){
    for(j=0;j<n;j++){
      int c=0;
      for(k=0;k<l;k++){
	c+=(s[POS(i+k,j)]=='0'?-1:1);
      }
      if(c>max){
	max=c;
	a[0]=i;
	a[1]=j;
	a[2]=i+l-1;
	a[3]=j;
      }
    }
  }
  for(i=0;i<n;i++){
    for(j=0;j<n-l+1;j++){
      int c=0;
      for(k=0;k<l;k++){
	c+=(s[POS(i,j+k)]=='0'?-1:1);
      }
      if(c>max){
	max=c;
	a[0]=i;
	a[1]=j;
	a[2]=i;
	a[3]=j+l-1;
      }
    }
  }
  flip(l,s,n,a[0],a[1],a[0]==a[2]);
  return;
}

void run(void){
  int n,k;
  scanf("%d%d",&n,&k);
  char *s=(char *)calloc((n+1)*n,sizeof(char));
  len *array=(len *)malloc(sizeof(len)*k);
  int *ans=(int *)malloc(sizeof(int)*4*k);
  int i;
  for(i=0;i<k;i++){
    int t;
    scanf("%d",&t);
    array[i].l=t;
    array[i].index=i;
  }
  qsort(array,k,sizeof(len),cmp);
  for(i=0;i<n;i++) scanf("%s",s+POS(i,0));

  const int parameter=4;
  for(i=0;i<n && array[i].l>=parameter;i++){
    int l=array[i].l;
    int index=array[i].index;
    func(l,s,n,ans+4*index);
  }

  int iter=15;
  while(iter--){
    for(i=0;i<n && array[i].l>=parameter;i++){
      int l=array[i].l;
      int index=array[i].index;
      flip(l,s,n,ans[4*index],ans[4*index+1],ans[4*index]==ans[4*index+2]);
      func(l,s,n,ans+4*index);
    }
  }
  for(;i<n;i++){
    int l=array[i].l;
    int index=array[i].index;
    func(l,s,n,ans+4*index);
  }

  for(i=0;i<k;i++){
    printf("%d %d %d %d\n",ans[i*4+0]+1,ans[i*4+1]+1,ans[i*4+2]+1,ans[i*4+3]+1);
  }
  return;
}

int main(void){
  run();
  return 0;
}
0