QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#183885#5666. Repetitive ElementsZiadElGafy#AC ✓11ms10144kbC++203.6kb2023-09-19 22:57:232023-09-19 22:57:23

Judging History

你现在查看的是最新测评结果

  • [2023-09-19 22:57:23]
  • 评测
  • 测评结果:AC
  • 用时:11ms
  • 内存:10144kb
  • [2023-09-19 22:57:23]
  • 提交

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