ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила
вернуться в форум

Обсуждение задачи 1297. Палиндромы

Got a WA on #27
Послано Kenith Chu 21 фев 2019 15:54
my cpp code is following:

#include <cstdio>
#include <algorithm>
#include <cstring>
#define fi first
#define se second
using namespace std;
typedef long long LL;
typedef pair<int, int> P;
const int N = 5010, INF = 0x3f3f3f3f;

int c[N], sa[N], x[N], y[N];

void GetSA(int *r, int *sa, int n, int m)
{
    for (int i = 1; i <= m; i++) c[i] = 0;
    for (int i = 1; i <= n; i++) c[x[i] = r[i]]++;
    for (int i = 2; i <= m; i++) c[i] += c[i - 1];
    for (int i = n; i >= 1; i--) if (c[x[i]]) sa[c[x[i]]--] = i;
    for (int k = 1, p = 0; k <= n; k <<= 1, p = 0)
    {
        for (int i = n - k + 1; i <= n; i++) y[++p] = i;
        for (int i = 1; i <= n; i++) if (sa[i] > k) y[++p] = sa[i] - k;
        for (int i = 1; i <= m; i++) c[i] = 0;
        for (int i = 1; i <= n; i++) c[x[i]]++;
        for (int i = 2; i <= m; i++) c[i] += c[i - 1];
        for (int i = n; i >= 1; i--) sa[c[x[y[i]]]--] = y[i], y[i] = 0;
        swap(x, y); x[sa[1]] = p = 1;
        for (int i = 2; i <= n; i++) x[sa[i]] = (y[sa[i]] == y[sa[i - 1]] && y[sa[i] + k] == y[sa[i - 1] + k]) ? p : ++p;
        if (p == n) break; m = p;
    }
}

int hei[N], rnk[N];

void GetH(int *r, int *sa, int n)
{
    for (int i = 1; i <= n; i++) rnk[sa[i]] = i;
    for (int i = 1, k = 0, j; i <= n; hei[rnk[i++]] = k)
        for (k ? k-- : 0, j = sa[rnk[i] - 1]; r[i + k] == r[j + k]; k++);
}

int n;

int s[N];
char str[N];

bool check(int a, int b, int len)
{
    return n - a + 2 == b + len;
}

int main()
{
    int mx = 0;
    scanf("%s", str + 1);
    int len = strlen(str + 1);
    for (int i = 1; i <= len; i++) s[i] = str[i], mx = max(mx, s[i]);
    s[len + 1] = '$';
    for (int i = len; i >= 1; i--) s[len * 2 - i + 2] = str[i];
    n = (len << 1) + 1;
    GetSA(s, sa, n, 1000);
    GetH(s, sa, n);
    P ans = P(1, -1);
    for (int i = 3; i <= n; i++)
    {
        int a = max(sa[i - 1], sa[i]), b = min(sa[i - 1], sa[i]);
        if (!(a > len + 1 && b <= len)) continue;
        if (check(a, b, hei[i]) && P(hei[i], -b) > ans) ans = P(hei[i], -b);
    }
    int pos = -ans.se;
    for (int i = pos; i < pos + ans.fi; i++) printf("%c", str[i]); puts("");
    return 0;
}

I've tried to enlarge the alphabet size, but there's no effect.

I also test lots of random test cases, all of them are correct.

I hope someone could give me a hack data.

Edited by author 21.02.2019 15:57
Re: Got a WA on #27
Послано PixSor 21 фев 2019 16:57
All right, I knew what's wrong...
Re: Got a WA on #27
Послано GJC_xj 3 май 2019 11:57
can you tell me why you wrong? i wrong on #27 too