QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#110564#5440. P-P-PalindromeZeardoeWA 51ms69296kbC++203.5kb2023-06-02 20:48:062023-06-02 20:48:07

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-06-02 20:48:07]
  • 评测
  • 测评结果:WA
  • 用时:51ms
  • 内存:69296kb
  • [2023-06-02 20:48:06]
  • 提交

answer

/*
[templates]: 
duipai
spjdp
compre
addhis
*/
#include<bits/stdc++.h>
using namespace std;
#define int long long
//use ll instead of int.
#define f(i, a, b) for(int i = (a); i <= (b); i++)
#define cl(i, n) i.clear(),i.resize(n);
#define endl '\n'
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int inf = 1e9;
//#define cerr if(false)cerr
//#define freopen if(false)freopen
mt19937 rng(time(0)); 
int rnd(int l, int r) {return rng() % (r-l+1) + l; }
#define watch(x) cerr  << (#x) << ' '<<'i'<<'s'<<' ' << x << endl
void pofe(int number, int bitnum) {
    string s; f(i, 0, bitnum) {s += char(number & 1) + '0'; number >>= 1; } 
    reverse(s.begin(), s.end()); cerr << s << endl; 
    return;
}
template <typename TYP> void cmax(TYP &x, TYP y) {if(x < y) x = y;}
template <typename TYP> void cmin(TYP &x, TYP y) {if(x > y) x = y;}
//调不出来给我对拍!
//use std::array.
map<uint64_t, int> mp;
uint64_t base = 210982; uint64_t powp[1000010];
struct PAM {
    int cnt, lst, n; string s; int tot; 
    vector<int> fail; vector<array<int, 26>> ed; vector<int> len; vector<uint64_t> pre; 
    PAM() {
        cnt = 1; lst = 1; n = 0; fail.push_back(1); fail.push_back(1); 
        ed.push_back({0}); ed.push_back({0}); len.push_back(0); 
        len.push_back(-1); pre.push_back(0); 
        tot = 0; 
    }
    int getfa(int x) {
        while(s[n] != s[n - len[x] - 1]) x = fail[x]; 
        return x; 
    }
    int hx(int l, int r) {
        return pre[r] - pre[l - 1] * powp[r - l + 1]; 
    }
    void input(int l, int leng) {
        int r = l + leng - 1; 
        //tot += t.size(); 
        uint64_t tt = hx(l, r); //cerr << l << " " << r << " " << s.substr(l, r - l + 1) << " " << tt << endl; 
     //   cerr << t << endl; 
        if(mp.count(tt)) mp[tt] ++; else mp[tt] = 1; 
    }
    void insert(char ch) {
        n++; int p = getfa(lst); pre.push_back((pre[n-1] * base) + (uint64_t)s[n]); 
        if(!ed[p][ch - 'a']) {
            ++cnt; fail.push_back(0); ed.push_back({0}); len.push_back(len[p]+2);
            int np = getfa(fail[p]); fail[cnt] = ed[np][ch - 'a']; 
            ed[p][ch - 'a'] = cnt; 
            if(len[cnt] % (len[cnt] - len[fail[cnt]]) == 0) {
                input(n - len[cnt] + 1, len[cnt] - len[fail[cnt]]); 
            }
            else {
                input(n - len[cnt] + 1, len[cnt]);
            }
        } 
        
        lst = ed[p][ch - 'a']; //tot += len[lst] - len[fail[lst]]; 
      //  cerr << "n = " << n << ", lst = " << lst << ", fail[lst] = " << fail[lst] << ", delta len(T) = " <<  len[lst] - len[fail[lst]] << endl; 
        
    }
}pam; 
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);
    //freopen();
    //freopen();
    //time_t start = clock();
    //think twice,code once.
    //think once,debug forever.
    int n; cin >> n;  
    powp[0] = 1; for(int i = 1; i <= 1000000; i ++) powp[i] = powp[i - 1] * base; 
    f(i, 1, n) {
        pam.lst = 1; pam.n = 0; pam.pre.clear(); pam.pre.push_back(0); 
        cin >> pam.s; pam.s = ' ' + pam.s; 
        for(char ch : pam.s) if(ch != ' ') pam.insert(ch); 
    }
    int ans = 0;  
    for(auto it : mp) {
        ans += it.second * it.second; 
    }
    cout << ans << endl;
    //time_t finish = clock();
    //cout << "time used:" << (finish-start) * 1.0 / CLOCKS_PER_SEC <<"s"<< endl;
    return 0;
};

详细

Test #1:

score: 100
Accepted
time: 4ms
memory: 11340kb

input:

2
aaaa
aaa

output:

16

result:

ok 1 number(s): "16"

Test #2:

score: 0
Accepted
time: 5ms
memory: 11364kb

input:

3
abaaa
abbbba
bbbaba

output:

28

result:

ok 1 number(s): "28"

Test #3:

score: 0
Accepted
time: 7ms
memory: 11456kb

input:

1
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab

output:

15130

result:

ok 1 number(s): "15130"

Test #4:

score: 0
Accepted
time: 2ms
memory: 11380kb

input:

3
aaaaaaaaaaaaaaaaaaaaaaaaa
bbbbbbbbbbbbbbbbbbbbbbbbb
bababababababaabababababa

output:

1282

result:

ok 1 number(s): "1282"

Test #5:

score: 0
Accepted
time: 16ms
memory: 25756kb

input:

5
ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff...

output:

3600000000

result:

ok 1 number(s): "3600000000"

Test #6:

score: 0
Accepted
time: 24ms
memory: 25860kb

input:

5
wwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwww...

output:

3600000000

result:

ok 1 number(s): "3600000000"

Test #7:

score: -100
Wrong Answer
time: 51ms
memory: 69296kb

input:

3
abbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbab...

output:

300922154

result:

wrong answer 1st numbers differ - expected: '133586', found: '300922154'