Submission #76486

#	Time	Username	Problem	Language	Result	Execution time	Memory
76486		mfbalin	Palinilap (COI16_palinilap)	C++17	0 / 100	1086 ms	3736 KiB

palinilap

#include <iostream>
#include <string>
#include <vector>
#include <cinttypes>
using namespace std;

int main(int argc, char *argv[]) {
	ios::sync_with_stdio(false);
	string s;
	cin >> s;
	s = string("&") + s;
	vector<uint64_t> h1(s.size());
	auto h2 = h1;
	h1[0] = 0;
	h2[s.size() - 1] = 0;
	auto h31 = h1;
	h31[0] = 1;
	for(int i = 1; i < s.size(); i++) {
		h31[i] = h31[i - 1] * 31;
		h1[i] = h1[i - 1] * 31 + (s[i] - 'a');
		h2[s.size() - 1 - i] = h2[s.size() - i] * 31 + (s[s.size() - 1 - i] - 'a');
	}
	auto fwd = [&](int i, int j) -> uint64_t {
		return h1[j] - h1[i - 1] * h31[j - i + 1];
	};
	auto rwd = [&](int i, int j) -> uint64_t {
		return h2[i] - h2[j + 1] * h31[j - i + 1];
	};
	vector<int> o(s.size());
	for(int i = 1; i < s.size(); i++) {
		int l = 0, r = min(i - 1, (int)s.size() - 1 - i);
		while(l < r) {
			int m = (l + r) / 2;
			if(fwd(i - m, i) == rwd(i, i + m))
				l = m;
			else
				r = m - 1;
		}
		o[i] = l;
	}
	vector<int> e(s.size() - 1);//i corresponds to the right of the i'th letter
	for(int i = 1; i < s.size() - 1; i++) {
		int l = 0, r = min(i, (int)s.size() - 1 - i);
		while(l < r) {
			int m = (l + r) / 2;
			if(fwd(i - m + 1, i) == rwd(i + 1, i + m))
				l = m;
			else
				r = m - 1;
		}
		e[i] = l;
	}
	
	return 0;
}

Compilation message (stderr)

palinilap.cpp: In function 'int main(int, char**)':
palinilap.cpp:18:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 1; i < s.size(); i++) {
                 ~~^~~~~~~~~~
palinilap.cpp:30:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 1; i < s.size(); i++) {
                 ~~^~~~~~~~~~
palinilap.cpp:42:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 1; i < s.size() - 1; i++) {
                 ~~^~~~~~~~~~~~~~

• Subtask 1: 0 / 17
• Subtask 2: 0 / 37
• Subtask 3: 0 / 46