oj.uz

Submission #617162

# Submission time Handle Problem Language Result Execution time Memory
617162 2022-08-01T09:11:32 Z Zanite Palinilap (COI16_palinilap) C++17
17 / 100
 1000 ms 1104 KB 
#include <bits/stdc++.h>
using namespace std;

using ll	= long long;

const int maxN	= 5005;

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll getRand(ll l, ll r) {return uniform_int_distribution<ll>(l, r)(rng);}

const ll mod	= 1049433169;
ll madd(ll x, ll y) {x += y; if (x >= mod) x -= mod; return x;}
ll mmul(ll x, ll y) {x *= y; x %= mod; return x;}
ll modexp(ll x, ll y) {
	if (!x) return 0; if (!y) return 1;
	ll t = modexp(x, y >> 1);
	return mmul(t, mmul(t, ((y & 1ll) ? x : 1)));
}

ll key;
ll kpow[maxN], invkpow[maxN];

ll n;

void precomp() {
	key = getRand(1e5, 2e5);

	kpow[0] = invkpow[0] = 1;
	kpow[1] = key, invkpow[1] = modexp(key, mod-2);
	for (ll i = 1; i <= n; i++) {
		kpow[i] = mmul(kpow[i-1], kpow[1]);
		invkpow[i] = mmul(invkpow[i-1], invkpow[1]);
	}
}

struct HashString {
	ll fwd, bwd, len;

	HashString() {fwd = bwd = len = 0;}
	HashString(char c) {
		fwd = bwd = c - 'a';
		len = 1;
	}

	HashString operator + (const HashString &other) const {
		HashString ret = HashString();
		ret.fwd = madd(fwd, mmul(other.fwd, kpow[len]));
		ret.bwd = madd(mmul(bwd, kpow[other.len]), other.bwd);
		ret.len = len + other.len;
		return ret;
	}

	bool isPalindrome() {return (fwd == bwd);}
};

string S;

ll compute(string &str) {
	ll ret = 0;
	for (int i = 1; i <= n; i++) {
		HashString H = HashString();
		for (int j = i; j <= n; j++) {
			H = H + HashString(str[j]);
			ret += H.isPalindrome();
		}
	}
	//cout << "compute(" << str << ") = " << ret << '\n';
	return ret;
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL);

	cin >> S;
	n = S.length();
	S = "#" + S;
	precomp();

	ll ans = 0;
	for (int i = 1; i <= n; i++) {
		for (char c = 'a'; c <= 'z'; c++) {
			string T = S;
			T[i] = c;
			ans = max(ans, compute(T));
		}
	}
	cout << ans << '\n';
}

Compilation message

palinilap.cpp: In function 'll modexp(ll, ll)':
palinilap.cpp:15:2: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   15 |  if (!x) return 0; if (!y) return 1;
      |  ^~
palinilap.cpp:15:20: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   15 |  if (!x) return 0; if (!y) return 1;
      |                    ^~

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 212 KB Output is correct
2 Correct 79 ms 212 KB Output is correct
3 Correct 81 ms 308 KB Output is correct
4 Correct 82 ms 312 KB Output is correct
5 Correct 84 ms 320 KB Output is correct

Subtask #2
0 / 37.0

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

Subtask #3
0 / 46.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 1104 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -