結果

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

ソースコード

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;
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 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) {
    int mx = -INF;
    int idx_i = -1, idx_j = -1;
    rep(i, N) rep(j, N - l[k] + 1) {
      int cand = lsum[i][j] - ( j + l[k] < N ? lsum[i][j + l[k]] : 0 );
      if (mx < cand) {
        mx = cand;
        idx_i = i, idx_j = j;
      }
    }
    //*
    ret += mx;
    //*/
    vec.emplace_back(idx_i, idx_j, idx_i, idx_j + l[k] - 1);
    REP(j, idx_j, idx_j + l[k]) {
      a[idx_i][j] ^= 1;
    }
    /*
    DBG("-------------------\n");
    rep(i, N) {
      rep(j, N) {
        DBG("%3d", a[i][j]);
      }
      DBG("\n");
    }
    DBG("===================\n");
    //*/
    calc_xlsum(idx_i);
  }

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

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

  std::random_device rdev{};
  std::mt19937 mt(rdev());
  // 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();

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

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