#1195004 (C++23(gcc16)) No.5025 Forest Fire

• 問題: No.5025 Forest Fire
• ユーザー: occhan
• 提出日時: 2026-10-24 15:45:36
• 言語: C++23(gcc16) (gcc 16.2.0 + boost 1.92.0 + ACL)
• 結果: AC
• 実行時間: 1,790 ms / 2,000 ms
• コード長: 4,001 bytes
• コンパイル時間: 3,110 ms
• コンパイル使用メモリ: 369,040 KB
• 実行使用メモリ: 9,920 KB
• スコア: 83,787,440
• 最終ジャッジ日時: 2026-10-24 15:48:06
• 合計ジャッジ時間: 149,266 ms
• ジャッジサーバーID （参考情報）: judge6_0 / <nil>

ファイルパターン	結果
other	AC * 50

ソースコード

#include <bits/stdc++.h>
using namespace std;

struct XorShift {
  uint64_t x;

  explicit XorShift(uint64_t seed) : x(seed) {}

  uint64_t next64() {
    x ^= x << 7;
    x ^= x >> 9;
    return x;
  }

  uint32_t next32() {
    return static_cast<uint32_t>(next64() >> 32);
  }

  int next10() {
    uint32_t v;
    do {
      v = next32();
    } while (v >= 4294967290u);
    return v % 10;
  }
};

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  const auto startTime = chrono::steady_clock::now();

  int N, K;
  cin >> N >> K;

  vector<string> d(N);
  for (int i = 0; i < N; ++i) cin >> d[i];

  const int V = N * N;

  vector<int> treeCells;
  treeCells.reserve(V);

  uint64_t seed = 0x123456789abcdefULL;

  for (int i = 0; i < N; ++i) {
    for (int j = 0; j < N; ++j) {
      int id = i * N + j;
      int x = d[i][j] - '0';

      if (x > 0) treeCells.push_back(id);

      seed ^= static_cast<uint64_t>(x + 1) *
              (static_cast<uint64_t>(id + 1) * 0x9e3779b97f4a7c15ULL);
      seed ^= seed >> 27;
      seed *= 0x94d049bb133111ebULL;
    }
  }

  if (seed == 0) seed = 1;

  XorShift rng(seed);

  vector<unsigned char> dry(V);

  vector<int> ord(V);
  vector<int> low(V);
  vector<int> parent(V);
  vector<int> sub(V);

  vector<int> separatedSize(V);
  vector<long long> separatedSq(V);

  vector<unsigned long long> totalValue(V, 0);

  int timer = 0;
  long long samples = 0;

  const int di[4] = {-1, 1, 0, 0};
  const int dj[4] = {0, 0, -1, 1};

  while (true) {
    auto now = chrono::steady_clock::now();
    double elapsed =
        chrono::duration<double>(now - startTime).count();

    if (elapsed >= 1.8) break;

    fill(dry.begin(), dry.end(), 0);

    for (int id : treeCells) {
      int i = id / N;
      int j = id % N;
      int prob = d[i][j] - '0';

      if (rng.next10() < prob) {
        dry[id] = 1;
      }
    }

    fill(ord.begin(), ord.end(), -1);
    fill(parent.begin(), parent.end(), -1);
    fill(separatedSize.begin(), separatedSize.end(), 0);
    fill(separatedSq.begin(), separatedSq.end(), 0);

    timer = 0;

    for (int start : treeCells) {
      if (!dry[start] || ord[start] != -1) continue;

      vector<int> component;
      component.reserve(256);

      auto dfs = [&](auto&& self, int v) -> void {
        ord[v] = low[v] = timer++;
        sub[v] = 1;
        component.push_back(v);

        int i = v / N;
        int j = v % N;

        for (int dir = 0; dir < 4; ++dir) {
          int ni = i + di[dir];
          int nj = j + dj[dir];

          if (ni < 0 || ni >= N || nj < 0 || nj >= N) continue;

          int to = ni * N + nj;
          if (!dry[to]) continue;

          if (ord[to] == -1) {
            parent[to] = v;
            self(self, to);

            sub[v] += sub[to];
            low[v] = min(low[v], low[to]);

            if (low[to] >= ord[v]) {
              separatedSize[v] += sub[to];
              separatedSq[v] +=
                  1LL * sub[to] * sub[to];
            }
          } else if (to != parent[v]) {
            low[v] = min(low[v], ord[to]);
          }
        }
      };

      dfs(dfs, start);

      int S = static_cast<int>(component.size());
      long long original = 1LL * S * S;

      for (int v : component) {
        int remain = S - 1 - separatedSize[v];

        long long after =
            separatedSq[v] + 1LL * remain * remain;

        long long value = original - after;

        totalValue[v] +=
            static_cast<unsigned long long>(value);
      }
    }

    ++samples;
  }

  vector<int> candidates = treeCells;

  sort(candidates.begin(), candidates.end(),
       [&](int a, int b) {
         if (totalValue[a] != totalValue[b]) {
           return totalValue[a] > totalValue[b];
         }
         return a < b;
       });

  int M = min(K, static_cast<int>(candidates.size()));

  cout << M << '\n';

  for (int k = 0; k < M; ++k) {
    int id = candidates[k];
    cout << id / N << ' ' << id % N << '\n';
  }

  return 0;
}