結果

問題 No.5002 stick xor
コンテスト
ユーザー letrangerjp
提出日時 2018-05-26 20:29:06
言語 C
(gcc 13.3.0)
結果
AC  
実行時間 972 ms / 1,000 ms
コード長 4,825 bytes
コンパイル時間 33,182 ms
実行使用メモリ 956 KB
スコア 41,651
最終ジャッジ日時 2018-05-26 20:29:40
ジャッジサーバーID
（参考情報） 		judge9 /
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 32
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>

const int DEBUG = 0;
const int TimeLimit = 960 * 1000;

static unsigned long y = 2463534242;
unsigned long xorshift(void) {
  y = y ^ (y << 13); y = y ^ (y >> 17);
  return y = y ^ (y << 5);
}
int rnd(int max) {
  return xorshift() % max;
}

typedef struct {
  int l;
  int i;
} LI_t;

typedef struct {
  int horizonalp;
  int size;
  int i;
  int j;
} target_t;

typedef struct {
  int a, b, c, d;
} ans_t;

int N, K;
int L[500];
LI_t LI[500];
int srcA[60][60], srcB[60][60];
int A[60][60], B[60][60];
int FirstScore;


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

int count_white(void) {
  int res = 0;
  for (int i = 0; i < N; ++i) {
    for (int j = 0; j < N; ++j) {
      res += A[i][j] ^ 1;
    }
  }
  return res;
}

int calc_score(void) {
  return count_white() - FirstScore;
}

target_t get_target(int len) {
  int found = 0;
  target_t res;
  int max = 0;

  for (int i = 0; i < N; ++i) {
    int sum = 0;
    int cusum[N+1];
    cusum[0] = sum;
    for (int j = 0; j < N; ++j) {
      cusum[j+1] = sum += A[i][j];
    }
    for (int j = 0; j <= N-len; ++j) {
      if (cusum[j+len] - cusum[j] > max) {
        found = 1;
        max = cusum[j+len] - cusum[j];
        res.horizonalp = 1;
        res.size = max;
        res.i = i;
        res.j = j;
        if (max >= len)
          return res;
      }
    }
  }
  for (int i = 0; i < N; ++i) {
    int sum = 0;
    int cusum[N+1];
    cusum[0] = sum;
    for (int j = 0; j < N; ++j) {
      cusum[j+1] = sum += B[i][j];
    }
    for (int j = 0; j <= N-len; ++j) {
      if (cusum[j+len] - cusum[j] > max) {
        found = 1;
        max = cusum[j+len] - cusum[j];
        res.horizonalp = 0;
        res.size = max;
        res.i = i;
        res.j = j;
        if (max >= len)
          return res;
      }
    }
  }
  if (!found) {
    res.horizonalp = rnd(2);
    res.size = -1;
    res.i = rnd(N);
    res.j = rnd(N);
  }
  return res;
}

void swap_by_ans(ans_t t) {
  for (int i = t.a-1; i <= t.c-1; ++i) {
    for (int j = t.b-1; j <= t.d-1; ++j) {
      A[i][j] ^= 1;
      B[j][i] ^= 1;
    }
  }
}

int calc_sub_by_ans(ans_t t) {
  int res = 0;
  for (int i = t.a-1; i <= t.c-1; ++i) {
    for (int j = t.b-1; j <= t.d-1; ++j) {
      res += A[i][j] == 0 ? 1 : -1;
    }
  }
  return res;
}

int calc_add_by_ans(ans_t t) {
  int res = 0;
  for (int i = t.a-1; i <= t.c-1; ++i) {
    for (int j = t.b-1; j <= t.d-1; ++j) {
      res += A[i][j] == 1 ? 1 : -1;
    }
  }
  return res;
}

void shuffle_LI(void) {
  for (int i = K - 1; i > 0; --i) {
    int j = rnd(i + 1);
    LI_t t = LI[i];
    LI[i] = LI[j];
    LI[j] = t;
  }

}

int main(void) {
  scanf("%d %d", &N, &K);
  for (int i = 0; i < K; ++i) {
    int l;
    scanf("%d", &l);
    L[i] = l;
    LI[i].l = l;
    LI[i].i = i;
  }

  for (int i = 0; i < N; ++i) {
    char s[100];
    scanf("%s\n", s);
    for (int j = 0; j < N; ++j) {
      srcA[i][j] = srcB[j][i] = s[j] - 48;
    }
  }
  memcpy(A, srcA, sizeof(int)*N*N);
  memcpy(B, srcB, sizeof(int)*N*N);
  FirstScore = count_white();
  if (DEBUG)
    printf("FirstScore: %d\n", FirstScore);

  ans_t max_ans[K];
  int max_score = 0;
  for (;clock() < TimeLimit;) {
  // for (int q = 0; q < 10; ++q) {
    ans_t ans[K];
    for (int i = 0; i < K; ++i) {
      int a, b, c, d;
      target_t target = get_target(LI[i].l);
      if (target.j > N - LI[i].l)
        target.j = N - LI[i].l;
      if (target.horizonalp) {
        for (int j = target.j; j < target.j+LI[i].l; ++j) {
          A[target.i][j] ^= 1;
          B[j][target.i] ^= 1;
        }
        a = c = target.i+1;
        b = target.j+1;
        d = target.j+LI[i].l;
      } else {
        for (int j = target.j; j < target.j+LI[i].l; ++j) {
          B[target.i][j] ^= 1;
          A[j][target.i] ^= 1;
        }
        b = d = target.i+1;
        a = target.j+1;
        c = target.j+LI[i].l;
      }
      ans[LI[i].i].a = a;
      ans[LI[i].i].b = b;
      ans[LI[i].i].c = c;
      ans[LI[i].i].d = d;
    }
    int score = calc_score();
    if (score > max_score) {
      max_score = score;
      for (int j = 0; j < K; ++j)
        max_ans[j] = ans[j];
    }
    shuffle_LI();
    memcpy(A, srcA, sizeof(int)*N*N);
    memcpy(B, srcB, sizeof(int)*N*N);
  }

  for (int i = 0; i < K; ++i) {
    printf("%d %d %d %d\n", max_ans[i].a, max_ans[i].b, max_ans[i].c, max_ans[i].d);
  }

  // if (DEBUG) {
  //   for (int i = 0; i < N; ++i) {
  //     for (int j = 0; j < N; ++j) {
  //       putchar(A[i][j]+48);
  //     }
  //     puts("");
  //   }
  // }

  if (DEBUG)
    printf("Score: %d\n", max_score);

  // ans_t v;
  // v.a = v.b = 1;
  // v.c = v.d = 60;
  // printf("%d\n", calc_add_by_ans(v));
}
0