QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#723556#9406. TriangleAllenJYLWA 19ms42884kbC++145.0kb2024-11-07 22:53:282024-11-07 22:53:28

Judging History

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

  • [2024-11-07 22:53:28]
  • 评测
  • 测评结果:WA
  • 用时:19ms
  • 内存:42884kb
  • [2024-11-07 22:53:28]
  • 提交

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});
    }
    if(n!=14) 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: 11ms
memory: 42756kb

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: 19ms
memory: 42884kb

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'