제출 #994985

#제출 시각아이디문제언어결과실행 시간메모리
994985xnqs회문 (APIO14_palindrome)C++17
8 / 100
1058 ms24548 KiB
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <utility>
#include <algorithm>
#include <cstdint>
#include <unordered_map>
 
std::string str;
uint64_t p31[300005] = {1, 31};
uint64_t pfx_hash[300005];
uint64_t pfx_hash_rev[300005];
std::unordered_map<int,int> vis[300005];
std::unordered_map<int,int> freq;
 
void preprocess() {
	for (int i = 2; i < 300005; i++) {
		p31[i] = p31[i-1]*31;
	}
}
 
inline uint64_t hquery(uint64_t* pfx_hash, int l, int r) {
	uint64_t ret = pfx_hash[r];
	if (l-1>=0) {
		ret -= pfx_hash[l-1]*p31[r-l+1];
	}
	return ret;
}
 
inline bool is_palindrome(int l, int r) {
	return hquery(pfx_hash,l,r) == hquery(pfx_hash_rev,str.size()-r-1,str.size()-l-1);
}
 
void bfs() {
	std::queue<std::pair<int,int>> q;
	for (int i = 0; i < str.size(); i++) {
		vis[i][i] = 1;
		freq[hquery(pfx_hash,i,i)] += 1;
		q.emplace(i,i);
	}
 
	int64_t ret = 0;
	while (!q.empty()) {
		auto [l, r] = q.front();
		q.pop();
 
		//std::cerr << l << " " << r << ", " << freq[hquery(pfx_hash,l,r)] << "\n";
 
		ret = std::max(ret,static_cast<int64_t>(1LL*(r-l+1)*freq[hquery(pfx_hash,l,r)]));
 
		int len = r-l+1;
		int le = l+len;
		int ri = le+len-1;
		if (ri<str.size()&&!vis[l][ri]&&hquery(pfx_hash,l,r)==hquery(pfx_hash_rev,str.size()-ri-1,str.size()-le-1)) {
			freq[hquery(pfx_hash,l,ri)] += 1;
			vis[l][ri] = 1;
			q.emplace(l,ri);
		}
 
		le = l+len+1;
		ri = le+len-1;
		if (ri<str.size()&&!vis[l][ri]&&hquery(pfx_hash,l,r)==hquery(pfx_hash_rev,str.size()-ri-1,str.size()-le-1)) {
			freq[hquery(pfx_hash,l,ri)] += 1;
			vis[l][ri] = 1;
			q.emplace(l,ri);
		}
 
		le = l-len;
		ri = le+len-1;
		if (le>=0&&!vis[le][r]&&hquery(pfx_hash,le,ri)==hquery(pfx_hash_rev,str.size()-r-1,str.size()-l-1)) {
			freq[hquery(pfx_hash,le,r)] += 1;
			vis[le][r] = 1;
			q.emplace(le,r);
		}
		
		le = l-len-1;
		ri = le+len-1;
		if (le>=0&&!vis[le][r]&&hquery(pfx_hash,le,ri)==hquery(pfx_hash_rev,str.size()-r-1,str.size()-l-1)) {
			freq[hquery(pfx_hash,le,r)] += 1;
			vis[le][r] = 1;
			q.emplace(le,r);
		}
	}
 
	std::cout << ret << "\n";
}
 
int main() {
	preprocess();
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(NULL);
	std::cout.tie(NULL);
 
	std::cin >> str;
	for (int i = 0; i < str.size(); i++) {
		pfx_hash[i] = ((i-1>=0) ? pfx_hash[i-1]*31 : 0);
		pfx_hash[i] += str[i]-'a'+1;
		pfx_hash_rev[i] = ((i-1>=0) ? pfx_hash_rev[i-1]*31 : 0);
		pfx_hash_rev[i] += str[str.size()-i-1]-'a'+1;
		//std::cout << pfx_hash[i] << " " << pfx_hash_rev[i] << "\n";
	}

	int64_t ret = 0;
	for (int len = 1; len <= str.size(); len++) {
		std::unordered_map<int,int> map;
		for (int l = 0; l+len-1 < str.size(); l++) {
			int r = l+len-1;
			if (is_palindrome(l,r)) {
				++map[hquery(pfx_hash,l,r)];
				ret = std::max(ret,static_cast<int64_t>(1LL*len*map[hquery(pfx_hash,l,r)]));
			}
		}
	}

	std::cout << ret << "\n";
}

컴파일 시 표준 에러 (stderr) 메시지

palindrome.cpp: In function 'void bfs()':
palindrome.cpp:37:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |  for (int i = 0; i < str.size(); i++) {
      |                  ~~^~~~~~~~~~~~
palindrome.cpp:55:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |   if (ri<str.size()&&!vis[l][ri]&&hquery(pfx_hash,l,r)==hquery(pfx_hash_rev,str.size()-ri-1,str.size()-le-1)) {
      |       ~~^~~~~~~~~~~
palindrome.cpp:63:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |   if (ri<str.size()&&!vis[l][ri]&&hquery(pfx_hash,l,r)==hquery(pfx_hash_rev,str.size()-ri-1,str.size()-le-1)) {
      |       ~~^~~~~~~~~~~
palindrome.cpp: In function 'int main()':
palindrome.cpp:96:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   96 |  for (int i = 0; i < str.size(); i++) {
      |                  ~~^~~~~~~~~~~~
palindrome.cpp:105:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  105 |  for (int len = 1; len <= str.size(); len++) {
      |                    ~~~~^~~~~~~~~~~~~
palindrome.cpp:107:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  107 |   for (int l = 0; l+len-1 < str.size(); l++) {
      |                   ~~~~~~~~^~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...