QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#183885 | #5666. Repetitive Elements | ZiadElGafy# | AC ✓ | 11ms | 10144kb | C++20 | 3.6kb | 2023-09-19 22:57:23 | 2023-09-19 22:57:23 |
Judging History
answer
#pragma GCC optimize("Ofast")
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#define el '\n'
#define F first
#define S second
typedef long long ll;
typedef long double ld;
typedef __int128 bigInt;
using namespace std;
const int N = 4e5 + 5, INF = 1e9 + 5, mod = 1e9 + 7, LOG = 21, SQ = 500;
/// DON'T FORGET TO CALL PRE()!
const int b1 = 29, b2 = 37;
int mul(int a, int b){
return 1LL * a * b % mod;
}
int add(int a, int b){
a = (a + mod) % mod;
b = (b + mod) % mod;
return (a + b) % mod;
}
int fp(int b, int p){
if (b == 1 or p == 0)
return 1;
if (p == 1)
return b;
ll hp = fp(b, p >> 1);
ll ans = hp * hp % mod;
if (p % 2)
(ans *= b) %= mod;
return ans;
}
int modInv(int x){
return fp(x, mod - 2);
}
int pw1[N], invP1[N];
int pw2[N], invP2[N];
void pre(){
pw1[0] = invP1[0] = 1;
int baseInverse1 = modInv(b1);
pw2[0] = invP2[0] = 1;
int baseInverse2 = modInv(b2);
for(int i = 1; i < N; i++){
pw1[i] = mul(pw1[i - 1], b1);
invP1[i] = mul(invP1[i - 1], baseInverse1);
pw2[i] = mul(pw2[i - 1], b2);
invP2[i] = mul(invP2[i - 1], baseInverse2);
}
}
struct Hash{
vector<pair<int, int>> prefixHash, revHash;
int sz;
Hash():sz(0){}
Hash(string s){
sz = s.size();
prefixHash.assign(sz, {0, 0});
revHash.assign(sz, {0, 0});
for(int i = 0; i < sz; i++){
prefixHash[i].first = mul(s[i] - 'A' + 1, pw1[i]);
prefixHash[i].second = mul(s[i] - 'A' + 1, pw2[i]);
if(i > 0){
prefixHash[i].first = add(prefixHash[i].first, prefixHash[i - 1].first);
prefixHash[i].second = add(prefixHash[i].second, prefixHash[i - 1].second);
}
}
reverse(s.begin(), s.end());
for(int i = 0; i < sz; i++){
revHash[i].first = mul(s[i] - 'A' + 1, pw1[i]);
revHash[i].second = mul(s[i] - 'A' + 1, pw2[i]);
if(i > 0){
revHash[i].first = add(revHash[i].first, revHash[i - 1].first);
revHash[i].second = add(revHash[i].second, revHash[i - 1].second);
}
}
}
pair<int, int> getHashValue(){
return prefixHash.back();
}
pair<int, int> getRangeHashValue(int l, int r){
return {mul(add(prefixHash[r].first, -(l ? prefixHash[l - 1].first: 0)), invP1[l]),
mul(add(prefixHash[r].second, -(l ? prefixHash[l - 1].second: 0)), invP2[l])};
}
pair<int, int> getRevHashValue(int pl, int pr){// if rangeHash(i, j) == revHash(i, j) --> substr(i, j) is a palindrome
int l = sz - pr - 1;
int r = sz - pl - 1;
return {mul(add(revHash[r].first, -(l ? revHash[l - 1].first: 0)), invP1[l]),
mul(add(revHash[r].second, -(l ? revHash[l - 1].second: 0)), invP2[l])};
}
};
void doWork() {
string s;
cin >> s;
int n = s.size();
Hash h(s);
for (int sz = n / 2; sz > 0; sz--) {
for (int i = 0; i + sz - 1 < n; i++) {
auto hash = h.getRangeHashValue(i, i + sz - 1);
for (int j = i + sz; j + sz - 1 < n; j++) {
if (h.getRangeHashValue(j, j + sz - 1) == hash) {
return cout << s.substr(i, sz) << el, void();
}
}
}
}
}
int main() {
ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int tests = 1;
cin >> tests;
pre();
for (int i = 1; i <= tests; i++) {
doWork();
}
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 10096kb
input:
5 TATCGATCGAGTTGT TCCGCGAGCGAGTCTCTCCATT GTTTCATCATACGAGGCCCCATACGCGCTGG AGATGGGATCCTTATG GCCCTTAGGCATGGGATGTCGTTTCTTG
output:
ATCG GCGA CATACG GAT CTT
result:
ok 5 lines
Test #2:
score: 0
Accepted
time: 11ms
memory: 10144kb
input:
50 TTGACAACTTCAGGTTGGCACTCCTTCATTTGGATTTCGGAATAATAGTTTTCTGCTCTGCC ATCCTATTCGGGGATAGGAGAGATGGGTTGCCGCTATAAAAGCATTTGAACTCCATTTCACTCCGTTGGCTAGGGGTCGCACTG CCGTAATATAAAGACTCGGAATTCCAATAGCTGCTATTTGCGAGTATGTGACTGAAAACACACCTATAAATATTAGCTGCGTACAAGCTA ATGGCTGCATGCAGGGTCGACTAGACACACTTTGTCT TTGAGGATGTCGACGTGTCT...
output:
CTTCA CATTT TAGCTGC TGCA ACGTG GCGCCGG CTCTT AGTAT AGAG ACAG TAT TGAC CTTG CGTC TACTGG GCCGGT GAA CAGTA GCGT GGTT CCCT GAG TAGAC GGTGC GCAGT TGAG ATCAA CCACACA GAGTC ATGTA ATGGTA TATA TATGAA TTCC CATACG TACCA TTAG GGAATGT CAGG GCT AAG CTGT GGAT TCTTC AAAAC ATG GATAA TTA ACATAT CAAT
result:
ok 50 lines