oj.uz

Submission #80154

# Submission time Handle Problem Language Result Execution time Memory
80154 2018-10-19T08:18:04 Z aminra Palindromic Partitions (CEOI17_palindromic) C++14
60 / 100
 16 ms 10820 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
const int MOD = (int)1e9 + 7;
const int MAXN = (int)2e5 + 7;
const int infint = (int)1e9;
ll T, h[MAXN], pwr[MAXN], base = 37;
string s;
void hsh()
{
	h[0] = (s[0] - 'a' + 1);
	for (int i = 1; i < s.size(); i++)
		h[i] = (h[i - 1] * base % MOD + (s[i] - 'a' + 1)) % MOD;
}
ll get(int l, int r)
{
	if(l > r)
		return -1;
	ll ans = h[r];
	if(l)
		ans -= h[l - 1] * pwr[r - l + 1] % MOD, ans = (ans + MOD) % MOD;
	return ans;
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	pwr[0] = 1;
	for (int i = 1; i < MAXN; i++)
		pwr[i] = pwr[i - 1] * base % MOD;
	cin >> T;
	for (int i = 0; i < T; i++)
	{
		cin >> s;
		hsh();
		ll cur = 0, ans = 0, c = 1;
		for (int i = 0; i < s.size(); i++)
			if(i < s.size() - i - 1 && get(cur, i) == get(s.size() - i - 1, s.size() - cur - 1))
			{
				ans += 2, cur = i + 1;
				if(i == s.size() - i - 2)
					c = 0;
			}
		cout << ans + c << "\n";
	}
}

Compilation message

palindromic.cpp: In function 'void hsh()':
palindromic.cpp:13:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 1; i < s.size(); i++)
                  ~~^~~~~~~~~~
palindromic.cpp: In function 'int main()':
palindromic.cpp:38:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < s.size(); i++)
                   ~~^~~~~~~~~~
palindromic.cpp:39:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if(i < s.size() - i - 1 && get(cur, i) == get(s.size() - i - 1, s.size() - cur - 1))
       ~~^~~~~~~~~~~~~~~~~~
palindromic.cpp:42:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if(i == s.size() - i - 2)
        ~~^~~~~~~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

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

Subtask #2
20.0 / 20.0

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

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1912 KB Output is correct
2 Correct 4 ms 2096 KB Output is correct
3 Correct 4 ms 2096 KB Output is correct
4 Correct 4 ms 2096 KB Output is correct
5 Correct 4 ms 2188 KB Output is correct
6 Correct 4 ms 2188 KB Output is correct
7 Correct 4 ms 2188 KB Output is correct
8 Correct 4 ms 2188 KB Output is correct
9 Correct 4 ms 2264 KB Output is correct
10 Correct 7 ms 2356 KB Output is correct
11 Correct 5 ms 2584 KB Output is correct
12 Correct 7 ms 2584 KB Output is correct
13 Correct 6 ms 2648 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1912 KB Output is correct
2 Correct 4 ms 2096 KB Output is correct
3 Correct 4 ms 2096 KB Output is correct
4 Correct 4 ms 2096 KB Output is correct
5 Correct 4 ms 2188 KB Output is correct
6 Correct 4 ms 2188 KB Output is correct
7 Correct 4 ms 2188 KB Output is correct
8 Correct 4 ms 2188 KB Output is correct
9 Correct 4 ms 2264 KB Output is correct
10 Correct 7 ms 2356 KB Output is correct
11 Correct 5 ms 2584 KB Output is correct
12 Correct 7 ms 2584 KB Output is correct
13 Correct 6 ms 2648 KB Output is correct
14 Runtime error 16 ms 10820 KB Execution killed with signal 11 (could be triggered by violating memory limits)
15 Halted 0 ms 0 KB -