oj.uz

답안 #694166

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
694166 2023-02-04T01:37:55 Z TriangleBicycle Palindromic Partitions (CEOI17_palindromic) C++17
60 / 100
 10000 ms 30624 KB 
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using graph = vector<vector<int>>;

constexpr uint64_t MAXLEN = 1000005;
constexpr uint64_t mod = (1ULL << 61) - 1;

const uint64_t seed = chrono::system_clock::now().time_since_epoch().count();
const uint64_t base = mt19937_64(seed)() % (mod / 3) + (mod / 3);

uint64_t base_pow[MAXLEN];

int64_t modmul(uint64_t a, uint64_t b){
    uint64_t l1 = (uint32_t)a, h1 = a >> 32, l2 = (uint32_t)b, h2 = b >> 32;
    uint64_t l = l1 * l2, m = l1 * h2 + l2 * h1, h = h1 * h2;
    uint64_t ret = (l & mod) + (l >> 61) + (h << 3) + (m >> 29) + (m << 35 >> 3) + 1;
    ret = (ret & mod) + (ret >> 61);
    ret = (ret & mod) + (ret >> 61);
    return ret - 1;
}

void init(){
    base_pow[0] = 1;
    for (int i = 1; i < MAXLEN; i++){
        base_pow[i] = modmul(base_pow[i - 1], base);
    }
}

int slow(string& s) {
	int n = s.length();
	int ans = 0;
	int l = 0;
	int r = s.length() - 1;

	string left = "";
	string right = "";
	bool middle = false;
	bool even_middle = false;

	while (l <= r) {
		left += s[l];
		right = s[r] + right;
		
		if (left == right) {
			ans += 2;
			left = "";
			right = "";
			if (l == r) {
				middle = true;
			}

			if (n % 2 == 0 && l + 1 == r) {
				even_middle = true;
			}
		}

		++l;
		--r;
	}

	if (n % 2 == 1) {
		if (middle) --ans;
		else ++ans;
	} else {
		if (!even_middle) ++ans;
	}

	return ans;
}

struct PolyHash{
    /// Remove suff vector and usage if reverse hash is not required for more speed
    vector<int64_t> pref, suff;

    PolyHash() {}

    template <typename T>
    PolyHash(const vector<T>& ar){
        if (!base_pow[0]) init();

        int n = ar.size();
        assert(n < MAXLEN);
        pref.resize(n + 3, 0), suff.resize(n + 3, 0);

        for (int i = 1; i <= n; i++){
            pref[i] = modmul(pref[i - 1], base) + ar[i - 1] + 997;
            if (pref[i] >= mod) pref[i] -= mod;
        }

        for (int i = n; i >= 1; i--){
            suff[i] = modmul(suff[i + 1], base) + ar[i - 1] + 997;
            if (suff[i] >= mod) suff[i] -= mod;
        }
    }

    PolyHash(const char* str)
        : PolyHash(vector<char> (str, str + strlen(str))) {}

    uint64_t get_hash(int l, int r){
        int64_t h = pref[r + 1] - modmul(base_pow[r - l + 1], pref[l]);
        return h < 0 ? h + mod : h;
    }

    uint64_t rev_hash(int l, int r){
        int64_t h = suff[l + 1] - modmul(base_pow[r - l + 1], suff[r + 2]);
        return h < 0 ? h + mod : h;
    }
};

void solve() {
	string s;
	cin >> s;
	int n = s.length();

	PolyHash hash_s(s.c_str());
	int ans = 1;

	for (int i = 0; i < n/2; ++i) {
		int j = i;
		while (j < n/2) {
			if (hash_s.get_hash(i, j) == hash_s.get_hash(n - j - 1, n - i - 1)) {
				break;
			}
			++j;
		}
		i = j;
	}

	/* cout << ans << '\n'; */
	cout << slow(s) << '\n';
}

int main() {
	ios::sync_with_stdio(false), cin.tie(nullptr);
	int tc; cin >> tc;
	while(tc--) solve();
}

Compilation message

palindromic.cpp: In function 'void init()':
palindromic.cpp:25:23: warning: comparison of integer expressions of different signedness: 'int' and 'const uint64_t' {aka 'const long unsigned int'} [-Wsign-compare]
   25 |     for (int i = 1; i < MAXLEN; i++){
      |                     ~~^~~~~~~~
palindromic.cpp: In function 'void solve()':
palindromic.cpp:117:6: warning: unused variable 'ans' [-Wunused-variable]
  117 |  int ans = 1;
      |      ^~~
In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from palindromic.cpp:1:
palindromic.cpp: In instantiation of 'PolyHash::PolyHash(const std::vector<_Tp>&) [with T = char]':
palindromic.cpp:98:57:   required from here
palindromic.cpp:83:18: warning: comparison of integer expressions of different signedness: 'int' and 'const uint64_t' {aka 'const long unsigned int'} [-Wsign-compare]
   83 |         assert(n < MAXLEN);
      |                ~~^~~~~~~~
palindromic.cpp:88:25: warning: comparison of integer expressions of different signedness: '__gnu_cxx::__alloc_traits<std::allocator<long int>, long int>::value_type' {aka 'long int'} and 'const uint64_t' {aka 'const long unsigned int'} [-Wsign-compare]
   88 |             if (pref[i] >= mod) pref[i] -= mod;
palindromic.cpp:93:25: warning: comparison of integer expressions of different signedness: '__gnu_cxx::__alloc_traits<std::allocator<long int>, long int>::value_type' {aka 'long int'} and 'const uint64_t' {aka 'const long unsigned int'} [-Wsign-compare]
   93 |             if (suff[i] >= mod) suff[i] -= mod;

Subtask #1
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 8020 KB Output is correct
2 Correct 10 ms 8060 KB Output is correct
3 Correct 9 ms 8148 KB Output is correct
4 Correct 10 ms 8108 KB Output is correct
5 Correct 10 ms 8080 KB Output is correct

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 8020 KB Output is correct
2 Correct 10 ms 8060 KB Output is correct
3 Correct 9 ms 8148 KB Output is correct
4 Correct 10 ms 8108 KB Output is correct
5 Correct 10 ms 8080 KB Output is correct
6 Correct 9 ms 8136 KB Output is correct
7 Correct 9 ms 8148 KB Output is correct
8 Correct 8 ms 8148 KB Output is correct
9 Correct 9 ms 8148 KB Output is correct

Subtask #3
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 8020 KB Output is correct
2 Correct 10 ms 8060 KB Output is correct
3 Correct 9 ms 8148 KB Output is correct
4 Correct 10 ms 8108 KB Output is correct
5 Correct 10 ms 8080 KB Output is correct
6 Correct 9 ms 8136 KB Output is correct
7 Correct 9 ms 8148 KB Output is correct
8 Correct 8 ms 8148 KB Output is correct
9 Correct 9 ms 8148 KB Output is correct
10 Correct 15 ms 8508 KB Output is correct
11 Correct 13 ms 8404 KB Output is correct
12 Correct 14 ms 8408 KB Output is correct
13 Correct 12 ms 8380 KB Output is correct

Subtask #4
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 8020 KB Output is correct
2 Correct 10 ms 8060 KB Output is correct
3 Correct 9 ms 8148 KB Output is correct
4 Correct 10 ms 8108 KB Output is correct
5 Correct 10 ms 8080 KB Output is correct
6 Correct 9 ms 8136 KB Output is correct
7 Correct 9 ms 8148 KB Output is correct
8 Correct 8 ms 8148 KB Output is correct
9 Correct 9 ms 8148 KB Output is correct
10 Correct 15 ms 8508 KB Output is correct
11 Correct 13 ms 8404 KB Output is correct
12 Correct 14 ms 8408 KB Output is correct
13 Correct 12 ms 8380 KB Output is correct
14 Execution timed out 10093 ms 30624 KB Time limit exceeded
15 Halted 0 ms 0 KB -