Submission #172194

#	Time	Username	Problem	Language	Result	Execution time	Memory
172194		nicolaalexandra	Palindromic Partitions (CEOI17_palindromic)	C++14	60 / 100	10071 ms	14384 KiB

palindromic

#include <bits/stdc++.h>
#define DIM 1000010
using namespace std;
int t,n,i,j;
char v[DIM];
vector <int> poz[30];
int cautare_binara (vector <int> v, int poz){
    /// prima pozitie mai mare decat poz
    int st = 0, dr = v.size()-1, sol = -1;
    while (st <= dr){
        int mid = (st+dr)>>1;
        if (v[mid] > poz){
            dr = mid-1;
            sol = mid;
        } else st = mid+1;
    }
    if (sol == -1)
        return n+1;
    return v[sol];
}
int main (){
    //ifstream fin ("date.in");
    //ofstream fout ("date.out");
    cin>>t;
    for (;t--;){
        for (int i=0;i<=26;i++)
            poz[i].clear();

        cin>>v+1;
        n = strlen (v+1);

        for (i=1;i<=n;i++){
           // hash[i] = (hash[i-1]*27 + v[i]-'a')%MOD;
            poz[v[i]-'a'].push_back(i);
        }
        int st = 1, dr = n, sol = 0;
        while (st < dr){
            if (v[st] == v[dr]){
                sol += 2;
                st++, dr--;
                continue;
            }
            /// caut binar prima aparite a lui v[dr] dupa st
            int x = st;
            for (;;){
                x = cautare_binara (poz[v[dr]-'a'],x);
                int lg = x-st+1;
                if (x >= dr-lg+1){
                    /// nu am gasit nimic deci trebuie sa l iau pe tot
                    sol++;
                    st = dr+1;
                    break;
                }
                int ok = 1;
                for (int j=st,t=dr-lg+1;j<=x;j++,t++){
                    if (v[j] != v[t]){
                        ok = 0;
                        break;
                    }}
                if (ok){
                    sol += 2;
                    st += lg, dr -= lg;
                    break;
                }
            }

        }
        if (st == dr)
            sol++;
        cout<<sol<<"\n";
    }



    return 0;
}

Compilation message (stderr)

palindromic.cpp: In function 'int main()':
palindromic.cpp:29:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
         cin>>v+1;
              ~^~

• Subtask 1: 15 / 15
• Subtask 2: 20 / 20
• Subtask 3: 25 / 25
• Subtask 4: 0 / 40