QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#723533 | #9406. Triangle | AllenJYL | WA | 18ms | 42728kb | C++14 | 5.0kb | 2024-11-07 22:45:21 | 2024-11-07 22:45:27 |
Judging History
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: 18ms
memory: 42728kb
input:
3 6 cbaa cb cb cbaa ba ba 3 sdcpc sd cpc 1 ccpc
output:
885791550 838209604 152948505 865776132 112059265 641729560 620398638 693859724 1111873161 822609682 472264211 534809596 856438654 650084712 912776978 67688441 1062160664 241115637 331818580 122331761 940298426 34341264 22894057 280687509 138636781 419157010 16 401224994 788329748 466358774 10317096...
result:
wrong answer 1st lines differ - expected: '16', found: '885791550 838209604 152948505 ...80687509 138636781 419157010 16'