oj.uz

Submission #172207

# Submission time Handle Problem Language Result Execution time Memory
172207 2019-12-31T15:08:48 Z nicolaalexandra Palindromic Partitions (CEOI17_palindromic) C++14
100 / 100
 569 ms 11188 KB 
#include <bits/stdc++.h>
#define DIM 1000010
#define MOD 1000000007
using namespace std;
int t,n,i,j;
char v[DIM];
vector <int> poz[30];

int main (){
    //ifstream fin ("date.in");
    //ofstream fout ("date.out");
    cin>>t;
    for (;t--;){

        cin>>v+1;
        n = strlen (v+1);
        //for (i=1;i<=n;i++)
            // hash[i] = (hash[i-1]*27 + v[i]-'a')%MOD;
        int st = 1, dr = n, sol = 0;
        int st_ant = 0, dr_ant = n+1, nr = 0;
        long long prf = 0, suf = 0, p = 1;
        while (st < dr){

            prf = (prf*27 + v[st] - '0')%MOD;
            suf = (suf + p*(v[dr] - '0'))%MOD;
            p = (p*27)%MOD;
            nr++;
            if (prf == suf){
                /// trb sa mai testez odata daca sunt egale
                int ok = 1;
                for (int i=st_ant+1,j=dr;i<=st,j<dr_ant;i++,j++){
                    if (v[i] != v[j]){
                        ok = 0;
                        break;
                    }}
                if (ok){ /// sunt egale
                    sol += 2;
                    prf = 0, suf = 0, p = 1, nr = 0;
                    st_ant = st, dr_ant = dr;
                }
            }
            st++, dr--;
        }
        if (st == dr || nr)
            sol++;

        cout<<sol<<"\n";

    }



    return 0;
}

Compilation message

palindromic.cpp: In function 'int main()':
palindromic.cpp:15:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
         cin>>v+1;
              ~^~
palindromic.cpp:31:43: warning: left operand of comma operator has no effect [-Wunused-value]
                 for (int i=st_ant+1,j=dr;i<=st,j<dr_ant;i++,j++){
                                          ~^~~~

Subtask #1
15.0 / 15.0

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 3 ms 376 KB Output is correct
5 Correct 2 ms 256 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 256 KB Output is correct
8 Correct 2 ms 256 KB Output is correct
9 Correct 2 ms 396 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 3 ms 376 KB Output is correct
5 Correct 2 ms 256 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 256 KB Output is correct
8 Correct 2 ms 256 KB Output is correct
9 Correct 2 ms 396 KB Output is correct
10 Correct 8 ms 504 KB Output is correct
11 Correct 5 ms 376 KB Output is correct
12 Correct 8 ms 504 KB Output is correct
13 Correct 7 ms 376 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 3 ms 376 KB Output is correct
5 Correct 2 ms 256 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 256 KB Output is correct
8 Correct 2 ms 256 KB Output is correct
9 Correct 2 ms 396 KB Output is correct
10 Correct 8 ms 504 KB Output is correct
11 Correct 5 ms 376 KB Output is correct
12 Correct 8 ms 504 KB Output is correct
13 Correct 7 ms 376 KB Output is correct
14 Correct 569 ms 11188 KB Output is correct
15 Correct 302 ms 6584 KB Output is correct
16 Correct 538 ms 10660 KB Output is correct
17 Correct 299 ms 6008 KB Output is correct