oj.uz

Submission #1013426

# Submission time Handle Problem Language Result Execution time Memory
1013426 2024-07-03T14:15:17 Z ByeWorld Palindromic Partitions (CEOI17_palindromic) C++14
100 / 100
 1032 ms 27072 KB 
#include <bits/stdc++.h>
// #pragma GCC optimize("O3", "unroll-loops")
#define ll long long
#define int long long
#define pb push_back
#define fi first
#define se second
#define lf (id<<1)
#define rg ((id<<1)|1)
#define md ((l+r)>>1)
#define ld long double
using namespace std;
typedef pair<int,int> pii;
typedef pair<pii, int> ipii;
const int MAXN = 1e6+20;
const int MAXA = 9e3+20;
const ll INF = 1e18+10;
const int LOG = 19;
const int SQRT = 450;
const vector<int> NOL = {};
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const vector<int> dx = {1, -1, 0, 0};
const vector<int> dy = {0, 0, 1, -1};
vector <int> key = {29, 31};
vector <int> mod = {998244353, 1000000007};

int sum(int a, int b, int MOD){ return (a+b)%MOD; }
int mul(int a, int b, int MOD){ return (a*b)%MOD; }
int sub(int a, int b, int MOD){ return (a+MOD-b)%MOD; }
int expo(int a, int b, int MOD){
	if(b==0) return 1;
	int te = expo(a, b/2, MOD); te = mul(te, te, MOD);
	return (b%2 ? mul(te,a,MOD) : te);
}
void chsum(int &a, int b, int MOD){ a = (a+b)%MOD; }
void chmul(int a, int b, int MOD){ a = (a*b)%MOD; }
void chsub(int a, int b, int MOD){ a = (a+MOD-b)%MOD; }

pii pr[MAXN];
pii GET(int x, int y){
	int len = y-x+1;
	pii te = pii(mul(pr[x-1].fi, expo(key[0], len, mod[0]), mod[0]), 
		mul(pr[x-1].se, expo(key[1], len, mod[1]), mod[1]));
	// cout << x <<' ' << y<< " x\n";
	// cout << te.fi << ' ' << te.se << " tee\n";
	pii ret = pii(sub(pr[y].fi, te.fi, mod[0]), sub(pr[y].se, te.se, mod[1]));
	return ret;
}
signed main(){
	// ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int T; cin >> T;
	while(T--){
		string s; cin >> s; s = '.'+s;
		int n = s.size()-1;
		for(int i=1; i<=n; i++){
			pr[i].fi = sum(mul(pr[i-1].fi, key[0], mod[0]), (int)(s[i]-'a'+1), mod[0]);
			pr[i].se = sum(mul(pr[i-1].se, key[1], mod[1]), (int)(s[i]-'a'+1), mod[1]);
			// cout << i << ' ' << pr[i].fi << ' ' << pr[i].se << " te\n";
		}

		int l=1, r=n, ANS = 0;
		pii le = GET(1, 1), ri = GET(n, n);
		// cout << (GET(2,3)==GET(7,8)) << " pp\n";
		int lasl = 1, lasr = n;
		while(l<r){
			if(le != ri){
				l++; le = GET(lasl, l);
				r--; ri = GET(r, lasr);
			} else {
				// cout << le << ' ' << ri << " pp\n";
				ANS+=2;
				l++; r--;
				lasl = l; lasr = r;
				le = GET(l, l); 
				ri = GET(r, r);
			}
		}
		if(lasl != n/2+1 || lasr != n/2) ANS++;
 		cout << ANS << '\n';
	}
}

Subtask #1
15.0 / 15.0

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

Subtask #2
20.0 / 20.0

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

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 456 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 8 ms 604 KB Output is correct
11 Correct 6 ms 640 KB Output is correct
12 Correct 8 ms 604 KB Output is correct
13 Correct 4 ms 604 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 456 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 8 ms 604 KB Output is correct
11 Correct 6 ms 640 KB Output is correct
12 Correct 8 ms 604 KB Output is correct
13 Correct 4 ms 604 KB Output is correct
14 Correct 1032 ms 26640 KB Output is correct
15 Correct 926 ms 23004 KB Output is correct
16 Correct 990 ms 27072 KB Output is correct
17 Correct 228 ms 15212 KB Output is correct