oj.uz

Submission #686731

# Submission time Handle Problem Language Result Execution time Memory
686731 2023-01-25T21:07:44 Z yashsingh Palindromic Partitions (CEOI17_palindromic) C++17
100 / 100
 167 ms 26836 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

// String hashing template from USACO Guide
const ll M = LLONG_MAX-1;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const ll B = uniform_int_distribution<ll>(27, 27)(rng);
class HashedString {
	private:
		static vector<ll> pow;
		vector<ll> p_hash;
	public:
		HashedString(const string& s) : p_hash(s.size() + 1) {
			while (pow.size() < s.size()) {
				pow.push_back((pow.back() * B) % M);
			}

			p_hash[0] = 0;
			for (int i = 0; i < (int)s.size(); i++) {
				p_hash[i + 1] = ((p_hash[i] * B) % M + (s[i] - 'a' + 1)) % M;
			}
		}

		ll getHash(int start, int end) {
			ll raw_val = (
				p_hash[end + 1] - (p_hash[start] * pow[end - start + 1])
			);
			return (raw_val % M + M) % M;
		}
};
vector<ll> HashedString::pow = {1};

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);

  // Slice bit by bit
  // Prefix and suffix maintained, once they match:
  // if they intersect then return so far + 1
  // otherwise slice prefix and suffix, add two to answer, and repeat

  int t;
  cin >> t;

  string s;
  while (t--) {
    cin >> s;
    int n{(int)s.size()};
    int curl{0}, curr{n - 1};
    int till{0}, tillr{n - 1};
    HashedString hs(s);
    int ans{0};
    while (true) {
      if (till >= tillr) {
        ++ans;
        break;
      }
      if (hs.getHash(curl, till) == hs.getHash(tillr, curr)) {
        curl = till + 1;
        curr = tillr - 1;
        ans += 2;
        if (curl == curr) ++ans;
        if (curl >= curr) break;
      }
      ++till;
      --tillr;
    }
    cout << ans << "\n";
  }

  return 0;
}

Subtask #1
15.0 / 15.0

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 320 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 1 ms 328 KB Output is correct
9 Correct 1 ms 212 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 320 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 1 ms 328 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 2 ms 724 KB Output is correct
11 Correct 1 ms 648 KB Output is correct
12 Correct 3 ms 724 KB Output is correct
13 Correct 2 ms 596 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 320 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 1 ms 328 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 2 ms 724 KB Output is correct
11 Correct 1 ms 648 KB Output is correct
12 Correct 3 ms 724 KB Output is correct
13 Correct 2 ms 596 KB Output is correct
14 Correct 167 ms 26836 KB Output is correct
15 Correct 101 ms 22052 KB Output is correct
16 Correct 160 ms 25876 KB Output is correct
17 Correct 87 ms 14152 KB Output is correct