oj.uz

Submission #934326

# Submission time Handle Problem Language Result Execution time Memory
934326 2024-02-27T07:21:41 Z KaleemRazaSyed Palindromic Partitions (CEOI17_palindromic) C++17
100 / 100
 374 ms 45868 KB 
#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
const int MAXN = 1e6+5, b = 193, mod1 = 1e9+7, mod2 = 1e9+9;

ll pw1[MAXN], pw2[MAXN], h1[MAXN], h2[MAXN];

pair<ll, ll> Hash(int l, int r)
{
  pair<ll, ll> res;
 res.first = (((h1[r + 1] - h1[l] * pw1[r - l + 1] % mod1) % mod1 + mod1)) % mod1;
 res.second= (((h2[r + 1] - h2[l] * pw2[r - l + 1] % mod2) % mod2 + mod2)) % mod2;
  return res;
}

void solve()
{
  string s;
  cin >> s;
  int ans = 0;
  int n = s.size();
  deque<int> idx[26];
  for(int i = 0; i < n; i ++)
    idx[s[i] - 'a'].push_back(i);

  h1[0] = h1[0] = 0;
  for(int i = 0; i < n; i ++)
    {
      h1[i + 1] = (h1[i] * b % mod1 + s[i]) % mod1;
      h2[i + 1] = (h2[i] * b % mod2 + s[i]) % mod2;
    }
  
  int l = 0, r = n-1;
  while(r - l + 1 > 0)
    {
      char c = s[l];
      while(idx[c - 'a'].front() < l) idx[c - 'a'].pop_front();
      while(idx[c - 'a'].back() > r) idx[c - 'a'].pop_back();
      
      int last = (int)idx[c - 'a'].size() - 1;
      while(last >= 0)
	{
	  int sz = r - idx[c-'a'][last] + 1;
	  //cerr << l << ' ' << l + sz - 1 << endl;
	  //cerr << r - sz + 1 << ' ' << r << endl;
	  if(Hash(l, l + sz - 1) == Hash(r - sz + 1, r) && sz * 2 <= r - l + 1)
	    {
	      ans += 2, l = l + sz, r = r - sz;
	      break;
	    }
	  last--;
	}
      if(last == -1)
	{
	  ans++;
	  break;
	}
    }
  cout << ans << endl;
}

int main()
{
  pw1[0] = pw2[0] = 1;
  for(int i = 1; i < MAXN; i++)
    pw1[i] = pw1[i - 1] * b % mod1,
      pw2[i] = pw2[i - 1] * b % mod2;
  int t;
  cin >> t;
  while(t--)
    solve();
  return 0;
}

Compilation message

palindromic.cpp: In function 'void solve()':
palindromic.cpp:28:9: warning: operation on 'h1[0]' may be undefined [-Wsequence-point]
   28 |   h1[0] = h1[0] = 0;
      |   ~~~~~~^~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 19032 KB Output is correct
2 Correct 8 ms 19136 KB Output is correct
3 Correct 8 ms 19288 KB Output is correct
4 Correct 8 ms 19264 KB Output is correct
5 Correct 8 ms 19140 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 19032 KB Output is correct
2 Correct 8 ms 19136 KB Output is correct
3 Correct 8 ms 19288 KB Output is correct
4 Correct 8 ms 19264 KB Output is correct
5 Correct 8 ms 19140 KB Output is correct
6 Correct 8 ms 19036 KB Output is correct
7 Correct 8 ms 19036 KB Output is correct
8 Correct 9 ms 19292 KB Output is correct
9 Correct 8 ms 19036 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 19032 KB Output is correct
2 Correct 8 ms 19136 KB Output is correct
3 Correct 8 ms 19288 KB Output is correct
4 Correct 8 ms 19264 KB Output is correct
5 Correct 8 ms 19140 KB Output is correct
6 Correct 8 ms 19036 KB Output is correct
7 Correct 8 ms 19036 KB Output is correct
8 Correct 9 ms 19292 KB Output is correct
9 Correct 8 ms 19036 KB Output is correct
10 Correct 12 ms 19272 KB Output is correct
11 Correct 10 ms 19292 KB Output is correct
12 Correct 11 ms 19288 KB Output is correct
13 Correct 11 ms 19288 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 19032 KB Output is correct
2 Correct 8 ms 19136 KB Output is correct
3 Correct 8 ms 19288 KB Output is correct
4 Correct 8 ms 19264 KB Output is correct
5 Correct 8 ms 19140 KB Output is correct
6 Correct 8 ms 19036 KB Output is correct
7 Correct 8 ms 19036 KB Output is correct
8 Correct 9 ms 19292 KB Output is correct
9 Correct 8 ms 19036 KB Output is correct
10 Correct 12 ms 19272 KB Output is correct
11 Correct 10 ms 19292 KB Output is correct
12 Correct 11 ms 19288 KB Output is correct
13 Correct 11 ms 19288 KB Output is correct
14 Correct 374 ms 45868 KB Output is correct
15 Correct 193 ms 40324 KB Output is correct
16 Correct 333 ms 43700 KB Output is correct
17 Correct 189 ms 34924 KB Output is correct