#260660 (C) No.5002 stick xor

• 問題: No.5002 stick xor
• ユーザー: letrangerjp
• 提出日時: 2018-05-26 19:58:40
• 言語: C (gcc 13.3.0)
• 結果: TLE
• 実行時間: -
• コード長: 5,254 bytes
• コンパイル時間: 34,027 ms
• 実行使用メモリ: 956 KB
• スコア: 38,923
• 最終ジャッジ日時: 2018-05-26 19:59:16
• ジャッジサーバーID （参考情報）: judge7 /

ファイルパターン	結果
other	AC * 31 TLE * 1

ソースコード

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

int DEBUG = 0;
const int TimeLimit = 980 * 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 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;
}

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;
      // putchar(A[i][j]+48);
    }
  }
  // printf("a:%d,b:%d,c:%d,d:%d,res:%d\n", t.a,t.b,t.c,t.d,res);
  return res;
}

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;
  }
  qsort(LI, K, sizeof(LI[0]), cmp);
  // for (int i = 0; i < K; ++i) {
  //   printf("l:%d,i:%d ", LI[i].l, LI[i].i);
  // }

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

  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;
  }

  // ここから
  for (;clock() < TimeLimit;) {
  // for (int q = 0; q < 100000; ++q) {
    int i = rnd(K);
    ans_t t = ans[i];
    // int size = abs(t.a - t.c) + abs(t.b - t.d) + 1;
    int size = L[i];
    if (size < 3)
      continue;

    // int base = -calc_sub_by_ans(t);
    swap_by_ans(t);
    int base = calc_add_by_ans(t);
    // printf("base:%d\n", base);
    if (base == size) {
      swap_by_ans(t);
      continue;
    }
    int modified = 0;
    for (int j = 0; j < 100; ++j) {
      ans_t u;
      if (rnd(2)) {
        u.a = u.c = rnd(N) + 1;
        u.b = rnd(N - size + 1) + 1;
        u.d = u.b + size - 1;
      } else {
        u.b = u.d = rnd(N) + 1;
        u.a = rnd(N - size + 1) + 1;
        u.c = u.a + size - 1;
      }
      // printf("[%d > %d] ", calc_add_by_ans(u), base);
      if (calc_add_by_ans(u) > base) {
        swap_by_ans(u);
        ans[i] = u;
        modified = 1;
        break;
      }
    }
    if (!modified) {
      swap_by_ans(t);
    }
  }

  for (int i = 0; i < K; ++i) {
    printf("%d %d %d %d\n", ans[i].a, ans[i].b, ans[i].c, 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", calc_score());

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