結果
| 問題 | No.5002 stick xor |
| ユーザー |
 akakimidori
|
| 提出日時 | 2018-05-27 11:13:52 |
| 言語 | C90 (gcc 11.4.0) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 5,562 bytes |
| コンパイル時間 | 46,771 ms |
| スコア | 0 |
| 最終ジャッジ日時 | 2018-05-27 11:14:40 |
|
ジャッジサーバーID （参考情報） |
judge9 / |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | TLE | - |
| testcase_01 | TLE | - |
| testcase_02 | TLE | - |
| testcase_03 | TLE | - |
| testcase_04 | TLE | - |
| testcase_05 | TLE | - |
| testcase_06 | TLE | - |
| testcase_07 | TLE | - |
| testcase_08 | TLE | - |
| testcase_09 | TLE | - |
| testcase_10 | TLE | - |
| testcase_11 | TLE | - |
| testcase_12 | TLE | - |
| testcase_13 | TLE | - |
| testcase_14 | TLE | - |
| testcase_15 | TLE | - |
| testcase_16 | TLE | - |
| testcase_17 | TLE | - |
| testcase_18 | TLE | - |
| testcase_19 | TLE | - |
| testcase_20 | TLE | - |
| testcase_21 | TLE | - |
| testcase_22 | TLE | - |
| testcase_23 | TLE | - |
| testcase_24 | TLE | - |
| testcase_25 | TLE | - |
| testcase_26 | TLE | - |
| testcase_27 | TLE | - |
| testcase_28 | TLE | - |
| testcase_29 | TLE | - |
| testcase_30 | TLE | - |
| testcase_31 | TLE | - |
ソースコード
#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 func(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){
max=c;
a[0]=i;
a[1]=j;
a[2]=i+l-1;
a[3]=j;
}
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){
max=c;
a[0]=i;
a[1]=j;
a[2]=i+l-1;
a[3]=j;
}
}
}
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){
max=c;
a[0]=i;
a[1]=j;
a[2]=i;
a[3]=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){
max=c;
a[0]=i;
a[1]=j;
a[2]=i;
a[3]=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 swap(len *array,int x,int y){
len t=array[x];
array[x]=array[y];
array[y]=t;
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<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;
a[0]=i;
a[1]=j;
a[2]=i;
a[3]=j+l1-1;
b[0]=i;
b[1]=j+k;
b[2]=i;
b[3]=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;
a[0]=i;
a[1]=j;
a[2]=i;
a[3]=j+l1-1;
b[0]=i;
b[1]=j+k;
b[2]=i;
b[3]=j+k+l2-1;
}
}
}
}
for(i=0;i+l1<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;
a[0]=i;
a[1]=j;
a[2]=i+l1-1;
a[3]=j;
b[0]=i+k;
b[1]=j;
b[2]=i+k+l2-1;
b[3]=j;
}
}
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;
a[0]=i;
a[1]=j;
a[2]=i+l1-1;
a[3]=j;
b[0]=i+k;
b[1]=j;
b[2]=i+k+l2-1;
b[3]=j;
}
}
}
}
flip(l1,s,n,a);
flip(l2,s,n,b);
return max;
}
void algo6(char *s,int n,len *array,int k,int *ans,int *tmp){
const int parameter=4;
int i;
for(i=0;i<k && array[i].l>=parameter;i++);
const int m=i/2*2;
for(i=0;i<m;i++) func(array[i].l,s,n,ans+4*array[i].index);
int maxScore=score(s,n);
int iter=10;
while(iter--){
for(i=0;i<4*k;i++) tmp[i]=ans[i];
for(i=0;i<m;i++) swap(array,i,rand()%m);
for(i=0;i<m;i++) flip(array[i].l,s,n,tmp+4*array[i].index);
for(i=0;i<m;i+=2){
int a=func(array[i].l,s,n,tmp+4*array[i].index);
int b=func(array[i+1].l,s,n,tmp+4*array[i+1].index);
if(ABS(array[i].l-array[i+1].l)>=3 && (a<=0 || b<=0)){
flip(array[i].l,s,n,tmp+4*array[i].index);
flip(array[i+1].l,s,n,tmp+4*array[i+1].index);
int tmp0[4];
int tmp1[4];
int c;
if(array[i].l>array[i+1].l){
c=func_algo6(array[i].l,array[i+1].l,s,n,tmp0,tmp1);
} else {
c=func_algo6(array[i+1].l,array[i].l,s,n,tmp1,tmp0);
}
if(c<a+b){
flip(array[i].l,s,n,tmp0);
flip(array[i+1].l,s,n,tmp1);
flip(array[i].l,s,n,tmp+4*array[i].index);
flip(array[i+1].l,s,n,tmp+4*array[i+1].index);
} else {
tmp[4*array[i].index+0]=tmp0[0];
tmp[4*array[i].index+1]=tmp0[1];
tmp[4*array[i].index+2]=tmp0[2];
tmp[4*array[i].index+3]=tmp0[3];
tmp[4*array[i+1].index+0]=tmp1[0];
tmp[4*array[i+1].index+1]=tmp1[1];
tmp[4*array[i+1].index+2]=tmp1[2];
tmp[4*array[i+1].index+3]=tmp1[3];
}
}
}
int localScore=score(s,n);
if(localScore>maxScore){
maxScore=localScore;
for(i=0;i<4*k;i++) ans[i]=tmp[i];
} else {
for(i=0;i<m;i++){
flip(array[i].l,s,n,tmp+4*array[i].index);
flip(array[i].l,s,n,ans+4*array[i].index);
}
}
}
for(i=m;i<k;i++){
func(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 *tmp=(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));
algo6(s,n,array,k,ans,tmp);
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;
}