Submission #1303476

#	Time	Username	Problem	Language	Result	Execution time	Memory
1303476		jinhan814	개구리 (KOI13_frog)	C++20	2 / 19	1096 ms	1356 KiB

frog

#include <bits/stdc++.h>
using namespace std;

// debug /*{{{*/
#define debug(...) __dbg(#__VA_ARGS__, __VA_ARGS__)

template<typename T, typename U> ostream& operator<< (ostream&, pair<T, U>);
template<typename...T> ostream& operator<< (ostream&, tuple<T...>);
template<typename T, size_t U> ostream& operator<< (ostream& out, array<T, U> i);
template<typename T, typename A> ostream& operator<< (ostream& out, vector<T, A> i);
template<typename T, typename A> ostream& operator<< (ostream& out, list<T, A> i);
template<typename T, typename A> ostream& operator<< (ostream& out, deque<T, A> i);
template<typename T, typename U, typename F> ostream& operator<< (ostream& out, priority_queue<T, U, F> i);
template<typename T, typename F, typename A> ostream& operator<< (ostream& out, set<T, F, A> i);
template<typename T, typename F, typename A> ostream& operator<< (ostream& out, multiset<T, F, A> i);
template<typename T> ostream& operator<< (ostream& out, unordered_set<T> i);
template<typename T, typename U, typename F, typename A> ostream& operator<< (ostream& out, map<T, U, F, A> i);
template<typename T, typename U> ostream& operator<< (ostream& out, unordered_map<T, U> i);

template<typename T, typename U>
ostream& operator<< (ostream& out, pair<T, U> i) {
	out << '(' << i.first << ' ' << i.second << ')';
	return out;
}

template<typename T, size_t...I>
void __write_tuple(const T& i, index_sequence<I...>) {
	(..., (cout << (I ? " " : "") << get<I>(i)));
}

template<typename...T>
void __write_tuples(tuple<T...> i) {
	__write_tuple(i, make_index_sequence<sizeof...(T)>());
}

template<typename...T>
ostream& operator<< (ostream& out, tuple<T...> i) {
	out << '('; __write_tuples(i); out << ')';
	return out;
}

template<typename T, size_t U>
ostream& operator<< (ostream& out, array<T, U> i) {
	bool f = 0;
	out << '(';
	for (auto i : i) { if (f) out << ' '; out << i; f = 1; }
	out << ')';
	return out;
}

template<typename T, typename A>
ostream& operator<< (ostream& out, vector<T, A> i) {
	bool f = 0;
	out << '(';
	for (auto i : i) { if (f) out << ' '; out << i; f = 1; }
	out << ')';
	return out;
}

template<typename T, typename A>
ostream& operator<< (ostream& out, list<T, A> i) {
	bool f = 0;
	out << '(';
	for (auto i : i) { if (f) out << ' '; out << i; f = 1; }
	out << ')';
	return out;
}

template<typename T, typename A>
ostream& operator<< (ostream& out, deque<T, A> i) {
	bool f = 0;
	out << '(';
	for (auto i : i) { if (f) out << ' '; out << i; f = 1; }
	out << ')';
	return out;
}

template<typename T, typename U, typename F>
ostream& operator<< (ostream& out, priority_queue<T, U, F> i) {
	bool f = 0;
	out << '(';
	while (i.size()) { if (f) out << ' '; out << i.top(); i.pop(); f = 1; }
	out << ')';
	return out;
}

template<typename T, typename F, typename A>
ostream& operator<< (ostream& out, set<T, F, A> i) {
	bool f = 0;
	out << '(';
	for (auto i : i) { if (f) out << ' '; out << i; f = 1; }
	out << ')';
	return out;
}

template<typename T, typename F, typename A>
ostream& operator<< (ostream& out, multiset<T, F, A> i) {
	bool f = 0;
	out << '(';
	for (auto i : i) { if (f) out << ' '; out << i; f = 1; }
	out << ')';
	return out;
}

template<typename T>
ostream& operator<< (ostream& out, unordered_set<T> i) {
	bool f = 0;
	out << '(';
	for (auto i : i) { if (f) out << ' '; out << i; f = 1; }
	out << ')';
	return out;
}

template<typename T, typename U, typename F, typename A>
ostream& operator<< (ostream& out, map<T, U, F, A> i) {
	bool f = 0;
	out << '(';
	for (auto i : i) { if (f) out << ' '; out << i; f = 1; }
	out << ')';
	return out;
}

template<typename T, typename U>
ostream& operator<< (ostream& out, unordered_map<T, U> i) {
	bool f = 0;
	out << '(';
	for (auto i : i) { if (f) out << ' '; out << i; f = 1; }
	out << ')';
	return out;
}

ostream& operator<< (ostream& out, __int128 n) {
	if (n < 0) out << '-', n = -n;
	string s;
	do s.push_back(n % 10 | 48); while (n /= 10);
	reverse(s.begin(), s.end());
	out << s;
	return out;
}

template<typename ...Args>
void __dbg(string s, Args&&... x) {
	string _;
	cout << '(' << s << ") : ";
	(..., (cout << _ << x, _ = ", "));
	cout << endl;
}
/*}}}*/

auto naive = [](int n, int m, int k, auto v) {
	auto f = [&](int i, int j) {
		auto [x1, y1] = v[i];
		auto [x2, y2] = v[j];
		auto c1 = [&](int x, int y) {
			return x1 <= x && x <= x1 + m && y1 - k <= y && y <= y1 + m + k;
		};
		auto c2 = [&](int x, int y) {
			return x1 - k <= x && x <= x1 + m + k && y1 <= y && y <= y1 + m;
		};
		if (c1(x2, y2)) return 1;
		if (c1(x2, y2 + m)) return 1;
		if (c1(x2 + m, y2)) return 1;
		if (c1(x2 + m, y2 + m)) return 1;
		if (c2(x2, y2)) return 1;
		if (c2(x2, y2 + m)) return 1;
		if (c2(x2 + m, y2)) return 1;
		if (c2(x2 + m, y2 + m)) return 1;
		return 0;
	};
	vector c(n, 0);
	auto rec = [&](const auto& self, int cur) -> void {
		c[cur] = 1;
		for (int nxt = 0; nxt < n; nxt++) {
			if (c[nxt]) continue;
			if (!f(cur, nxt)) continue;
			self(self, nxt);
		}
	};
	rec(rec, 0);
	int ret = 0;
	for (int i = 0; i < n; i++) {
		if (c[i] == 0) continue;
		ret = max(ret, v[i][0] + v[i][1] + 2 * m);
	}
	return ret;
};

auto sol = [](int n, int m, int k, auto v) {
	vector adj(n, vector(0, 0));
	for (int iter = 0; iter < 8; iter++) {
		vector c(0, 0);
		for (int i = 0; i < n; i++) {
			c.push_back(v[i][0]);
			c.push_back(v[i][0] + m);
		}
		sort(c.begin(), c.end());
		c.erase(unique(c.begin(), c.end()), c.end());
		vector in(c.size(), vector(0, 0));
		vector out(c.size(), vector(0, 0));
		vector buc(c.size(), vector(0, 0));
		for (int i = 0; i < n; i++) {
			int p1 = lower_bound(c.begin(), c.end(), v[i][0]) - c.begin();
			int p2 = lower_bound(c.begin(), c.end(), v[i][0] + m) - c.begin();
			in[p1].push_back(i);
			out[p2].push_back(i);
			buc[p1].push_back(i);
		}
		set s{ pair(0, 0) }; s.clear();
		for (int x = 0; x < c.size(); x++) {
			for (int i : in[x]) {
				s.insert(pair(v[i][1] + m, i));
			}
			for (int i : buc[x]) {
				if (s.begin()->first >= v[i][1]) continue;
				auto it = prev(s.lower_bound(pair(v[i][1], -1)));
				if (it->first < v[i][1] - k) continue;
				int j = it->second;
				adj[i].push_back(j);
				adj[j].push_back(i);
			}
			for (int i : out[x]) {
				s.erase(pair(v[i][1] + m, i));
			}
		}
		for (int i = 0; i < n; i++) {
			swap(v[i][0], v[i][1]);
			v[i][1] = -v[i][1] - m;
			if (iter % 4 == 3) v[i][0] = -v[i][0] - m;
		}
	}
	vector c(n, 0);
	auto rec = [&](const auto& self, int cur) -> void {
		c[cur] = 1;
		for (int nxt : adj[cur]) {
			if (c[nxt]) continue;
			self(self, nxt);
		}
	};
	rec(rec, 0);
	int ret = 0;
	for (int i = 0; i < n; i++) {
		if (c[i] == 0) continue;
		ret = max(ret, v[i][0] + v[i][1] + 2 * m);
	}
	return ret;
};

// vgen /*{{{*/
auto gen_rand = [](int l, int r) {
	static mt19937 rd(0x814814);
	return uniform_int_distribution(l, r)(rd);
};

auto gen = [] {
	int lim = 50;
	int n = gen_rand(2, 20);
	int m = gen_rand(1, 4);
	int k = gen_rand(1, 2 * lim);
	vector v(1, array{ 0, 0 });
	while (v.size() < n) {
		int x = gen_rand(0, lim);
		int y = gen_rand(0, lim);
		int flag = 1;
		for (auto [px, py] : v) {
			auto c = [&](int x, int y) {
				return px <= x && x <= px + m && py <= y && y <= py + m;
			};
			if (c(x, y) || c(x, y + m) || c(x + m, y) || c(x + m, y + m)) flag = 0;
		}
		if (flag == 0) continue;
		v.push_back(array{ x, y });
	}
	return tuple(n, m, k, v);
};

auto test = [] {
	for (int iter = 0; iter < 100000; iter++) {
		if (iter % 1000 == 0) debug(iter);
		auto [n, m, k, v] = gen();
		auto r1 = naive(n, m, k, v);
		auto r2 = sol(n, m, k, v);
		if (r1 == r2) continue;
		debug(n, m, k);
		debug(v);
		debug(r1);
		debug(r2);
		break;
	}
	exit(0);
};
/*}}}*/

int main() {
	cin.tie(0)->sync_with_stdio(0);
	int n, m; cin >> n >> m;
	vector v(n, array{ 0, 0 });
	for (int i = 0; i < n; i++) cin >> v[i][0] >> v[i][1];
	int k; cin >> k;
	cout << naive(n, m, k, v) << '\n';
}

• Subtask 1: 0 / 1
• Subtask 2: 2 / 2
• Subtask 3: 0 / 3
• Subtask 4: 0 / 4
• Subtask 5: 0 / 4
• Subtask 6: 0 / 5