test/ABC125-C.test.cpp

• View this file on GitHub
• Last update: 2023-03-06 15:21:58+09:00
• Problem: https://onlinejudge.u-aizu.ac.jp/courses/lesson/2/ITP1/1/ITP1_1_A
• Link: https://atcoder.jp/contests/abc125/submissions/39483132

Depends on

• sparseTable ( $x \oplus x\ =\ x$ の区間クエリ解答 ) (src/dataStructure/sparseTable.hpp)
• gcdStructure (Sparse Table) (src/utility/sparseTable/gcdStructure.hpp)

Code

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

#include "../src/dataStructure/sparseTable.hpp"
#include "../src/utility/sparseTable/gcdStructure.hpp"

#include <vector>
#include <iostream>
#include <algorithm>
#include <numeric>

int main() {
	// int N; std::cin >> N;
	// std::vector A(N, 0);
	// for (auto& a : A) {
	// 	std::cin >> a;
	// }
	// zawa::sparseTable<zawa::gcdStructure<int>> S(A);
	// int ans = S.query(0, N);
	// ans = std::max(ans, S.query(1, N));
	// for (int i = 0 ; i < N - 1 ; i++) {
	// 	ans = std::max(ans, std::gcd(S.query(0, i), S.query(i + 1, N)));
	// }
	// ans = std::max(ans, S.query(0, N - 1));
	// std::cout << ans << std::endl;

	std::cout << "Hello World" << std::endl;
}

/*
 * AtCoder Beginner Contest 125 - C GCD on Blackboard
 * https://atcoder.jp/contests/abc125/submissions/39483132
 */

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

#line 2 "src/dataStructure/sparseTable.hpp"

#include <vector>
#include <cassert>

namespace zawa {

template <class structure>
class sparseTable {
private:
	using T = typename structure::valueType;
	std::vector<int> L;
	std::vector<std::vector<T>> dat;

public:

	sparseTable(const std::vector<T>& A) : L(A.size() + 1, 0) {
		for (int i = 1 ; i < (int)L.size() ; i++) {
			L[i] = L[i - 1] + (i >> (L[i - 1] + 1));
		}
		dat = std::vector(L.back() + 1, A);
		for (int i = 1 ; i < (int)dat.size() ; i++) {
			int pt = (1 << i);
			for (int j = 0 ; j + pt - 1 < (int)dat[i].size() ; j++) {
				dat[i][j] = structure::operation(dat[i - 1][j], dat[i - 1][j + (pt >> 1)]);
			}
		}
	}

	T query(int l, int r) {
		assert(0 <= l and l < (int)dat[0].size());
		assert(l <= r and r <= (int)dat[0].size());
		int now = L[r - l];
		return structure::operation(dat[now][l], dat[now][r - (1 << now)]);
	}

	inline std::vector<std::vector<T>> _dat() const {
		return dat;
	}

};

} // namespace zawa
#line 1 "src/utility/sparseTable/gcdStructure.hpp"
#include <numeric>

namespace zawa {

template <class T>
struct gcdStructure {
	using valueType = T;
	static valueType operation(const valueType& a, const valueType& b) {
		return std::gcd(a, b);
	}
};

} // namespace zawa
#line 5 "test/ABC125-C.test.cpp"

#line 7 "test/ABC125-C.test.cpp"
#include <iostream>
#include <algorithm>
#line 10 "test/ABC125-C.test.cpp"

int main() {
	// int N; std::cin >> N;
	// std::vector A(N, 0);
	// for (auto& a : A) {
	// 	std::cin >> a;
	// }
	// zawa::sparseTable<zawa::gcdStructure<int>> S(A);
	// int ans = S.query(0, N);
	// ans = std::max(ans, S.query(1, N));
	// for (int i = 0 ; i < N - 1 ; i++) {
	// 	ans = std::max(ans, std::gcd(S.query(0, i), S.query(i + 1, N)));
	// }
	// ans = std::max(ans, S.query(0, N - 1));
	// std::cout << ans << std::endl;

	std::cout << "Hello World" << std::endl;
}

/*
 * AtCoder Beginner Contest 125 - C GCD on Blackboard
 * https://atcoder.jp/contests/abc125/submissions/39483132
 */

Back to top page