oj.uz

답안 #1117162

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1117162 2024-11-22T21:20:32 Z Thunnus Palinilap (COI16_palinilap) C++17
100 / 100
 146 ms 33804 KB 
#include <algorithm>
#include <cassert>
#include <functional>
#include <iostream>
#include <map>
#include <vector>

using namespace std;

// BeginCodeSnip{String Hashing}
/** source: https://usaco.guide/gold/modular */
long long pow_mod(long long x, long long n, long long mod) {
	assert(n >= 0);
	x %= mod;
	long long res = 1;
	while (n > 0) {
		if (n % 2 == 1) { res = res * x % mod; }
		x = x * x % mod;
		n /= 2;
	}
	return res;
}

class HashedString {
  private:
	static const long long MOD = 1e9 + 9;
	static const long long POW = 101;

	static vector<long long> pow;
	static vector<long long> mod_inv;

	const string &s;
	vector<long long> p_hash;

  public:
	HashedString(const string &s) : s(s), p_hash(s.size() + 1) {
		while (pow.size() < s.size()) {
			pow.push_back((pow.back() * POW) % MOD);
			mod_inv.push_back(pow_mod(pow.back(), MOD - 2, MOD));
		}

		p_hash[0] = 0;
		for (int i = 0; i < s.size(); i++) {
			p_hash[i + 1] = (p_hash[i] + s[i] * pow[i] % MOD) % MOD;
		}
	}

	long long hash(int from, int to) {
		long long pref = (p_hash[to + 1] - p_hash[from] + MOD) % MOD;
		return pref * mod_inv[from] % MOD;
	}

	/** @return substring hash with a given character replaced */
	long long hash(int from, int to, const pair<int, char> &rep) {
		long long pref = p_hash[to + 1] - p_hash[from];
		if (from <= rep.first && rep.first <= to) {
			pref += rep.second * pow[rep.first] - s[rep.first] * pow[rep.first];
		}
		return (pref % MOD + MOD) * mod_inv[from] % MOD;
	}
};
vector<long long> HashedString::pow = {1};
vector<long long> HashedString::mod_inv = {1};
// EndCodeSnip

/**
 * @return the largest number in [lo, hi] such that check is satisfied.
 * if no number in the range works, -1 is returned
 */
int last_true(int lo, int hi, function<bool(int)> check) {
	int valid = -1;
	while (lo <= hi) {
		int mid = (lo + hi) / 2;
		if (check(mid)) {
			lo = mid + 1;
			valid = mid;
		} else {
			hi = mid - 1;
		}
	}
	return valid;
}

/**
 * @return the resulting array when the operations in the ranges are performend
 * @param ranges in each of the ranges in this variable, consecutive numbers
 * starting from 1 are added to the subarray. for example, [0, 3] would add
 * the numbers 1, 2, 3, and 4 to the first 4 elements to the range [0, 3].
 */
vector<long long> range_res(int size, const vector<pair<int, int>> &ranges) {
	vector<long long> arr(size + 1);
	for (const auto &[a, b] : ranges) {
		arr[a]++;
		arr[b + 1]--;
	}
	for (int i = 1; i < size; i++) { arr[i] += arr[i - 1]; }
	for (const auto &[a, b] : ranges) { arr[b + 1] -= b - a + 1; }
	for (int i = 1; i < size; i++) { arr[i] += arr[i - 1]; }
	arr.pop_back();
	return arr;
}

int main() {
	string str;
	cin >> str;
	int len = str.size();  // shorthand

	string rev_str = str;
	reverse(rev_str.begin(), rev_str.end());
	HashedString h_str(str), h_rev_str(rev_str);

	// checks if a substring is a palindrome
	auto is_pal = [&](int from, int to) {
		return h_str.hash(from, to) == h_rev_str.hash(len - to - 1, len - from - 1);
	};
	// checks if a substring is a palindrome with a replaced character
	auto is_pal_rep = [&](int from, int to, pair<int, char> rep) {
		pair<int, char> r_rep{len - rep.first - 1, rep.second};
		return h_str.hash(from, to, rep) ==
		       h_rev_str.hash(len - to - 1, len - from - 1, r_rep);
	};

	function<bool(int)> check;
	vector<map<char, long long>> good(len);
	// the ranges we have to add to our bad array
	vector<pair<int, int>> removal1, removal2;
	long long init_amt = 0;  // the initial amount of palindromes
	for (int c = 0; c < len; c++) {
		// first check the odd-length palindromes relative to c
		int most = min(c, len - c - 1);  // the most we can extend from position c
		check = [&](int d) { return is_pal(c - d, c + d); };
		int raw_pal = last_true(0, most, check);
		init_amt += raw_pal + 1;
		if (raw_pal > 0) {
			removal1.push_back({c - raw_pal, c - 1});
			removal2.push_back({c + 1, c + raw_pal});
		}

		pair<int, char> rep = {c + raw_pal + 1, str[c - raw_pal - 1]};
		check = [&](int d) { return is_pal_rep(c - d, c + d, rep); };
		int rep_pal = last_true(raw_pal + 1, most, check);
		if (rep_pal != -1) {
			good[rep.first][rep.second] += rep_pal - raw_pal;
			good[c - raw_pal - 1][str[c + raw_pal + 1]] += rep_pal - raw_pal;
		}

		// and then the even-length palindromes
		if (c < len - 1) {
			int most = min(c + 1, len - c - 1);
			check = [&](int d) { return is_pal(c - d + 1, c + d); };
			int raw_pal = last_true(0, most, check);
			init_amt += raw_pal;
			if (raw_pal > 0) {
				removal1.push_back({c - raw_pal + 1, c});
				removal2.push_back({c + 1, c + raw_pal});
			}

			pair<int, char> rep = {c + raw_pal + 1, str[c - raw_pal]};
			check = [&](int d) { return is_pal_rep(c - d + 1, c + d, rep); };
			int rep_pal = last_true(raw_pal + 1, most, check);
			if (rep_pal != -1) {
				good[rep.first][rep.second] += rep_pal - raw_pal;
				good[c - raw_pal][str[c + raw_pal + 1]] += rep_pal - raw_pal;
			}
		}
	}

	for (pair<int, int> &r : removal2) { r = {len - r.second - 1, len - r.first - 1}; }
	// these two combined give the bad array stated in the analysis
	vector<long long> bad1 = range_res(len, removal1);
	vector<long long> bad2 = range_res(len, removal2);
	std::reverse(bad2.begin(), bad2.end());

	long long max_weight = init_amt;
	for (int i = 0; i < len; i++) {
		long long max_inc = 0;
		for (const auto &[_, i] : good[i]) { max_inc = max(max_inc, i); }
		max_weight = max(max_weight, init_amt + max_inc - bad1[i] - bad2[i]);
	}

	cout << max_weight << endl;
}

Compilation message

palinilap.cpp: In constructor 'HashedString::HashedString(const string&)':
palinilap.cpp:43:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |   for (int i = 0; i < s.size(); i++) {
      |                   ~~^~~~~~~~~~

Subtask #1
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct

Subtask #2
37.0 / 37.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 1528 KB Output is correct
2 Correct 4 ms 1260 KB Output is correct
3 Correct 6 ms 1372 KB Output is correct
4 Correct 4 ms 1104 KB Output is correct
5 Correct 6 ms 1360 KB Output is correct
6 Correct 6 ms 1360 KB Output is correct
7 Correct 6 ms 1872 KB Output is correct

Subtask #3
46.0 / 46.0

# 결과 실행 시간 메모리 Grader output
1 Correct 118 ms 17664 KB Output is correct
2 Correct 82 ms 20484 KB Output is correct
3 Correct 86 ms 20484 KB Output is correct
4 Correct 123 ms 23308 KB Output is correct
5 Correct 120 ms 22800 KB Output is correct
6 Correct 134 ms 22628 KB Output is correct
7 Correct 132 ms 23308 KB Output is correct
8 Correct 63 ms 14356 KB Output is correct
9 Correct 137 ms 22540 KB Output is correct
10 Correct 118 ms 22540 KB Output is correct
11 Correct 85 ms 20484 KB Output is correct
12 Correct 115 ms 20484 KB Output is correct
13 Correct 110 ms 18700 KB Output is correct
14 Correct 126 ms 24076 KB Output is correct
15 Correct 116 ms 23048 KB Output is correct
16 Correct 106 ms 26680 KB Output is correct
17 Correct 137 ms 33644 KB Output is correct
18 Correct 137 ms 17420 KB Output is correct
19 Correct 146 ms 33804 KB Output is correct