oj.uz

Submission #76486

# Submission time Handle Problem Language Result Execution time Memory
76486 2018-09-13T16:37:56 Z mfbalin Palinilap (COI16_palinilap) C++17
0 / 100
 1000 ms 3736 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1086 ms 376 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 37.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1068 ms 760 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 46.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1075 ms 3736 KB Time limit exceeded
2 Halted 0 ms 0 KB -