playground/hackerearth.com/binary-monk-and-new-array.cpp at main · MuhtasimTanmoy/playground · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include <bits/stdc++.h>
using namespace std;

int main()
{
	int r, c;
	cin >> r >> c;
	int a[r][c];

	for (int i = 0; i < r; i++)
		for (int j = 0; j < c; j++)
			cin >> a[i][j];

	for (int i = 0; i < r; i++) sort(a[i], a[i] + c);

	int lowest = abs(a[0][0] - a[1][0]); //let it is the lowest

	for (int i = 0; i < r - 1; i++) {
		int *tmp;
		int tmp2;
		if (lowest == 0) break;

		for (int j = 0; j < c; j++) {
			if (lowest == 0)
				break;
			tmp = lower_bound(a[i + 1], a[i + 1] + c, a[i][j]);

			if (tmp == a[i + 1] + c) {
				tmp--;
				if (lowest > abs(a[i][j] - *tmp))
					lowest = abs(a[i][j] - *tmp);
				continue;
			}
			else if (tmp == (a[i + 1]))
				tmp2 = *tmp;
			else
				tmp2 = *(tmp - 1);

			if (abs(tmp2 - a[i][j]) < lowest)
				lowest = abs(tmp2 - a[i][j]);
			else if (abs(*tmp - a[i][j]) < lowest)
				lowest = abs(*tmp - a[i][j]);
		}
	}
	cout << lowest << endl;
	return 0;
}