random/random_monge.hpp

• View this file on GitHub
• Last update: 2026-05-31 17:32:53+09:00
• Include: #include "random/random_monge.hpp"

Depends on

• random/base.hpp

Verified with

• test/1_mytest/check_monge.test.cpp
• test/1_mytest/monge_shortest_path.test.cpp
• test/1_mytest/monotone_minima.test.cpp
• test/1_mytest/smawk.test.cpp

Code

#pragma once
#include "random/base.hpp"

// A[i1][j1] + A[i2][j2] <= A[i1][j2] + A[i2][j1] for i1 < i2, j1 < j2.
vvc<ll> random_monge_matrix(int H, int W) {
  ll LIM = 10;
  vv(ll, D, H, W);
  FOR(i, H) FOR(j, W) D[i][j] = RNG(0, LIM + 1);

  vv(ll, A, H, W);
  FOR(i, H) FOR(j, W) {
    ll x = D[i][j];
    if (i) x += A[i - 1][j];
    if (j) x += A[i][j - 1];
    if (i && j) x -= A[i - 1][j - 1];
    A[i][j] = x;
  }

  vc<ll> row(H), col(W);
  FOR(i, H) row[i] = RNG(-LIM * W, LIM * W + 1);
  FOR(j, W) col[j] = RNG(-LIM * H, LIM * H + 1);

  FOR(i, H) FOR(j, W) A[i][j] = -A[i][j] + row[i] + col[j];
  return A;
}

#line 2 "random/base.hpp"

u64 RNG_64() {
  static u64 x_ = u64(chrono::duration_cast<chrono::nanoseconds>(chrono::high_resolution_clock::now().time_since_epoch()).count()) * 10150724397891781847ULL;
  x_ ^= x_ << 7;
  return x_ ^= x_ >> 9;
}

u64 RNG(u64 lim) { return RNG_64() % lim; }

ll RNG(ll l, ll r) { return l + RNG_64() % (r - l); }
#line 3 "random/random_monge.hpp"

// A[i1][j1] + A[i2][j2] <= A[i1][j2] + A[i2][j1] for i1 < i2, j1 < j2.
vvc<ll> random_monge_matrix(int H, int W) {
  ll LIM = 10;
  vv(ll, D, H, W);
  FOR(i, H) FOR(j, W) D[i][j] = RNG(0, LIM + 1);

  vv(ll, A, H, W);
  FOR(i, H) FOR(j, W) {
    ll x = D[i][j];
    if (i) x += A[i - 1][j];
    if (j) x += A[i][j - 1];
    if (i && j) x -= A[i - 1][j - 1];
    A[i][j] = x;
  }

  vc<ll> row(H), col(W);
  FOR(i, H) row[i] = RNG(-LIM * W, LIM * W + 1);
  FOR(j, W) col[j] = RNG(-LIM * H, LIM * H + 1);

  FOR(i, H) FOR(j, W) A[i][j] = -A[i][j] + row[i] + col[j];
  return A;
}

Back to top page