satanic0258
9/27/2017 - 5:51 PM

SRM721

SRM721

using PAIR = std::pair<int, int>;
constexpr int INFINT = 1 << 30;    // 1.07x10^ 9

std::string POS = "Possible", IMP = "Impossible";
struct RememberWords {
	PAIR f(ll d, ll w) {
		PAIR res(-1, -1);
		if (d*(d - 1) / 2 >= w) res.first = 0;
		else {
			ll l = 0, r = INFINT;
			while (l + 1 != r) {
				ll m = (l + r) / 2;
				if (m*d + d*(d - 1) / 2 >= w) r = m;
				else l = m;
			}
			res.first = r;
		}
		ll l = 0, r = INFINT;
		while (l + 1 != r) {
			ll m = (l + r) / 2;
			ll s;
			if (m < d) s = m * (m + 1) / 2;
			else s = (m - (d - 1))*d + d*(d - 1) / 2;
			if (s > w) r = m;
			else l = m;
		}
		res.second = l;
		return res;
	}

	std::string isPossible(int d1, int d2, int w1, int w2) {
		PAIR p1(f(d1, w1));
		PAIR p2(f(d2, w2));
		--p1.first; ++p1.second;
		if (p2.second < p1.first || p1.second < p2.first) return IMP;
		return POS;
	}
};