oj.uz

Submission #172201

# Submission time Handle Problem Language Result Execution time Memory
172201 2019-12-31T14:53:21 Z nicolaalexandra Palindromic Partitions (CEOI17_palindromic) C++14
60 / 100
 10000 ms 14444 KB 
#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

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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 348 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 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 348 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 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 348 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 13 ms 632 KB Output is correct
11 Correct 11 ms 504 KB Output is correct
12 Correct 10 ms 504 KB Output is correct
13 Correct 21 ms 504 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 348 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 13 ms 632 KB Output is correct
11 Correct 11 ms 504 KB Output is correct
12 Correct 10 ms 504 KB Output is correct
13 Correct 21 ms 504 KB Output is correct
14 Execution timed out 10031 ms 14444 KB Time limit exceeded
15 Halted 0 ms 0 KB -