QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#723551 | #9406. Triangle | AllenJYL | WA | 18ms | 42864kb | C++14 | 5.0kb | 2024-11-07 22:51:14 | 2024-11-07 22:51:14 |
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;
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<<" ";
}
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: 100
Accepted
time: 18ms
memory: 42780kb
input:
3 6 cbaa cb cb cbaa ba ba 3 sdcpc sd cpc 1 ccpc
output:
16 0 0
result:
ok 3 lines
Test #2:
score: -100
Wrong Answer
time: 15ms
memory: 42864kb
input:
14 1 lfpbavjsm 2 pdtlkfwn mbd 3 dvqksg dvqksg uhbhpyhj 4 ombwb ombwb ombwb ombwb 5 oztclz oztclz oztclz oztclz kul 6 vco vco vco dtktsqtinm vco vco 7 tb tb kowbsu ygkfphcij tb uvei tb 8 vxxtxssht abnsxbf bydaae bydaae udalyvmcef bydaae bydaae bydaae 9 aaze zvyonw qjfv mmhkef qjfv qjfv qjfv mmhkef qj...
output:
0 0 0 4 10 20 10 20 41 14 63 74 18 100 dpa mkstfb mkstfb mkstfb hzpgohgb jsbpabob fqyqqgyppb yhgbjshc lpfyetc lpfyetc lpfyetc lpfyetc lpfyetc lpfyetc lpfyetc lpfyetc lpfyetc lpfyetc lpfyetc lpfyetc lpfyetc tyc tyc tyc tyc tyc tyc tyc tyc tyc tyc tyc tyc tyc tyc tyc tyc tyc tyc tyc tyc tyc tyc cuujai...
result:
wrong answer 14th lines differ - expected: '11081', found: '100'