Matrix
Time Limit: 6000MS | Memory Limit: 65536K | |
Total Submissions: 4428 | Accepted: 1102 |
Description
Given a N × N matrix A, whose element in the i-th row and j-th column Aij is an number that equals i2 + 100000 × i + j2 - 100000 × j + i × j, you are to find the M-th smallest element in the matrix.
Input
The first line of input is the number of test case.
For each test case there is only one line contains two integers, N(1 ≤ N ≤ 50,000) and M(1 ≤ M ≤ N × N). There is a blank line before each test case.
Output
For each test case output the answer on a single line.
Sample Input
12 1 1 2 1 2 2 2 3 2 4 3 1 3 2 3 8 3 9 5 1 5 25 5 10
Sample Output
3
-99993
3
12
100007
-199987
-99993
100019
200013
-399969
400031
-99939
Source
POJ Founder Monthly Contest – 2008.08.31, windy7926778
首先二分第m小的数,由公式易得每列的数是按照从小到大排列的,因此可二分,两次二分即可。
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream> using namespace std; typedef long long ll; int n;
ll m; ll cal(ll i,ll j) {
return i * i + j * j + (i - j) * + i * j;
} bool judge(ll x) {
ll sum = ;
for(int j = ; j <= n; ++j) {
int l = ,r = n;
while(l < r){
int mid = (l + r + ) / ;
if(cal(mid,j) <= x) {
l = mid;
} else {
r = mid - ;
}
}
sum += l;
} return sum >= m; } void solve() {
ll l = -1e12,r = 1e12; //printf(" n = %d l = %lld r = %lld\n",n,l,r); while(l < r) {
ll mid = (l + r) >> ;
if(judge(mid)) r = mid;
else l = mid + ;
} printf("%I64d\n",l);
} int main() {
// freopen("sw.in","r",stdin); int t;
scanf("%d",&t); while(t--) {
scanf("%d%I64d",&n,&m);
solve();
} return ;
}