| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1078165 |
2024-08-27T13:27:43 Z |
ntnq |
Lozinke (COCI17_lozinke) |
C++17 |
|
1000 ms |
13916 KB |
#include <bits/stdc++.h>
#define quick ios_base :: sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define file(name) freopen(name".inp","r",stdin); freopen(name".out","w",stdout);
#define endl '\n'
#define N 100000
#define pii pair <int,int>
using namespace std;
const int INF = 1e9;
const int base=1001;
const int mod=1e10+7;
const int MOD=1e10+3;
vector <long long> sum[N],SUM[N];
vector <long long> h,H;
int n;
string st[N];
long long get(int u,int v, vector <long long> &s,vector <long long> hh,long long mo)
{
long long mm=mo*mo;
return (s[v]-s[u-1]*h[v-u+1]+mm)%mo;
}
bool cmp(string a,string b)
{
return a.size()<b.size();
}
int main()
{
quick;
cin>>n;
for (int i=1;i<=n;i++) cin>>st[i];
sort(st+1,st+n+1,cmp);
for (int i=1;i<=n;i++)
{
string s;
s=st[i];
int m=s.size();
s=' '+s;
sum[i].push_back(0);
SUM[i].push_back(0);
for (int j=1;j<=m;j++) sum[i].push_back((sum[i][j-1]*base+s[j])%mod);
for (int j=1;j<=m;j++) SUM[i].push_back((SUM[i][j-1]*base+s[j])%MOD);
}
h.push_back(1);
H.push_back(1);
for (int i=1;i<=100;i++) h.push_back(h[i-1]*base%mod);
for (int i=1;i<=100;i++) H.push_back(H[i-1]*base%mod);
long long ans=0;
for (int i=1;i<n;i++)
{
long long a=get(1,st[i].size(),sum[i],h,mod),b=get(1,st[i].size(),SUM[i],H,MOD);
// cout<<a<<' '<<b<<endl;
for (int j=i+1;j<=n;j++)
for (int k=1;k<=st[j].size()-st[i].size()+1;k++)
{
// cout<<j<<' '<<get(k,k+st[i].size()-1,sum[j],h,mod)<<' '<<get(k,k+st[i].size()-1,SUM[j],H,MOD)<<endl;
if (a==get(k,k+st[i].size()-1,sum[j],h,mod) && b==get(k,k+st[i].size()-1,SUM[j],H,MOD))
{
ans++;
if (st[i]==st[j]) ans++;
break;
}
}
}
cout<<ans;
return 0;
}
Compilation message
lozinke.cpp:10:19: warning: overflow in conversion from 'double' to 'int' changes value from '1.0000000007e+10' to '2147483647' [-Woverflow]
10 | const int mod=1e10+7;
| ~~~~^~
lozinke.cpp:11:19: warning: overflow in conversion from 'double' to 'int' changes value from '1.0000000003e+10' to '2147483647' [-Woverflow]
11 | const int MOD=1e10+3;
| ~~~~^~
lozinke.cpp: In function 'int main()':
lozinke.cpp:53:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
53 | for (int k=1;k<=st[j].size()-st[i].size()+1;k++)
| ~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
8284 KB |
Output is correct |
| 2 |
Correct |
4 ms |
8284 KB |
Output is correct |
| 3 |
Correct |
6 ms |
8284 KB |
Output is correct |
| 4 |
Correct |
12 ms |
8348 KB |
Output is correct |
| 5 |
Correct |
68 ms |
8284 KB |
Output is correct |
| 6 |
Correct |
129 ms |
8592 KB |
Output is correct |
| 7 |
Correct |
185 ms |
8540 KB |
Output is correct |
| 8 |
Correct |
133 ms |
8796 KB |
Output is correct |
| 9 |
Execution timed out |
1030 ms |
9820 KB |
Time limit exceeded |
| 10 |
Execution timed out |
1065 ms |
10344 KB |
Time limit exceeded |
| 11 |
Execution timed out |
1034 ms |
10840 KB |
Time limit exceeded |
| 12 |
Execution timed out |
1047 ms |
11956 KB |
Time limit exceeded |
| 13 |
Execution timed out |
1064 ms |
13068 KB |
Time limit exceeded |
| 14 |
Execution timed out |
1053 ms |
11680 KB |
Time limit exceeded |
| 15 |
Execution timed out |
1071 ms |
12636 KB |
Time limit exceeded |
| 16 |
Execution timed out |
1042 ms |
13916 KB |
Time limit exceeded |
| 17 |
Execution timed out |
1063 ms |
13916 KB |
Time limit exceeded |
| 18 |
Execution timed out |
1031 ms |
13064 KB |
Time limit exceeded |
| 19 |
Execution timed out |
1027 ms |
12120 KB |
Time limit exceeded |
| 20 |
Execution timed out |
1039 ms |
12120 KB |
Time limit exceeded |
