oj.uz

Submission #990815

# Submission time Handle Problem Language Result Execution time Memory
990815 2024-05-31T12:23:45 Z ChottuF Palindromic Partitions (CEOI17_palindromic) C++17
100 / 100
 152 ms 30436 KB 
  #include <bits/stdc++.h>
  using namespace std;

  #define int long long

  const int P = 31;
  const int M = 1e9+9;

  vector<int> binpow;
  vector<int> pref;

  int gethash(int l, int r){
      int h = ((pref[r+1] - (binpow[r-l+1] * pref[l]))%M + M)%M;
      return h;
  }

  signed main(){
      ios::sync_with_stdio(0);
      cin.tie(0);
      int t;
      cin >> t;
      while (t--){
          string s;
          cin >> s;
          int n = s.size();
          binpow.clear();
          binpow.resize(n);
          binpow[0] = 1;
          for (int i = 1; i<n; i++){
              binpow[i] = (binpow[i-1]*P) % M;
          }
          pref.clear();
          pref.resize(n+1);
          pref[0] = 0;
          for (int i = 1; i<=n; i++){
              pref[i] = ((pref[i-1]*P)+(s[i-1]-'a'+1)) % M;
          }
          int r = 0;
          int ln = 0;
          int ans = 0;
          vector<bool> vis(n);
          int lst = n-1;
          while (r+ln < n/2){
              int st = r; int stt = r+ln;
              int nd = lst-ln; int ndd = lst;
              int one = gethash(st,stt);
              int two = gethash(nd,ndd);
              //cout << st << " " << stt << "  " << nd << " " << ndd << "\n";
              //cout << one << " " << two << "\n\n";
              if (one == two){
                  for (int i = st; i<=stt; i++){
                      vis[i] = true;
                  }
                  for (int i = nd; i<=ndd; i++){
                      vis[i] = true;
                  }
                  ans += 2;
                  r += ln+1;
                  lst -= ln+1;
                  ln = 0;
              }
              else{
                  ln++;
              }
          }
          int bk = 0;
          for (int i = 0; i<n; i++){
              bk += vis[i];
          }
          if (bk != n) ans++;
          cout << ans << '\n';
      }
      return 0;
  }

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 2 ms 604 KB Output is correct
11 Correct 1 ms 604 KB Output is correct
12 Correct 2 ms 720 KB Output is correct
13 Correct 2 ms 696 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 2 ms 604 KB Output is correct
11 Correct 1 ms 604 KB Output is correct
12 Correct 2 ms 720 KB Output is correct
13 Correct 2 ms 696 KB Output is correct
14 Correct 152 ms 28588 KB Output is correct
15 Correct 87 ms 30436 KB Output is correct
16 Correct 149 ms 29220 KB Output is correct
17 Correct 82 ms 15264 KB Output is correct