Submission #3658898

---

Source Code Expand

#include <bits/stdc++.h>

using namespace std;

#define FORE(i, a) for (auto i = a.begin(); i != a.end(); ++i)
#define REPU(i, a, b) for (int i = (a); i < (b); ++i)
#define REPD(i, a, b) for (int i = (a); i > (b); --i)
#define MEM(a, x) memset(a, x, sizeof(a))
#define ALL(a) a.begin(), a.end()
#define UNIQUE(a) a.erase(unique(ALL(a)), a.end())

vector<string> split(const string &s, char c) {
	vector<string> v; stringstream ss(s); string x;
	while (getline(ss, x, c)) v.push_back(x);
	return v;
}
#define DEBUG(args...) { vector<string> _v = split(#args, ','); err(_v.begin(), args); }
void err(vector<string>::iterator it) {}
template<typename T, typename... Args>
void err(vector<string>::iterator it, T a, Args... args) {
	cerr << "[DEBUG] " << it -> substr((*it)[0] == ' ', it -> length()) << " = " << a << '\n';
	err(++it, args...);
}

typedef long long ll;
const int MOD = 1000000007;

template<class T, class U> inline T tmin(T a, U b) { return (a < b) ? a : b; }
template<class T, class U> inline T tmax(T a, U b) { return (a > b) ? a : b; }
template<class T, class U> inline void amax(T &a, U b) { if (b > a) a = b; }
template<class T, class U> inline void amin(T &a, U b) { if (b < a) a = b; }
template<class T> T gcd(T a, T b) { while (b != 0) { T c = a; a = b; b = c % b; } return a; }

const int N = 1000005;
int x[N], y[N];

int main(int argc, char *argv[]) {
	ios_base::sync_with_stdio(false);

	int n, D; cin >> n >> D;

	if (D > 30) return 0;
	vector<int> cnt(D * D, 0);
	REPU(i, 0, n) {
		cin >> x[i] >> y[i];
		x[i] %= D;
		y[i] %= D;
		cnt[x[i] * D + y[i]]++;
	}

	int ans = INT_MAX;
	int lb = 0, rb = 1000000000;
	while (rb - lb > 1) {
		int mb = (lb + rb) >> 1;
		bool ok(false);
		REPU(r, 0, D) {
			REPU(c, 0, D) {
				bool ok2(true);
				REPU(i, 0, D * D) if (cnt[i] > 0) {
					int vx = i / D, vy = i % D;
					if (vx < r) vx += D;
					if (vy < c) vy += D;
					if (mb + r < vx || mb + c < vy || ((mb + r - vx) / D + 1) * 1LL * ((mb + c - vy) / D + 1) < cnt[i]) {
						ok2 = false; break;
					}
				}
				if (ok2) {
					ok = true; break;
				}
				if (ok) break;
			}
		}
		if (ok) rb = mb;
		else lb = mb;
	}
	cout << rb << endl;

	return 0;
}

Submission Info

Judge Result