POJ 3685: Matrix

概要

N次正方行列があって，その(i,j)-成分はi^2+100000*i+j^2-100000*j+i*jで与えられる．
M番目に小さい要素の値はいくつか．

解法

解について二分探索．列を固定してしまえば，値は行について単調増加であることが式からわかる．
2次方程式を解けばO(1)で計算できるのだろうけど，ここでも二分探索を使った．

#include <cstdio>
#include <algorithm>

typedef long long ll;

const ll MAX_N = 50010;

ll N, M;
ll func(ll i, ll j){
    return i * i + 100000 * i + j * j - 100000 * j + i * j;
}
bool C(ll x){
    ll cnt = 0;
    for(int j = 1; j <= N; ++j){
        ll lb = 0, ub = N + 1;
        while(ub - lb > 1){
            ll mid = (lb + ub) / 2;
            if(func(mid, j) < x){
                lb = mid;
            } else{
                ub = mid;
            }
        }
        cnt += lb;
    }
    // printf(">>%lld\n", cnt);
    return cnt < M;
}
main(){
    int T;
    scanf("%d", &T);
    for(;T>0;--T){
        scanf("%lld%lld", &N, &M);
        ll ub = MAX_N * MAX_N * 3 + MAX_N * 100000 * 2;
        ll lb = -ub;
        while(ub - lb > 1){
            ll mid = (lb + ub) / 2;
            // printf("(%lld)\n", mid);
            if(C(mid)){
                lb = mid;
            }
            else{
                ub = mid;
            }
        }
        printf("%lld\n", lb);
    }
    return 0;
}