oj.uz

Submission #245378

# Submission time Handle Problem Language Result Execution time Memory
245378 2020-07-06T07:53:25 Z tonowak Palindromic Partitions (CEOI17_palindromic) C++14
100 / 100
 337 ms 20380 KB 
#include <bits/stdc++.h> // Tomasz Nowak
using namespace std;     // XIII LO Szczecin
using LL = long long;    // Poland
#define FOR(i, l, r) for(int i = (l); i <= (r); ++i)
#define REP(i, n) FOR(i, 0, (n) - 1)
template<class T> int size(T &&x) {
	return int(x.size());
}
template<class A, class B> ostream& operator<<(ostream &out, const pair<A, B> &p) {
	return out << '(' << p.first << ", " << p.second << ')';
}
template<class T> auto operator<<(ostream &out, T &&x) -> decltype(x.begin(), out) {
	out << '{';
	for(auto it = x.begin(); it != x.end(); ++it)
		out << *it << (it == prev(x.end()) ? "" : ", ");
	return out << '}';
}
void dump() {}
template<class T, class... Args> void dump(T &&x, Args... args) {
	cerr << x << ";  ";
	dump(args...);
}
#ifdef DEBUG
  struct Nl{~Nl(){cerr << '\n';}};
# define debug(x...) cerr << (strcmp(#x, "") ? #x ":  " : ""), dump(x), Nl(), cerr << ""
#else
# define debug(...) 0 && cerr
#endif
mt19937_64 rng(0);
int rd(int l, int r) {
	return uniform_int_distribution<int>(l, r)(rng);
}
// end of templates

struct Hashing {
	vector<int> ha, pw;
	int mod = 1e9 + 696969;
	int base;

	Hashing(string &str, int b = -1) {
		if(b == -1) base = 31;
		else base = b;

		int len = size(str);
		ha.resize(len + 1);
		pw.resize(len + 1, 1);
		REP(i, len) {
			ha[i + 1] = (LL(ha[i]) * base + str[i] - 'a' + 1) % mod;
			pw[i + 1] = (LL(pw[i]) * base) % mod;
		}
	}

	int operator()(int l, int r) {
		return ((ha[r + 1] - LL(ha[l]) * pw[r - l + 1]) % mod + mod) % mod;
	}
};

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

	int t;
	cin >> t;
	while(t --> 0) {
		string s;
		cin >> s;
		const int n = size(s);
		Hashing hash(s);

		int answer = 0;
		int L = 0, R = n - 1;
		while(L < R) {
			debug(L, R);
			bool found = false;
			FOR(len, 1, (R - L + 1) / 2)
				if(hash(L, L + len - 1) == hash(R - len + 1, R)) {
					L += len;
					R -= len;
					answer += 2;
					found = true;
					break;
				}
			if(not found)
				break;
		}
		if(L <= R)
			answer += 1;
		cout << answer << '\n';
	}
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 4 ms 384 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 4 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 5 ms 384 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 4 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 8 ms 512 KB Output is correct
11 Correct 6 ms 512 KB Output is correct
12 Correct 7 ms 512 KB Output is correct
13 Correct 7 ms 512 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 4 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 8 ms 512 KB Output is correct
11 Correct 6 ms 512 KB Output is correct
12 Correct 7 ms 512 KB Output is correct
13 Correct 7 ms 512 KB Output is correct
14 Correct 315 ms 20380 KB Output is correct
15 Correct 178 ms 14808 KB Output is correct
16 Correct 337 ms 18940 KB Output is correct
17 Correct 161 ms 11072 KB Output is correct