oj.uz

답안 #368152

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
368152 2021-02-19T16:41:06 Z Nima_Naderi 회문 (APIO14_palindrome) C++14
0 / 100
 272 ms 20676 KB 
/** Im the best because i work as hard as i possibly can **/

#pragma GCC optimize("O2")
#include <bits/stdc++.h>
using namespace std;

typedef long long                   ll;
typedef long double                 ld;
typedef pair<int,int>               pii;
typedef pair<ll,ll>                 pll;
#define all(x)                      (x).begin(),(x).end()
#define F                           first
#define S                           second
#define Mp                          make_pair
#define fast_io                     ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define file_io                     freopen("in.txt" , "r+" , stdin) ; freopen("out.txt" , "w+" , stdout);
#define endl                        "\n"

const int N = 3e5 + 10;
const ll mod = 884577481;
const ll mod2 = 998244353;
const ll inf = 8e18;
const int LOG = 20;
const ll base = 609859;

string s;

char C[N];

ll PW, n, T, lcp[N], tmp[N], Cnt[N], SA[N], rnk[N], seg[N << 2];

ll pw[N], hshL[N], hshR[N];

inline void BuildSuffixArray(const string &s){
    assert((s[0] == '$') && (n + 1 == (int)s.size()));
    iota(SA + 1, SA + n + 1, 1), SA[0] = n + 1;
    for(int i = 1; i <= n; i ++) rnk[i] = s[i];
    int _Max = 'z', p = 1, k;
    for(PW = 0; p < n; PW ++){
        k = ((1LL << PW) >> 1), p = 1;
        for(int i = n - k + 1; i <= n; i ++){
            tmp[p ++] = i;
        }
        for(int i = 1; i <= n; i ++){
            if(SA[i] > k) tmp[p ++] = SA[i] - k;
        }
        for(int i = 0; i <= _Max; i ++) Cnt[i] = 0;
        for(int i = 1; i <= n; i ++) Cnt[rnk[i]] ++;
        for(int i = 1; i <= _Max; i ++){
            Cnt[i] += Cnt[i - 1];
        }
        for(int i = n; i; i --){
            SA[Cnt[rnk[tmp[i]]] --] = tmp[i];
        }
        swap(rnk, tmp);
        rnk[SA[1]] = p = 1;
        for(int i = 2; i <= n; i ++){
            if(tmp[SA[i - 1]] != tmp[SA[i]] || SA[i - 1] + k > n || tmp[SA[i - 1] + k] != tmp[SA[i] + k]){
                p ++;
            }
            rnk[SA[i]] = p;
        }
        _Max = p;
    }
    SA[0] = n + 1;
}
inline void BuildLcpTable(const string &s){
    assert((s[0] == '$') && (n + 1 == (int)s.size()));
    for(int i = 1, k = 0; i <= n; i ++){
        if(rnk[i] == n) continue;
        if(k) k --;
        while(s[i + k] == s[SA[rnk[i] + 1] + k]){
            k ++;
        }
        lcp[rnk[i] + 1] = k;
    }
}

inline ll baze(int l, int r)
{
	return (hshL[r] - (hshL[l - 1] * pw[r - l + 1] % mod) + mod) % mod;
}

inline ll baze2(int l, int r)
{
	return (hshR[l] - (hshR[r + 1] * pw[r - l + 1] % mod) + mod) % mod;
}

void build(int v = 1, int tl = 1, int tr = n)
{
	if(tl == tr)
	{
		seg[v] = lcp[tl];
		return;
	}
	int mid = (tl + tr) >> 1;
	build(v << 1, tl, mid), build(v << 1 | 1, mid + 1, tr);
	seg[v] = min(seg[v << 1], seg[v << 1 | 1]);
}

int find_nxt(int p, int x, int v = 1, int tl = 1, int tr = n)
{
	if(p > n) return n + 1;
	if(tr < p) return -1;
	if(seg[v] >= x)
	{
		if(tr == n) return n + 1;
		return -1;
	}
	if(tl == tr) return tl;
	int mid = (tl + tr) >> 1;
	int cu = find_nxt(p, x, v << 1, tl, mid);
	if(cu == -1) cu = find_nxt(p, x, v << 1 | 1, mid + 1, tr);
	return cu;
}

int find_prv(int p, int x, int v = 1, int tl = 1, int tr = n)
{
	if(tl > p) return -1;
	if(seg[v] >= x)
	{
		if(tl == 1) return 0;
		return -1;
	}
	if(tl == tr) return tl;
	int mid = (tl + tr) >> 1;
	int cu = find_prv(p, x, v << 1 | 1, mid + 1, tr);
	if(cu == -1) cu = find_prv(p, x, v << 1, tl, mid);
	return cu;
}

ll calc(int l, int r)
{
	int sz = r - l + 1, id = rnk[l];
	int L = find_prv(id, sz);
	int R = find_nxt(id + 1, sz);
	return R - L;
}

int main()
{
    scanf("%s", C);
	n = strlen(C);
	s = C;
	s = "$" + s;
	BuildSuffixArray(s);
	BuildLcpTable(s);
	build();
	ll tot = 0;
	for(ll i = 1; i <= n; i ++)
	{
		int d = 0, up = min(i - 1, n - i) + 1;
		while(up - d > 1)
		{
			int mid = (up + d) >> 1;
			if(baze(i, i + mid) == baze2(i - mid, i)) d = mid;
			else up = mid;
		}
		tot = max(tot, calc(i - d, i + d) * (2 * d + 1));
	}
	for(ll i = 1; i < n; i ++)
	{
		if(s[i] != s[i + 1]) continue;
		int d = 0, up = min(i - 1, n - i - 1) + 1;
		while(up - d > 1)
		{
			int mid = (up + d) >> 1;
			if(baze(i + 1, i + 1 + mid) == baze2(i - mid, i)) d = mid;
			else up = mid;
		}
		tot = max(tot, calc(i - d, i + d + 1) * (2 *  d + 2));
	}
	printf("%lld", tot);
	return 0;
}

Compilation message

palindrome.cpp: In function 'int main()':
palindrome.cpp:142:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  142 |     scanf("%s", C);
      |     ~~~~~^~~~~~~~~

Subtask #1
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 5100 KB Output is correct
2 Correct 5 ms 5100 KB Output is correct
3 Correct 5 ms 5100 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 5 ms 5100 KB Output is correct
6 Correct 5 ms 5100 KB Output is correct
7 Correct 5 ms 5100 KB Output is correct
8 Correct 5 ms 5100 KB Output is correct
9 Correct 6 ms 5100 KB Output is correct
10 Correct 6 ms 5100 KB Output is correct
11 Incorrect 6 ms 5100 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 5120 KB Output is correct
2 Correct 8 ms 5100 KB Output is correct
3 Correct 9 ms 5100 KB Output is correct
4 Correct 7 ms 5100 KB Output is correct
5 Correct 9 ms 5100 KB Output is correct
6 Correct 8 ms 5100 KB Output is correct
7 Incorrect 8 ms 5100 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 17 ms 5612 KB Output is correct
2 Incorrect 14 ms 5612 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Correct 82 ms 9580 KB Output is correct
2 Correct 77 ms 9580 KB Output is correct
3 Correct 112 ms 9452 KB Output is correct
4 Correct 126 ms 9580 KB Output is correct
5 Incorrect 102 ms 9836 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #5
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 272 ms 20580 KB Output is correct
2 Incorrect 231 ms 20676 KB Output isn't correct
3 Halted 0 ms 0 KB -