test/ABC203-E.test.cpp

• View this file on GitHub
• Last update: 2023-01-21 19:38:49+09:00
• Problem: https://onlinejudge.u-aizu.ac.jp/courses/lesson/2/ITP1/1/ITP1_1_A
• Link: https://atcoder.jp/contests/abc203/submissions/38188430

Depends on

• accum2d (二次元累積和) (src/dataStructure/accum2d.hpp)
• binary-seach (整数二分探索) (src/template/binary-search.hpp)

Code

#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/lesson/2/ITP1/1/ITP1_1_A"

#include "../src/template/binary-search.hpp"
#include "../src/dataStructure/accum2d.hpp"

#include <iostream>
#include <vector>

int main() {
	// int N, K; std::cin >> N >> K;
	// std::vector A(N, std::vector(N, 0));
	// for (auto& a : A) {
	// 	for (auto& x : a) {
	// 		std::cin >> x;
	// 	}
	// }
	// auto f = [&](int p) -> bool {
	// 	std::vector B(N, std::vector(N, 0));
	// 	for (int i = 0 ; i < N ; i++) {
	// 		for (int j = 0 ; j < N ; j++) {
	// 			B[i][j] = (A[i][j] <= p);
	// 		}
	// 	}
	// 	zawa::accum2d S(B);
	// 	bool res = false;
	// 	for (int i = 0 ; i + K <= N ; i++) {
	// 		for (int j = 0 ; j + K <= N ; j++) {
	// 			res |= S.sum(i, j, i + K, j + K) >= (K * K + 1) / 2;
	// 		}
	// 	}
	// 	return res;
	// };
	// std::cout << zawa::binary_search((int)1e9, -1, f) << std::endl;
	
	std::cout << "Hello World" << std::endl;
}

/*
 * AtCoder Beginner Contest 203 - D Pond
 * https://atcoder.jp/contests/abc203/submissions/38188430
 */

#line 1 "test/ABC203-E.test.cpp"
#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/lesson/2/ITP1/1/ITP1_1_A"

#line 2 "src/template/binary-search.hpp"

#include <cmath>

namespace zawa {

template <class T, class F>
T binary_search(T ok, T ng, const F& f) {
	while (std::abs(ok - ng) > 1) {
		T mid = ((ok + ng) >> 1);
		if (f(mid)) {
			ok = mid;
		}
		else {
			ng = mid;
		}
	}
	return ok;
}

}
#line 2 "src/dataStructure/accum2d.hpp"

#include <vector>
#include <utility>

namespace zawa {

template <class T>
struct accum2d : std::vector<std::vector<T>> {
	accum2d() {
		(*this).push_back({ T() });
	}
	accum2d(const std::vector<std::vector<T>>& A) : std::vector<std::vector<T>>(A.size() + 1, std::vector<T>(A[0].size() + 1, T())) {
		for (std::size_t i = 0 ; i < A.size() ; i++) {
			for (std::size_t j = 0 ; j < A[i].size() ; j++) {
				(*this)[i + 1][j + 1] = (*this)[i][j + 1] + (*this)[i + 1][j] - (*this)[i][j] + A[i][j];
			}
		}
	}
	T sum(std::size_t y1, std::size_t x1, std::size_t y2, std::size_t x2) {
		return (*this)[y2][x2] - (*this)[y1][x2] - (*this)[y2][x1] + (*this)[y1][x1];
	}
	T sum(std::pair<std::size_t, std::size_t> p1, std::pair<std::size_t, std::size_t> p2) {
		return sum(p1.first, p1.second, p2.first, p2.second);
	}
};

} // namespace zawa
#line 5 "test/ABC203-E.test.cpp"

#include <iostream>
#line 8 "test/ABC203-E.test.cpp"

int main() {
	// int N, K; std::cin >> N >> K;
	// std::vector A(N, std::vector(N, 0));
	// for (auto& a : A) {
	// 	for (auto& x : a) {
	// 		std::cin >> x;
	// 	}
	// }
	// auto f = [&](int p) -> bool {
	// 	std::vector B(N, std::vector(N, 0));
	// 	for (int i = 0 ; i < N ; i++) {
	// 		for (int j = 0 ; j < N ; j++) {
	// 			B[i][j] = (A[i][j] <= p);
	// 		}
	// 	}
	// 	zawa::accum2d S(B);
	// 	bool res = false;
	// 	for (int i = 0 ; i + K <= N ; i++) {
	// 		for (int j = 0 ; j + K <= N ; j++) {
	// 			res |= S.sum(i, j, i + K, j + K) >= (K * K + 1) / 2;
	// 		}
	// 	}
	// 	return res;
	// };
	// std::cout << zawa::binary_search((int)1e9, -1, f) << std::endl;
	
	std::cout << "Hello World" << std::endl;
}

/*
 * AtCoder Beginner Contest 203 - D Pond
 * https://atcoder.jp/contests/abc203/submissions/38188430
 */

Back to top page