oj.uz

Submission #83421

# Submission time Handle Problem Language Result Execution time Memory
83421 2018-11-07T13:50:29 Z Tusk Palindromic Partitions (CEOI17_palindromic) C++14
100 / 100
 104 ms 42784 KB 
#include <bits/stdc++.h>

#define pii pair<int, int>
#define x first
#define y second

using namespace std;

const int N = 1e6+5;

pii add(pii a, pii b) { return pii(a.x + b.x, a.y + b.y); }
pii sub(pii a, pii b) { return pii(a.x - b.x, a.y - b.y); }
pii mul(pii a, pii b) { return pii(a.x * b.x, a.y * b.y); }

int t;
char A[N];
pii iden(23, 29), hpow[N], dp[N];

int main() {
	hpow[0] = pii(1, 1);
	for(int i = 1; i < N; i++) hpow[i] = mul(hpow[i-1], iden);
	scanf("%d", &t);
	while(t--) {
		int ans = 0;
		scanf(" %s", A+1);
		hpow[0] = pii(0, 0);
		int n = strlen(A+1);
		for(int i = 1; i <= n; i++) dp[i] = add(mul(dp[i-1], iden), pii(A[i], A[i]));
		int sz = 0;
		for(int i = 1, j = n; i <= j; i++, j--) {
			++sz;
			int l = i-sz, r = j+sz-1;
			pii lhs = sub(dp[i], mul(dp[l], hpow[sz]));
			pii rhs = sub(dp[r], mul(dp[j-1], hpow[sz]));
			if(lhs == rhs && i != j) ans += 2, sz = 0;
			if(lhs == rhs && i == j) ++ans, sz = 0;
		}
		if(sz) ++ans;
		printf("%d\n", ans);
	}

	return 0;
}

Compilation message

palindromic.cpp: In function 'int main()':
palindromic.cpp:22:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &t);
  ~~~~~^~~~~~~~~~
palindromic.cpp:25:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf(" %s", A+1);
   ~~~~~^~~~~~~~~~~~

Subtask #1
15.0 / 15.0

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 8184 KB Output is correct
2 Correct 9 ms 8184 KB Output is correct
3 Correct 9 ms 8336 KB Output is correct
4 Correct 9 ms 8336 KB Output is correct
5 Correct 8 ms 8336 KB Output is correct
6 Correct 9 ms 8344 KB Output is correct
7 Correct 9 ms 8396 KB Output is correct
8 Correct 9 ms 8400 KB Output is correct
9 Correct 9 ms 8496 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 8184 KB Output is correct
2 Correct 9 ms 8184 KB Output is correct
3 Correct 9 ms 8336 KB Output is correct
4 Correct 9 ms 8336 KB Output is correct
5 Correct 8 ms 8336 KB Output is correct
6 Correct 9 ms 8344 KB Output is correct
7 Correct 9 ms 8396 KB Output is correct
8 Correct 9 ms 8400 KB Output is correct
9 Correct 9 ms 8496 KB Output is correct
10 Correct 10 ms 8644 KB Output is correct
11 Correct 9 ms 8744 KB Output is correct
12 Correct 9 ms 8820 KB Output is correct
13 Correct 10 ms 8932 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 8184 KB Output is correct
2 Correct 9 ms 8184 KB Output is correct
3 Correct 9 ms 8336 KB Output is correct
4 Correct 9 ms 8336 KB Output is correct
5 Correct 8 ms 8336 KB Output is correct
6 Correct 9 ms 8344 KB Output is correct
7 Correct 9 ms 8396 KB Output is correct
8 Correct 9 ms 8400 KB Output is correct
9 Correct 9 ms 8496 KB Output is correct
10 Correct 10 ms 8644 KB Output is correct
11 Correct 9 ms 8744 KB Output is correct
12 Correct 9 ms 8820 KB Output is correct
13 Correct 10 ms 8932 KB Output is correct
14 Correct 104 ms 27576 KB Output is correct
15 Correct 62 ms 32604 KB Output is correct
16 Correct 104 ms 41852 KB Output is correct
17 Correct 61 ms 42784 KB Output is correct