QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#723538#9406. TriangleAllenJYLWA 17ms42760kbC++145.0kb2024-11-07 22:46:502024-11-07 22:46:51

Judging History

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

  • [2024-11-07 22:46:51]
  • 评测
  • 测评结果:WA
  • 用时:17ms
  • 内存:42760kb
  • [2024-11-07 22:46:50]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;

#define int long long
#define ls (p<<1)
#define rs (p<<1|1)
#define mid ((l+r)>>1)
#define all(_array) (_array).begin(),(_array).end()
#define msp(_array) memset(_array,0x3f,sizeof _array)
#define ms0(_array) memset(_array,0,sizeof _array)
#define msn(_array) memset(_array,-1,sizeof _array)
#define mc(_tar,_array) memcpy(_tar,_array,sizeof _tar)
#define Yes cout<<"Yes"<<endl
#define No cout<<"No"<<endl
#define YES cout<<"YES"<<endl
#define NO cout<<"NO"<<endl
#define TAK cout<<"TAK"<<endl
#define NIE cout<<"NIE"<<endl
#define OK cerr<<"OK"<<endl
#define pii pair<int,int>
#define endl '\n'

bool bg_memory;
mt19937 rnd(time(0));
int Case=1;
// const int mod=1e9+7;
const int inf=1e18;
// const int bs=233;
const double eps=1e-6;
const int N=3e5+7,M=1e6+7;

template<class _t1,class _t2>inline void cmax(_t1 &a,_t2 b){a=a<b?b:a;}
template<class _t1,class _t2>inline void cmin(_t1 &a,_t2 b){a=a>b?b:a;}
inline int qp(int a,int b,int p){int res=1;while(b){if(b&1)res=1ll*res*a%p;a=1ll*a*a%p;b>>=1;}return res;}
inline int sqrt(int x,int r){int l=0,ans=0;while(l<=r){if(1ll*mid*mid<=x) ans=mid,l=mid+1;else r=mid-1;}return ans;}

int n;
int val[26];
int ans;
struct node{
    string s;
    vector<int> h[2];
}s[N];
struct hash{
    int bs,mod;
    int pw[M];
    void clear(){
        pw[0]=1;
        for(int i=1;i<=1000000;i++) pw[i]=pw[i-1]*bs%mod;
    }
    void build(node&s,int id){
        int ans=0;
        s.h[id].push_back(0);
        for(int i=0;i<s.s.size();i++) s.h[id].push_back(
            ans=(1ll*ans*bs%mod+val[s.s[i]-'a'])%mod);
    }
}h[2];
bool check(node a,node b,int l){
    bool res=1;
    for(int i=0;i<2;i++){
        res&=((a.h[i][a.s.size()]-a.h[i][a.s.size()-l]*h[i].pw[l]%h[i].mod+h[i].mod)%h[i].mod
        ==(b.h[i][b.s.size()]-b.h[i][b.s.size()-l]*h[i].pw[l]%h[i].mod+h[i].mod)%h[i].mod);
    }
    return res;
}
bool operator<(node a,node b){
    int l=0,r=min(a.s.size(),b.s.size()),res=0;
    // cerr<<a.s<<" "<<b.s<<" "<<res<<endl;
    while(l<=r){
        // cerr<<l<<" "<<r<<endl;
        if(check(a,b,mid)) res=mid,l=mid+1;
        else r=mid-1;
    }
    if(res==a.s.size()&&res==b.s.size()) return 0;
    if(res==a.s.size()) return 1;
    if(res==b.s.size()) return 0;
    return a.s[a.s.size()-res-1]<b.s[b.s.size()-res-1];
}
unordered_map<int,vector<pii>> ap;

void Main(){
    
    cin>>n;
    ans=0;
    ap.clear();
    for(int i=0;i<26;i++) val[i]=rnd()%1145141919,cout<<val[i]<<" ";
    for(int i=1;i<=n;i++){
        cin>>s[i].s;
        reverse(all(s[i].s));
        s[i].h[0].clear();
        s[i].h[1].clear();
    }
    for(int i=1;i<=n;i++){
        h[0].build(s[i],0);
        h[1].build(s[i],1);
    }
    sort(s+1,s+n+1);
    // if(!Case&&n!=1){
    //     cout<<n<<endl;
    //     for(int i=1;i<=n;i++) cout<<s[i].s<<endl;
    // }
    for(int i=1;i<=n;i++){
        string tmp="";
        vector<int> h0,h1;
        h0.push_back(0),h1.push_back(0);
        int ht=(1ll*s[i].h[0].back()*h[0].bs%h[0].mod+s[i].h[1].back())%h[1].mod;
        // cout<<ht<<endl;
        for(int j=0;j<s[i].s.size();j++){
            int Tmp=(1ll*(s[i].h[0].back()-s[i].h[0][j]*h[0].pw[s[i].s.size()-j]%h[0].mod
            +h[0].mod)%h[0].mod*h[0].bs%h[0].mod+(s[i].h[1].back()-s[i].h[1][j]*h[1].pw[s[i].s.size()-j]%h[1].mod
            +h[1].mod)%h[1].mod)%h[1].mod;
            // cout<<i<<" "<<j<<" "<<Tmp<<endl;
            if(ap[Tmp].size()){
                int pos=upper_bound(s+1,s+n+1,(node){tmp,{h0,h1}})-s;
                int Pos=upper_bound(all(ap[Tmp]),(pii){pos,-114514})-ap[Tmp].begin();
                ans+=(ap[Tmp].back().second-(Pos?ap[Tmp][Pos-1].second:0))-(ap[Tmp].size()-Pos)*pos;
                // cout<<ap[Tmp].size()<<" "<<i<<" "<<j<<" "<<pos<<" "<<Pos<<" "<<ans<<endl;
            }
            tmp.push_back(s[i].s[j]);
            h0.push_back((1ll*h0.back()*h[0].bs%h[0].mod+val[s[i].s[j]-'a'])%h[0].mod);
            h1.push_back((1ll*h1.back()*h[1].bs%h[1].mod+val[s[i].s[j]-'a'])%h[1].mod);
        }
        ap[ht].push_back({i,(ap[ht].size()?ap[ht].back().second:0)+i});
    }
    cout<<ans<<endl;

    return;
}
string RdFile="";
bool en_memory;

signed main(){
    auto bg_clock=chrono::high_resolution_clock::now();
#ifdef ONLINE_JUDGE
    // freopen((RdFile+".in").c_str(),"r",stdin);
    // freopen((RdFile+".out").c_str(),"w",stdout);
#endif
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>Case;
    h[0].mod=1226999999,h[0].bs=233;
    h[1].mod=1000000007,h[1].bs=998244353;
    h[0].clear(),h[1].clear();
    while(Case--) Main();
    auto en_clock=chrono::high_resolution_clock::now();
    auto duration_clock=chrono::duration_cast<chrono::microseconds>(en_clock-bg_clock);
    double duration_count=duration_clock.count()*0.001;
    double memory_used=(&en_memory-&bg_memory)/1024.0/1024;
    // cerr<<"Time:"<<duration_count<<"ms"<<endl;
    // cerr<<"Memory: "<<memory_used<<"MB"<<endl;
    return 0;
}

詳細信息

Test #1:

score: 0
Wrong Answer
time: 17ms
memory: 42760kb

input:

3
6
cbaa
cb
cb
cbaa
ba
ba
3
sdcpc
sd
cpc
1
ccpc

output:

521221811 732589660 8341603 591069214 342261259 1144011774 594212236 478876969 1105851047 296515176 154726939 917279255 533393900 85301577 17943578 697247481 265069840 424500495 707415177 6670248 187836972 864366461 716471606 1094032133 296480484 551238721 16
927482976 1043217473 812559477 669095316...

result:

wrong answer 1st lines differ - expected: '16', found: '521221811 732589660 8341603 59...94032133 296480484 551238721 16'