Login
Immutable PageDiscussionInfoAttachments
iz/競技プログラミング/PKU 3685 Matrix

MMA

http://poj.org/problem?id=3685

A_ij = i * i + 100,000 * i + j * j - 100,000 * j + i * j

で定義されるN次正方行列のM番目の値を調べる。

ある値x未満の数が行列中に何個あるかは A_ijの値はjを固定したときiについて単調増加なので各列について二分探索をすればN * lg(N)で求められる。

x未満の数がM個未満となるような最大のxをとってくればそれが中央値。

   1 #include <iostream>
   2 
   3 using namespace std;
   4 
   5 typedef long long ll;
   6 
   7 ll N, M;
   8 
   9 ll count_lt(ll x) {
  10     ll cnt = 0;
  11     for (ll j = 1; j <= N; j++) {
  12         // [lb, ub)
  13         ll lb = 0, ub = N+1;
  14         while (lb + 1 < ub) {
  15             ll i = (lb + ub) / 2; // mid = i
  16             if (i * i + 100000 * i + j * j - 100000 * j + i * j < x) {
  17                 lb = i;
  18             } else {
  19                 ub = i;
  20             }
  21         }
  22         cnt += lb;
  23     }
  24     return cnt;
  25 }
  26 
  27 int main() {
  28     int T; // the number of test cases
  29     cin >> T;
  30     while (T--) {
  31         cin >> N >> M;
  32         ll lb = -1LL << 60, ub = 1LL << 60;
  33         while (lb + 1 < ub) {
  34             ll mid = (lb + ub) / 2;
  35             if (count_lt(mid) < M) {
  36                 lb = mid;
  37             } else {
  38                 ub = mid;
  39             }
  40         }
  41         cout << lb << endl;
  42     }
  43     return 0;
  44 }

iz/競技プログラミング/PKU 3685 Matrix (last edited 2012-12-22 00:17:55 by iz)