oj.uz

Submission #46322

# Submission time Handle Problem Language Result Execution time Memory
46322 2018-04-19T06:26:30 Z RayaBurong25_1 Palindromes (APIO14_palindrome) C++17
47 / 100
 1000 ms 16072 KB 
#include <stdio.h>
#include <map>
#define MOD 1000000007LL
char S[300005];
std::map<int, int> Map[300005];
int isPalin[2][300005];
int Ans = 0;
int main()
{
    scanf("%s", S);
    int N;
    for (N = 0; S[N] != '\0'; N++);
    int i, j;
    long long Hash;
    std::map<int, int>::iterator it;
    for (i = N - 1; i >= 0; i--)
    {
        Hash = 0;
        for (j = i; j < N; j++)
        {
            Hash = (Hash*26 + S[j] - 'a')%MOD;
            if (j == i)
            {
                isPalin[i%2][j] = 1;
                Map[j - i + 1][Hash]++;
                it = Map[j - i + 1].find(Hash);
                if (it->second*(j - i + 1) > Ans)
                    Ans = it->second*(j - i + 1);
            }
            else if (j == i + 1 && S[i] == S[j])
            {
                isPalin[i%2][j] = 1;
                Map[j - i + 1][Hash]++;
                it = Map[j - i + 1].find(Hash);
                if (it->second*(j - i + 1) > Ans)
                    Ans = it->second*(j - i + 1);
            }
            else if (S[i] == S[j] && isPalin[(i + 1)%2][j - 1])
            {
                isPalin[i%2][j] = 1;
                Map[j - i + 1][Hash]++;
                it = Map[j - i + 1].find(Hash);
                if (it->second*(j - i + 1) > Ans)
                    Ans = it->second*(j - i + 1);
            }
            else
                isPalin[i%2][j] = 0;
            // printf("i%d j%d isPalin %d\n", i, j, isPalin[i%2][j]);
        }
    }
    printf("%d", Ans);
}

Compilation message

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

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 14328 KB Output is correct
2 Correct 13 ms 14436 KB Output is correct
3 Correct 12 ms 14488 KB Output is correct
4 Correct 13 ms 14564 KB Output is correct
5 Correct 12 ms 14616 KB Output is correct
6 Correct 12 ms 14616 KB Output is correct
7 Correct 12 ms 14740 KB Output is correct
8 Correct 14 ms 14740 KB Output is correct
9 Correct 15 ms 14740 KB Output is correct
10 Correct 13 ms 14740 KB Output is correct
11 Correct 15 ms 14740 KB Output is correct
12 Correct 13 ms 14740 KB Output is correct
13 Correct 13 ms 14740 KB Output is correct
14 Correct 13 ms 14740 KB Output is correct
15 Correct 13 ms 14740 KB Output is correct
16 Correct 13 ms 14796 KB Output is correct
17 Correct 13 ms 14796 KB Output is correct
18 Correct 12 ms 14796 KB Output is correct
19 Correct 13 ms 14796 KB Output is correct
20 Correct 13 ms 14796 KB Output is correct
21 Correct 13 ms 14796 KB Output is correct
22 Correct 14 ms 14796 KB Output is correct
23 Correct 14 ms 14872 KB Output is correct
24 Correct 13 ms 14872 KB Output is correct
25 Correct 14 ms 14884 KB Output is correct
26 Correct 13 ms 14884 KB Output is correct
27 Correct 13 ms 14884 KB Output is correct
28 Correct 13 ms 14884 KB Output is correct
29 Correct 12 ms 14884 KB Output is correct
30 Correct 14 ms 14884 KB Output is correct
31 Correct 12 ms 14884 KB Output is correct
32 Correct 12 ms 14896 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 14896 KB Output is correct
2 Correct 18 ms 14896 KB Output is correct
3 Correct 18 ms 14896 KB Output is correct
4 Correct 17 ms 14896 KB Output is correct
5 Correct 18 ms 14896 KB Output is correct
6 Correct 18 ms 14904 KB Output is correct
7 Correct 16 ms 14908 KB Output is correct
8 Correct 19 ms 14908 KB Output is correct
9 Correct 16 ms 14916 KB Output is correct
10 Correct 17 ms 14916 KB Output is correct
11 Correct 16 ms 14916 KB Output is correct
12 Correct 16 ms 14916 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 666 ms 15572 KB Output is correct
2 Correct 529 ms 15572 KB Output is correct
3 Correct 550 ms 15572 KB Output is correct
4 Correct 484 ms 15572 KB Output is correct
5 Correct 377 ms 15664 KB Output is correct
6 Correct 383 ms 15664 KB Output is correct
7 Correct 517 ms 15664 KB Output is correct
8 Correct 371 ms 15664 KB Output is correct
9 Correct 372 ms 15664 KB Output is correct
10 Correct 380 ms 15688 KB Output is correct

Subtask #4
0 / 26.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1090 ms 15948 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1074 ms 16072 KB Time limit exceeded
2 Halted 0 ms 0 KB -