結果

問題 No.5002 stick xor
ユーザー akakimidoriakakimidori
提出日時 2018-05-31 01:20:09
言語 C90
(gcc 11.4.0)
結果
AC  
実行時間 788 ms / 1,000 ms
コード長 6,506 bytes
コンパイル時間 26,356 ms
実行使用メモリ 956 KB
スコア 46,361
最終ジャッジ日時 2018-05-31 01:20:37
ジャッジサーバーID
（参考情報） 		judge7 /
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 726 ms
956 KB
testcase_01 AC 691 ms
952 KB
testcase_02 AC 757 ms
952 KB
testcase_03 AC 752 ms
956 KB
testcase_04 AC 740 ms
956 KB
testcase_05 AC 734 ms
952 KB
testcase_06 AC 732 ms
952 KB
testcase_07 AC 766 ms
956 KB
testcase_08 AC 763 ms
956 KB
testcase_09 AC 750 ms
956 KB
testcase_10 AC 738 ms
956 KB
testcase_11 AC 760 ms
956 KB
testcase_12 AC 749 ms
952 KB
testcase_13 AC 726 ms
956 KB
testcase_14 AC 749 ms
952 KB
testcase_15 AC 755 ms
952 KB
testcase_16 AC 748 ms
952 KB
testcase_17 AC 760 ms
956 KB
testcase_18 AC 788 ms
956 KB
testcase_19 AC 760 ms
956 KB
testcase_20 AC 747 ms
956 KB
testcase_21 AC 766 ms
952 KB
testcase_22 AC 753 ms
956 KB
testcase_23 AC 772 ms
956 KB
testcase_24 AC 743 ms
956 KB
testcase_25 AC 719 ms
956 KB
testcase_26 AC 774 ms
956 KB
testcase_27 AC 742 ms
956 KB
testcase_28 AC 758 ms
956 KB
testcase_29 AC 740 ms
956 KB
testcase_30 AC 761 ms
956 KB
testcase_31 AC 729 ms
956 KB
権限があれば一括ダウンロードができます

ソースコード

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 *t){
  int a=t[0];
  int b=t[1];
  if(a==t[2]){
    int i;
    for(i=0;i<l;i++){
      int index=POS(a,b+i);
      s[index]=s[index]=='0'?'1':'0';
    }
  } else {
    int i;
    for(i=0;i<l;i++){
      int index=POS(a+i,b);
      s[index]=s[index]=='0'?'1':'0';
    }
  }
  return;
}

int cnt_put(int l,char *s,int n,int *t){
  int a=t[0];
  int b=t[1];
  if(a==t[2]){
    int cnt=0;
    int i;
    for(i=0;i<l;i++){
      int index=POS(a,b+i);
      cnt+=(s[index]=='0'?1:-1);
    }
    return cnt;
  } else {
    int cnt=0;
    int i;
    for(i=0;i<l;i++){
      int index=POS(a+i,b);
      cnt+=(s[index]=='0'?1:-1);
    }
    return cnt;
  }
}

void assign(int *a,int i,int j,int l,int dir){
  if(dir==0){
    a[0]=i;
    a[1]=j;
    a[2]=i+l-1;
    a[3]=j;
  } else {
    a[0]=i;
    a[1]=j;
    a[2]=i;
    a[3]=j+l-1;
  }
  return;
}

int func_algo10(int l,char *s,const int n,int *a){
  int max=-l-1;
  int i,j;
  for(j=0;j<n;j++){
    int c=0;
    for(i=0;i<l;i++){
      c+=(s[POS(i,j)]=='0'?-1:1);
    }
    i=0;
    if(c>max || (c==max && s[POS(i,j)]=='1' && s[POS(i+l-1,j)]=='1' && s[POS(i+l,j)]=='0')){
      max=c;
      assign(a,i,j,l,0);
    }
    while(i+l<n){
      c-=(s[POS(i,j)]=='0'?-1:1);
      c+=(s[POS(i+l,j)]=='0'?-1:1);
      i++;
      if(c>max || (c==max && s[POS(i,j)]=='1' && s[POS(i+l-1,j)]=='1' && s[POS(i-1,j)]=='0' && (i+l>=n || s[POS(i+l,j)]=='0'))){
	max=c;
	assign(a,i,j,l,0);
      }
    }
  }
  for(i=0;i<n;i++){
    int c=0;
    for(j=0;j<l;j++){
      c+=(s[POS(i,j)]=='0'?-1:1);
    }
    j=0;
    if(c>max || (c==max && s[POS(i,j)]=='1' && s[POS(i,j+l-1)]=='1' && s[POS(i,j+l)]=='0')){
      max=c;
      assign(a,i,j,l,1);
    }
    while(j+l<n){
      c-=(s[POS(i,j  )]=='0'?-1:1);
      c+=(s[POS(i,j+l)]=='0'?-1:1);
      j++;
      if(c>max || (c==max && s[POS(i,j)]=='1' && s[POS(i,j+l-1)]=='1' && s[POS(i,j-1)]=='0' && (j+l>=n || s[POS(i,j+l)]=='0'))){
	max=c;
	assign(a,i,j,l,1);
      }
    }
  }
  flip(l,s,n,a);
  return max;
}

int score(const char *s,const int n){
  int res=0;
  int i,j;
  for(i=0;i<n;i++){
    for(j=0;j<n;j++){
      res+=(s[POS(i,j)]=='0'?1:0);
    }
  }
  return res;
}

void print(const char *s,const int n){
  printf("score : %d\n",score(s,n));
  int i,j;
  for(i=0;i<n;i++){
    for(j=0;j<n;j++){
      putchar(s[POS(i,j)]);
    }
    putchar('\n');
  }
  putchar('\n');
  return;
}

void swap(len *array,int x,int y){
  len t=array[x];
  array[x]=array[y];
  array[y]=t;
  return;
}

void shuffle(len *array,int len){
  int i;
  for(i=0;i<len;i++) swap(array,i,rand()%len);
  return;
}

int func_algo6(int l1,int l2,char *s,int n,int *a,int *b){
  int max=-l1-1;
  int i,j,k;
  for(i=0;i<n;i++){
    for(j=0;j+l1-1<n;j++){
      for(k=0;k+l2-1<l1;k++){
	int c=0;
	int x;
	for(x=j;x<j+k;x++) c+=(s[POS(i,x)]=='0'?-1:1);
	for(x=j+k+l2;x<j+l1;x++) c+=(s[POS(i,x)]=='0'?-1:1);
	if(c>max){
	  max=c;
	  assign(a,i,j,l1,1);
	  assign(b,i,j+k,l2,1);
	}
      }
      for(;k<l1 && j+k+l2-1<n;k++){
	int c=0;
	int x;
	for(x=j;x<j+k;x++) c+=(s[POS(i,x)]=='0'?-1:1);
	for(x=l1;x<k+l2;x++) c+=(s[POS(i,x)]=='0'?-1:1);
	if(c>max){
	  max=c;
	  assign(a,i,j,l1,1);
	  assign(b,i,j+k,l2,1);
	}
      }
    }
  }
  for(i=0;i+l1-1<n;i++){
    for(j=0;j<n;j++){
      for(k=0;k+l2-1<l1;k++){
	int c=0;
	int x;
	for(x=i;x<i+k;x++) c+=(s[POS(x,j)]=='0'?-1:1);
	for(x=i+k+l2;x<i+l1;x++) c+=(s[POS(x,j)]=='0'?-1:1);
	if(c>max){
	  max=c;
	  assign(a,i,j,l1,0);
	  assign(b,i+k,j,l2,0);
	}
      }
      for(;k<l1 && i+k+l2-1<n;k++){
	int c=0;
	int x;
	for(x=i;x<i+k;x++) c+=(s[POS(x,j)]=='0'?-1:1);
	for(x=l1;x<k+l2;x++) c+=(s[POS(x,j)]=='0'?-1:1);
	if(c>max){
	  max=c;
	  assign(a,i,j,l1,0);
	  assign(b,i+k,j,l2,0);
	}
      }
    }
  }
  flip(l1,s,n,a);
  flip(l2,s,n,b);
  return max;
}

void algo10(char *s,int n,len *array,int k,int *ans){
  qsort(array,k,sizeof(len),cmp);
  const int parameter=4;
  int i;
  for(i=0;i<k && array[i].l>=parameter;i++);
  const int m=i;
  len *now=(len *)malloc(sizeof(len)*m);
  len *used=(len *)malloc(sizeof(len)*m);
  len *cover=(len *)malloc(sizeof(len)*m);
  len *maxCover=(len *)malloc(sizeof(len)*m);
  len *maxUsed=(len *)malloc(sizeof(len)*m);
  for(i=0;i<m;i++) now[i]=array[i];
  const int useParameter=5;
  int usedLen,coverLen;
  int maxCoverLen=0,maxUsedLen=0;
  int maxScore=score(s,n);
  int *tmp=(int *)malloc(sizeof(int)*4*k);
  int iter=100;
  do{
    shuffle(now,m);
    usedLen=coverLen=0;
    for(i=0;i<m;i++){
      int up=func_algo10(now[i].l,s,n,tmp+4*now[i].index);
      if(up*useParameter<=now[i].l){
	flip(now[i].l,s,n,tmp+4*now[i].index);
	cover[coverLen++]=now[i];
      } else {
	used[usedLen++]=now[i];
      }
    }
    int p=score(s,n);
    if(p>maxScore){
      for(i=0;i<coverLen;i++) maxCover[i]=cover[i];
      maxCoverLen=coverLen;
      for(i=0;i<usedLen;i++) maxUsed[i]=used[i];
      maxUsedLen=usedLen;
      for(i=0;i<4*k;i++) ans[i]=tmp[i];
      maxScore=p;
    }
    for(i=0;i<usedLen;i++) flip(used[i].l,s,n,tmp+4*used[i].index);
  } while(iter--);
  for(i=0;i<maxUsedLen;i++) flip(maxUsed[i].l,s,n,ans+4*maxUsed[i].index);
  qsort(maxCover,maxCoverLen,sizeof(len),cmp);
  const int f=4;
  for(i=maxCoverLen/f*f;i<maxCoverLen;i++) func_algo10(maxCover[i].l,s,n,ans+4*maxCover[i].index);
  int diff=maxCoverLen/f;
  for(i=0;i<maxCoverLen/f*f;i+=2*diff){
    int j;
    for(j=i;j<i+diff;j++){
      func_algo6(maxCover[j].l,maxCover[j+diff].l,s,n,ans+4*maxCover[j].index,ans+4*maxCover[j+diff].index);
    }
  }
  for(i=m;i<k;i++) func_algo10(array[i].l,s,n,ans+4*array[i].index);
  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;
  }
  for(i=0;i<n;i++) scanf("%s",s+POS(i,0));
  //qsort(array,k,sizeof(len),cmp);
  algo10(s,n,array,k,ans);
  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(int argc,char **argv){
  run();
  return 0;
}
0