Submission #368274

#	Time	Username	Problem	Language	Result	Execution time	Memory
368274		TruaShamu	Palinilap (COI16_palinilap)	C++11	0 / 100	1 ms	364 KiB

palinilap

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>

#pragma warning(disable : 4996)

const int maxn = 100005;
const long long base = 131, mod = 1000000007;

int n, mx, mx_id;
long long inc[maxn][26], dec[maxn], c1[maxn], c2[maxn], ori_ans, delta_ans;
char a[maxn];
long long poww[maxn], hash1[maxn], hash2[maxn];

inline long long get_hash1(int left, int right) {
	return ((hash1[right] - hash1[left - 1] * poww[right - left + 1]) % mod + mod) % mod;
}
inline long long get_hash2(int left, int right) {
	return ((hash2[left] - hash2[right + 1] * poww[right - left + 1]) % mod + mod) % mod;
}
inline void incc(int left, int right) {
	++c1[left];
	c1[right + 1] -= (right - left + 2);
	c1[right + 2] += (right - left + 1);
}
inline void decc(int left, int right) {
	++c1[right + 2];
	c1[left] += (right - left + 1);
	c1[left + 1] -= (right - left + 2);
}

int main(void) {
	freopen("palinilap.in", "r", stdin);
	freopen("palinilap.out", "w", stdout);
	scanf("%s", a + 1);
	n = strlen(a + 1);
	a[0] = '$';

	poww[0] = 1ull;
	for (int i = 1; i <= n; ++i) {
		poww[i] = poww[i - 1] * base % mod;
	}
	for (int i = 1; i <= n; ++i) {
		hash1[i] = (hash1[i - 1] * base + a[i]) % mod;
	}
	for (int i = n; i; --i) {
		hash2[i] = (hash2[i + 1] * base + a[i]) % mod;
	}

	int left, right, mid;
	for (int i = 1; i < n; ++i) {
		for (int j = i; j < i + 2; ++j) {
			left = 0;
			right = std::min(i, n - j + 1);
			while (left < right) {
				mid = (left + right + 1) >> 1;
				if (get_hash1(i - mid + 1, i) == get_hash2(j, j + mid - 1)) {
					left = mid;
				}
				else {
					right = mid - 1;
				}
			}
			ori_ans += (long long)left;

			if (left > 0) {
				if (i == j) {
					incc(i - left + 1, i - 1);
					decc(j + 1, j + left - 1);
				}
				else {
					incc(i - left + 1, i);
					decc(j, j + left - 1);
				}
			}

			if (i - left <= 0 || j + left > n) {
				continue;
			}
			long long& tem1 = inc[i - left][a[j + left] - 'a'];
			long long& tem2 = inc[j + left][a[i - left] - 'a'];
			int ori_left = left;
			right = std::min(i - left - 1, n - j - left);
			left = 0;
			while (left < right) {
				mid = (left + right + 1) >> 1;
				if (get_hash1(i - ori_left - mid, i - ori_left - 1) == get_hash2(j + ori_left + 1, j + ori_left + mid)) {
					left = mid;
				}
				else {
					right = mid - 1;
				}
			}
			tem1 += left + 1;
			tem2 += left + 1;
		}
	}

	for (int i = 1; i <= n; ++i) {
		c2[i] = c2[i - 1] + c1[i];
		dec[i] = dec[i - 1] + c2[i];
	}

	for (int i = 1; i <= n; ++i) {
		for (int j = 0; j < 26; ++j) {
			if (j == a[i] - 'a') {
				continue;
			}
			delta_ans = std::max(delta_ans, inc[i][j] - dec[i]);
		}
	}
	++ori_ans;
	 printf("%I64d\n", ori_ans + delta_ans);
	//std::cout << ori_ans + delta_ans << std::endl;
	return 0;
}

Compilation message (stderr)

palinilap.cpp:6: warning: ignoring #pragma warning  [-Wunknown-pragmas]
    6 | #pragma warning(disable : 4996)
      | 
palinilap.cpp: In function 'int main()':
palinilap.cpp:114:15: warning: format '%d' expects argument of type 'int', but argument 2 has type 'long long int' [-Wformat=]
  114 |   printf("%I64d\n", ori_ans + delta_ans);
      |           ~~~~^     ~~~~~~~~~~~~~~~~~~~
      |               |             |
      |               int           long long int
      |           %I64lld
palinilap.cpp:34:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   34 |  freopen("palinilap.in", "r", stdin);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
palinilap.cpp:35:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   35 |  freopen("palinilap.out", "w", stdout);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
palinilap.cpp:36:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   36 |  scanf("%s", a + 1);
      |  ~~~~~^~~~~~~~~~~~~

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