結果

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

ソースコード

diff # 

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

int DEBUG = 0;

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 = rand() % 2;
    res.size = -1;
    res.i = rand() % N;
    res.j = rand() % N;
  }
  return res;
}

int main(void) {
  srand(time(NULL));
  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 (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)
    printf("Score: %d\n", calc_score());
}
0