제출 #993589

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
993589		xnqs	회문 (APIO14_palindrome)	C++17	0 / 100	155 ms	83476 KiB

palindrome

#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <utility>
#include <algorithm>
#include <cstdint>
#include <unordered_map>

std::string str;
uint32_t p31[300005] = {1, 31};
uint32_t pfx_hash[300005];
uint32_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 uint32_t hquery(uint32_t* pfx_hash, int l, int r) {
	uint32_t ret = pfx_hash[r];
	if (l-1>=0) {
		ret -= pfx_hash[l-1]*p31[r-l+1];
	}
	return ret;
}

inline bool 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)]<=550) {
			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)]<=550) {
			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)]<=550) {
			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)]<=550) {
			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";
	}

	bfs();
}

컴파일 시 표준 에러 (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)&&freq[hquery(pfx_hash,l,ri)]<=550) {
      |       ~~^~~~~~~~~~~
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)&&freq[hquery(pfx_hash,l,ri)]<=550) {
      |       ~~^~~~~~~~~~~
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++) {
      |                  ~~^~~~~~~~~~~~

• Subtask 1: 0 / 8
• Subtask 2: 0 / 15
• Subtask 3: 0 / 24
• Subtask 4: 0 / 26
• Subtask 5: 0 / 27