結果

問題 No.5002 stick xor
コンテスト
ユーザー moti
提出日時 2018-05-29 23:59:17
言語 C++17(clang)
(17.0.6 + boost 1.89.0)
結果
TLE  
(最新)
AC  
(最初)
実行時間 -
コード長 4,112 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 18,921 ms
実行使用メモリ 3,736 KB
スコア 0
最終ジャッジ日時 2020-08-23 04:37:36
ジャッジサーバーID
（参考情報） 		judge9 / judge7
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 16 TLE * 16
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#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];
int lsum[66][66], lsum_tmp[66][66];
int N, K;
int max_diff = -INF;

std::random_device rdev{};
std::mt19937 mt(rdev());

using place_t = tuple<int, int, int, int>;
vector<place_t> max_placement;

int count_white() {
  int ret = 0;
  rep(i, N) rep(j, N) ret += !a[i][j];
  return ret;
}

void paint_stick(int idx_i, int idx_j, int L) {
  REP(j, idx_j, idx_j + L) {
    a[idx_i][j] ^= 1;
  }
}

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

tuple<int, int, int> get_nth_max(int nth, int L) { // nth: 0-origin
  int mx = -INF;
  int idx_i = -1, idx_j = -1;
  deque<tuple<int, int, int>> deq;
  rep(i, N) rep(j, N - L + 1) {
    auto cand = lsum[i][j] - ( j + L < N ? lsum[i][j + L] : 0 );
    if (mx < cand) {
      mx = cand;
      idx_i = i, idx_j = j;
      deq.emplace_back(mx, idx_i, idx_j);
      if (deq.size() > nth + 1) {
        deq.pop_front();
      }
    }
  }
  return deq[0]; // nth max
}

void solve(int rnd) {
  vector<place_t> vec;
  auto raw = count_white();
  auto ret = raw;
  rep(k, K) {
    auto t = get_nth_max(rnd == 0 ? 0 : (mt() % 3 < 1 ? 1 : 0), l[k]);
    int mx, idx_i, idx_j; tie(mx, idx_i, idx_j) = t;
    ret += mx;
    vec.emplace_back(idx_i, idx_j, idx_i, idx_j + l[k] - 1);
    paint_stick(idx_i, idx_j, l[k]);
    calc_xlsum(idx_i);
  }

  auto diff = ret - raw;
  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;
    }
  }
}

void annealing() {
  /*
あらかじめ、計算する時間をTを決める。
以下のスコープ内のコードを時間T経過するまで繰り返す。
{
    適当に、次の状態（近傍）を選ぶ。
    (1) 次の状態のスコアが、今の状態のスコアより良くなった場合は、常に、状態を次の状態にする（遷移）。
    (2) 次の状態のスコアが、今の状態のスコアより悪くなった場合でも、ある確率で、状態を次の状態にする。
        確率は以下のように決める。
       (2.A) 序盤(時刻t=0に近いとき)ほど高確率で、終盤(t=Tに近いとき)ほど低確率。
       (2.B) スコアが悪くなった量が大きければ大きいほど、低確率。
}
最後に、今まで一番スコアのよかった状態を選ぶ。
  */

//  solve(0);
}

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

  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);
    rep(j, N) lsum_tmp[i][j] = lsum[i][j];
  }

  // k [1 - 100] 区切りでシャッフルする
  for (int pt = 1; pt < min(K, 101); 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(0);
    rep(i, N) rep(j, N)
      a[i][j] = a_tmp[i][j], lsum[i][j] = lsum_tmp[i][j];

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

  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);
  }
  DBG("MAX = %d\n", max_diff);
}
0