結果

問題 No.5002 stick xor
コンテスト
ユーザー moti
提出日時 2018-05-27 23:58:11
言語 C++17(clang)
(17.0.6 + boost 1.87.0)
結果
AC  
実行時間 57 ms / 1,000 ms
コード長 4,178 bytes
コンパイル時間 4,587 ms
実行使用メモリ 3,760 KB
スコア 32,487
最終ジャッジ日時 2022-07-31 03:19:19
合計ジャッジ時間 5,880 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge15
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 32
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>

#define REP(i,a,b) for(int i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)
#if defined DEBUG
#define DBG(...) printf(__VA_ARGS__)
#define PAUSE for (char c; ~scanf("%c", &c) && c != '\n';);
#else
#define DBG(...)
#define PAUSE
#endif

using namespace std;

int INF = 1<<29;

int a[66][66], a_tmp[66][66];
vector<pair<int, int>> lraw;
int l[666], lrr[666];
int lsum[66][66], lsum_tmp[66][66];
int usum[66][66], usum_tmp[66][66];
int N, K;
int max_diff = -INF;
vector<tuple<int, int, int, int>> max_placement;

void calc_xlsum(int i) {
  for (int j = N - 1; j >= 0; j--) {
    lsum[i][j] = (a[i][j] ? 1 : -1) + (j < N - 1 ? lsum[i][j + 1] : 0);
  }
}

void calc_yusum(int j) {
  for (int i = N - 1; i >= 0; i--) {
    usum[i][j] = (a[i][j] ? 1 : -1) + (i < N - 1 ? usum[i + 1][j] : 0);
  }
}

tuple<int, int, int, int, int> get_max_xcand(int L) {
  int mx = -INF;
  int idx_i = -1, idx_j = -1;
  rep(i, N) rep(j, N - L + 1) {
    int cand = lsum[i][j] - ( j + L < N ? lsum[i][j + L] : 0 );
    if (mx < cand) {
      mx = cand;
      idx_i = i, idx_j = j;
    }
  }
  return make_tuple(mx, idx_i, idx_j, idx_i, idx_j + L - 1);
}

tuple<int, int, int, int, int> get_max_ycand(int L) {
  int mx = -INF;
  int idx_i = -1, idx_j = -1;
  rep(i, N - L + 1) rep(j, N) {
    int cand = usum[i][j] - ( i + L < N ? usum[i + L][j] : 0 );
    if (mx < cand) {
      mx = cand;
      idx_i = i, idx_j = j;
    }
  }
  return make_tuple(mx, idx_i, idx_j, idx_i + L - 1, idx_j);
}

void solve() {
  int raw = 0;
  rep(i, N) rep(j, N) raw += !a[i][j];
  vector<tuple<int, int, int, int>> vec;
  int ret = raw;
  rep(k, K) {
    auto xcand = get_max_xcand(l[k]);
    auto ycand = get_max_ycand(l[k]);
    auto selected = max(xcand, ycand);
    int mx; int top, left, bottom, right;
    tie(mx, top, left, bottom, right) = selected;
    //*
    ret += mx;
    //*/
    vec.emplace_back(top, left, bottom, right);
    if (left == right) {
      REP(i, top, bottom + 1) a[i][left] ^= 1;
      calc_yusum(left);
    }
    if (top == bottom) {
      REP(j, left, right + 1) a[top][j] ^= 1;
      calc_xlsum(top);
    }
    /*
    DBG("-------------------\n");
    DBG("k (/ K) = %d / %d\n", k, K);
    rep(i, N) {
      rep(j, N) {
        if (a[i][j]) {
          DBG("\x1b[40m%3d\x1b[49m", a[i][j]);
        } else {
          DBG("\x1b[47m%3d\x1b[49m", a[i][j]);
        }
      }
      DBG("\n");
    }
    DBG("===================\n");
    PAUSE
    //*/
  }

  int diff = ret - raw;
  /*
  DBG("ret = %d\n", ret);
  DBG("diff = %d\n", diff);
  PAUSE
  //*/
  if (max_diff < diff) {
    max_diff = diff;
    int k = 0;
    max_placement.clear();
    max_placement.resize(K);
    for (auto e: vec) {
      max_placement[lraw[k++].second] = e;
    }
  }
}

int main() {
  cin >> N >> K;
  rep(i, K) {
    int l; cin >> l;
    lraw.emplace_back(l, i);
    lrr[i] = l;
  }

  rep(i, N) {
    string s; cin >> s;
    rep(j, N) a[i][j] = a_tmp[i][j] = s[j] - '0';
  }

  rep(i, N) {
    calc_xlsum(i);
    calc_yusum(i);
    rep(j, N) lsum_tmp[i][j] = lsum[i][j], usum_tmp[i][j] = usum[i][j];
  }

  std::random_device rdev{};
  std::mt19937 mt(rdev());
  // k [1 - 100] 区切りでシャッフルする
  for (int pt = 1; pt < min(K, 11); pt++) {
    sort(lraw.rbegin(), lraw.rend());
    for (int k = 0; ; k++) {
      if (k * pt >= K) break;
      int last = (k + 1) * pt;
      if (last > K) last = K;
      std::shuffle(lraw.begin() + k * pt, lraw.begin() + last, mt);
    }
/*
    DBG("\npartition: %d\n", pt);
    for (auto e: lraw) {
      DBG("%d ", e.first);
    }
    DBG("\n");
//*/
    rep(i, K) l[i] = lraw[i].first;

    /*
    DBG("-------------------\n");
    rep(i, N) {
      rep(j, N) {
        DBG("%3d", a[i][j]);
      }
      DBG("\n");
    }
    DBG("===================\n");
    //*/

    solve();

    rep(i, N) rep(j, N)
      a[i][j] = a_tmp[i][j], lsum[i][j] = lsum_tmp[i][j];
  }

  int i = 0;
  for (auto e: max_placement) {
    int x, y, z, w; tie(x, y, z, w) = e;
    printf("%d %d %d %d\n", x + 1, y + 1, z + 1, w + 1);
//    assert((x == z && y + lrr[i] - 1 == w) || (y == w && x + lrr[i] - 1 == z));
    i++;
  }
  DBG("MAX = %d\n", max_diff);
}
0