oj.uz

Submission #172194

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

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

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 376 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 256 KB Output is correct
2 Correct 2 ms 376 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 256 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 256 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 376 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 256 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 256 KB Output is correct
10 Correct 28 ms 632 KB Output is correct
11 Correct 21 ms 504 KB Output is correct
12 Correct 38 ms 508 KB Output is correct
13 Correct 22 ms 504 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 376 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 256 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 256 KB Output is correct
10 Correct 28 ms 632 KB Output is correct
11 Correct 21 ms 504 KB Output is correct
12 Correct 38 ms 508 KB Output is correct
13 Correct 22 ms 504 KB Output is correct
14 Execution timed out 10071 ms 14384 KB Time limit exceeded
15 Halted 0 ms 0 KB -