oj.uz

Submission #47506

# Submission time Handle Problem Language Result Execution time Memory
47506 2018-05-04T06:48:31 Z Waschbar Palindromes (APIO14_palindrome) C++17
23 / 100
 1000 ms 4796 KB 
///©Waschbar
#include <bits/stdc++.h>
#define tmm first
#define uu second.first
#define vv second.second
using namespace std;

const int MAXN = 1e5;
const int LOG = 20;
const int INF = 1e9;
const int MOD = 1e9+7;

int ans;
map < string,bool > used;
string s;

vector < int > pfunc(string str) {
        vector < int > p(str.size(),0);
            int j = 0;
        for(int i = 1; i < str.size(); i++) {
            while( j > 0 && str[j] != str[i])
                j = p[j-1];
            if(str[i] == str[j]) j++;
            p[i] = j;
        }

    return p;
}

void check(string t) {
    if(used[t]) return;
    used[t] = 1;
     vector < int > p;
     string tt = t + "#" + s;
     p = pfunc(tt);
     int cnt = 0;
     for(int i = 0; i < p.size(); i++)
        if(p[i] == t.size()) cnt++;
     //cout << t << " " << cnt << endl;
     ans = max(ans,(int)(t.size()*cnt));
}

int main() {

    //freopen("input.txt","r",stdin);
    //freopen("output.txt","w",stdout);

    ans = 0;
    cin >> s;

    string t;
    for(int i = 0; i < s.size(); i++) {
        t = ""; t = s[i];
        int j = 1;
        while(i-j >= 0 && i+j < s.size() && s[i-j]==s[i+j]) {
             check(t);
             t = s[i-j] + t + s[i+j];
             j++;
        }
        check(t);
    }
    for(int i = 0; i < s.size()-1; i++) {
        t = ""; t = s[i]; t = t + s[i+1];
        if(s[i] != s[i+1]) continue;
        int j = 1;
        while(i-j >= 0 && i+j+1 < s.size() && s[i-j]==s[i+j+1]) {
             check(t);
             t = s[i-j] + t + s[i+j+1];
             j++;
        }
        check(t);
    }

    cout << ans;

    return 0;
}

Compilation message

palindrome.cpp: In function 'std::vector<int> pfunc(std::__cxx11::string)':
palindrome.cpp:20:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i = 1; i < str.size(); i++) {
                        ~~^~~~~~~~~~~~
palindrome.cpp: In function 'void check(std::__cxx11::string)':
palindrome.cpp:37:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
      for(int i = 0; i < p.size(); i++)
                     ~~^~~~~~~~~~
palindrome.cpp:38:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if(p[i] == t.size()) cnt++;
palindrome.cpp: In function 'int main()':
palindrome.cpp:52:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < s.size(); i++) {
                    ~~^~~~~~~~~~
palindrome.cpp:55:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         while(i-j >= 0 && i+j < s.size() && s[i-j]==s[i+j]) {
                           ~~~~^~~~~~~~~~
palindrome.cpp:62:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < s.size()-1; i++) {
                    ~~^~~~~~~~~~~~
palindrome.cpp:66:33: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         while(i-j >= 0 && i+j+1 < s.size() && s[i-j]==s[i+j+1]) {
                           ~~~~~~^~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 252 KB Output is correct
2 Correct 2 ms 484 KB Output is correct
3 Correct 2 ms 484 KB Output is correct
4 Correct 2 ms 484 KB Output is correct
5 Correct 2 ms 484 KB Output is correct
6 Correct 2 ms 484 KB Output is correct
7 Correct 2 ms 484 KB Output is correct
8 Correct 2 ms 484 KB Output is correct
9 Correct 2 ms 496 KB Output is correct
10 Correct 2 ms 496 KB Output is correct
11 Correct 2 ms 496 KB Output is correct
12 Correct 2 ms 496 KB Output is correct
13 Correct 2 ms 508 KB Output is correct
14 Correct 2 ms 508 KB Output is correct
15 Correct 2 ms 508 KB Output is correct
16 Correct 2 ms 508 KB Output is correct
17 Correct 2 ms 564 KB Output is correct
18 Correct 2 ms 572 KB Output is correct
19 Correct 2 ms 572 KB Output is correct
20 Correct 3 ms 580 KB Output is correct
21 Correct 2 ms 580 KB Output is correct
22 Correct 2 ms 580 KB Output is correct
23 Correct 3 ms 612 KB Output is correct
24 Correct 2 ms 612 KB Output is correct
25 Correct 3 ms 612 KB Output is correct
26 Correct 2 ms 612 KB Output is correct
27 Correct 2 ms 612 KB Output is correct
28 Correct 3 ms 612 KB Output is correct
29 Correct 2 ms 620 KB Output is correct
30 Correct 2 ms 620 KB Output is correct
31 Correct 2 ms 620 KB Output is correct
32 Correct 2 ms 620 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 228 ms 1296 KB Output is correct
2 Correct 82 ms 1296 KB Output is correct
3 Correct 401 ms 1488 KB Output is correct
4 Correct 20 ms 1488 KB Output is correct
5 Correct 412 ms 1488 KB Output is correct
6 Correct 427 ms 1488 KB Output is correct
7 Correct 10 ms 1488 KB Output is correct
8 Correct 205 ms 1488 KB Output is correct
9 Correct 10 ms 1488 KB Output is correct
10 Correct 2 ms 1488 KB Output is correct
11 Correct 2 ms 1488 KB Output is correct
12 Correct 9 ms 1488 KB Output is correct

Subtask #3
0 / 24.0

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

Subtask #4
0 / 26.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1080 ms 4796 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 1082 ms 4796 KB Time limit exceeded
2 Halted 0 ms 0 KB -