Submission #172201

#	Time	Username	Problem	Language	Result	Execution time	Memory
172201		nicolaalexandra	Palindromic Partitions (CEOI17_palindromic)	C++14	60 / 100	10031 ms	14444 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 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;
            int val = cautare_binara (poz[v[dr]-'a'],x);
            for (;;){
                if (val < poz[v[dr]-'a'].size())
                    x = poz[v[dr]-'a'][val];
                else x = n+1;
                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;
                }
                ++val;
            }
        }
        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;
              ~^~
palindromic.cpp:47:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 if (val < poz[v[dr]-'a'].size())
                     ~~~~^~~~~~~~~~~~~~~~~~~~~~~

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