oj.uz

Submission #248391

# Submission time Handle Problem Language Result Execution time Memory
248391 2020-07-12T10:48:27 Z vanic Palinilap (COI16_palinilap) C++14
54 / 100
 106 ms 13944 KB 
#include <iostream>
#include <cstdio>
#include <math.h>
#include <algorithm>
#include <vector>
#include <queue>


using namespace std;

typedef long long ll;
const int maxn=1e5+5, p=29, mod=1e9+7;

inline int sum(int a, int b){
	if(a+b>=mod){
		return a+b-mod;
	}
	else if(a+b<0){
		return a+b+mod;
	}
	return a+b;
}

inline int mul(int a, int b){
	return (ll)a*b%mod;
}


int pref[maxn], suff[maxn];
int n;
string s;
int pot[maxn];
int sw[maxn];
int oduz[maxn];
int dodaj[maxn][p];
int sol;


void precompute(){
	pot[0]=1;
	for(int i=1; i<maxn; i++){
		pot[i]=mul(pot[i-1], p);
	}
}

bool provjeri(int x, int y, int kolko){
	return sum(pref[x+1], -mul(pref[x-kolko], pot[kolko+1]))==sum(suff[n-y], -mul(suff[n-y-kolko-1], pot[kolko+1]));
}

int binary(int x, int y){
	int lo=0, hi=min(x+1, n-y), mid;
	while(lo<hi){
		mid=(lo+hi)/2;
		if(provjeri(x, y, mid)){
			lo=mid+1;
		}
		else{
			hi=mid;
		}
	}
	return lo;
}

void rijesi(int x, bool p){
	int l, d;
	if(p){
		l=x;
		d=x+1;
	}
	else{
		l=x-1;
		d=x+1;
	}
	int val;
	if(l<0 || d>=n){
		val=0;
	}
	else{
		val=binary(l, d);
	}
	l-=val;
	d+=val;
	sol+=x-l;
//	cout << x << " " << p << " " << x-l << endl;
//	cout << x << " " << p << " " << l << " " << d << '\n';
	if(p){
		sw[l+1]++;
		sw[x+1]--;
		sw[x+2]--;
		sw[d+1]++;
	}
	else{
		sw[l+1]++;
		sw[x+1]-=2;
		sw[d+1]++;
		oduz[x]+=x-l;
	}
}

void rijesi2(int x, bool p){
	int l, d;
	if(p){
		l=x;
		d=x+1;
	}
	else{
		l=x-1;
		d=x+1;
	}
	if(l<0 || d>=n){
		return;
	}
	int val;
	val=binary(l, d);
	l-=val;
	d+=val;
	if(l<0 || d>=n){
		return;
	}
	dodaj[l][s[d]-'a']++;
	dodaj[d][s[l]-'a']++;
	if(l-1<0 || d+1>=n){
		return;
	}
	val=binary(l-1, d+1);
	dodaj[l][s[d]-'a']+=val;
	dodaj[d][s[l]-'a']+=val;
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	precompute();
	cin >> s;
	n=s.size();
	for(int i=0; i<n; i++){
		pref[i+1]=sum(mul(pref[i], p), s[i]-'a');
		suff[i+1]=sum(mul(suff[i], p), s[n-i-1]-'a');
	}
	for(int i=0; i<n; i++){
		rijesi(i, 0);
		rijesi(i, 1);
	}
	int val=0;
	int upd=0;
	for(int i=0; i<n; i++){
		upd+=sw[i];
		val-=upd;
		oduz[i]+=val;
	}
/*	for(int i=0; i<n; i++){
		cout << oduz[i] << " ";
	}
	cout << '\n';*/
	for(int i=0; i<n; i++){
		rijesi2(i, 0);
		rijesi2(i, 1);
	}
	int maksi=0;
	for(int i=0; i<n; i++){
		for(int j=0; j<p; j++){
			maksi=max(maksi, oduz[i]+dodaj[i][j]);
		}
	}
	cout << sol+maksi << '\n';
	return 0;
}

Subtask #1
17.0 / 17.0

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

Subtask #2
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1408 KB Output is correct
2 Correct 4 ms 1408 KB Output is correct
3 Correct 5 ms 1408 KB Output is correct
4 Correct 3 ms 1152 KB Output is correct
5 Correct 4 ms 1280 KB Output is correct
6 Correct 5 ms 1408 KB Output is correct
7 Correct 7 ms 1436 KB Output is correct

Subtask #3
0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 106 ms 13944 KB Output is correct
2 Incorrect 85 ms 13944 KB Output isn't correct
3 Halted 0 ms 0 KB -