Submission #491020

#TimeUsernameProblemLanguageResultExecution timeMemory
491020kawaiiFibonacci representations (CEOI18_fib)C++14
0 / 100
14 ms8140 KiB
#include <bits/stdc++.h> using namespace std; #define int long long #define hash hashh int t, hash[1000005], mod = 998244353, base = 353, mul[1000005]; string s; void solve(){ mul[0] = 1; for(int i = 1; i <= 1e6; i++) mul[i] = (mul[i - 1] * base) % mod; while(t--){ cin >> s; int ans = 0, n = s.size(); for(int i = 0; i < s.size(); i++) hash[i + 1] = (hash[i] * base + s[i]) % mod; int l = 1, r = n, cnt = n; while(l <= r){ int p = (hash[cnt] - hash[r - 1] * mul[cnt - r + 1]) % mod; if(p < 0) p += mod; int q = (hash[l + cnt - r] - hash[l - 1] * mul[cnt - r + 1]) % mod; if(q < 0) q += mod; if(p == q){ ans += 2; if(l == r) ans--; l += cnt - r + 1; cnt = r - 1; } r--; } cout << ans << "\n"; } } signed main(){ ios_base::sync_with_stdio(NULL); cin.tie(nullptr); cout.tie(nullptr); cin >> t; solve(); }

Compilation message (stderr)

fib.cpp: In function 'void solve()':
fib.cpp:16:26: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   16 |         for(int i = 0; i < s.size(); i++) hash[i + 1] = (hash[i] * base + s[i]) % mod;
      |                        ~~^~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...