oj.uz

Submission #1095043

# Submission time Handle Problem Language Result Execution time Memory
1095043 2024-10-01T07:54:55 Z vjudge1 Palindromic Partitions (CEOI17_palindromic) C++17
100 / 100
 184 ms 24472 KB 
// Source: https://usaco.guide/general/io

#include <bits/stdc++.h>
#define int long long 
using namespace std;

const int base = 31;
const int MOD = 1000000003;
const int maxn = 1000111;

using namespace std;

int POW[maxn], Hash[maxn], len;
string s;

int getHash(int i,int j) {
    return (Hash[j] - Hash[i - 1] * POW[j - i + 1] + MOD * MOD) % MOD;
}

void solve(){
	cin >> s;
	int n = s.size();
	s = ' ' + s;
    for (int i = 1; i <= n; i++)
        Hash[i] = (Hash[i - 1] * base + s[i] - 'a' + 1) % MOD;
	
	int l1 = 1, r1 = 1, l2 = n, r2 = n;
	int ans = 0;
	while(r1 <= r2){
		if(getHash(l1, r1) == getHash(l2, r2)){
			if(r1 < l2){
				ans += 2;
				l1 = r1 + 1;
				r1++;
				r2 = l2 - 1;
				l2--;
			} else {
				ans++;
				break;
			}
		} else {
			r1++;
			l2--;
		}
	}
	cout << ans << '\n';
}
main() {
    POW[0] = 1;
    for (int i = 1; i <= 1000000; i++)
        POW[i] = (POW[i - 1] * base) % MOD;

	int test; cin >> test;
	while(test--){
		solve();
	}
}

Compilation message

palindromic.cpp:48:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   48 | main() {
      | ^~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 8024 KB Output is correct
2 Correct 7 ms 8280 KB Output is correct
3 Correct 7 ms 8284 KB Output is correct
4 Correct 7 ms 8028 KB Output is correct
5 Correct 6 ms 8092 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 8024 KB Output is correct
2 Correct 7 ms 8280 KB Output is correct
3 Correct 7 ms 8284 KB Output is correct
4 Correct 7 ms 8028 KB Output is correct
5 Correct 6 ms 8092 KB Output is correct
6 Correct 7 ms 8028 KB Output is correct
7 Correct 7 ms 8076 KB Output is correct
8 Correct 6 ms 8024 KB Output is correct
9 Correct 7 ms 8024 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 8024 KB Output is correct
2 Correct 7 ms 8280 KB Output is correct
3 Correct 7 ms 8284 KB Output is correct
4 Correct 7 ms 8028 KB Output is correct
5 Correct 6 ms 8092 KB Output is correct
6 Correct 7 ms 8028 KB Output is correct
7 Correct 7 ms 8076 KB Output is correct
8 Correct 6 ms 8024 KB Output is correct
9 Correct 7 ms 8024 KB Output is correct
10 Correct 9 ms 8284 KB Output is correct
11 Correct 8 ms 8284 KB Output is correct
12 Correct 8 ms 8284 KB Output is correct
13 Correct 8 ms 8392 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 8024 KB Output is correct
2 Correct 7 ms 8280 KB Output is correct
3 Correct 7 ms 8284 KB Output is correct
4 Correct 7 ms 8028 KB Output is correct
5 Correct 6 ms 8092 KB Output is correct
6 Correct 7 ms 8028 KB Output is correct
7 Correct 7 ms 8076 KB Output is correct
8 Correct 6 ms 8024 KB Output is correct
9 Correct 7 ms 8024 KB Output is correct
10 Correct 9 ms 8284 KB Output is correct
11 Correct 8 ms 8284 KB Output is correct
12 Correct 8 ms 8284 KB Output is correct
13 Correct 8 ms 8392 KB Output is correct
14 Correct 184 ms 22972 KB Output is correct
15 Correct 106 ms 20764 KB Output is correct
16 Correct 177 ms 24472 KB Output is correct
17 Correct 104 ms 16144 KB Output is correct