//#include<stdio.h>
#include<bits/stdc++.h>
using namespace std;
#define ll long long
//#define f_(i,a,b) for (int i=a;i>=b;i--)
//#define f(i,a,b) for (int i=a;i<=b;i++)
int n;
string s[20005];
long long dem=0;
bool ss(int x,int y) {
if (s[x].size()>s[y].size()) return false;
if (s[x].size()<s[y].size()) return true;
for (int i=0;i<s[x].size();i++) {
if (s[x][i]>s[y][i]) return false;
if (s[x][i]<s[y][i]) return true;
}
return true;
}
void xot(int l,int r) {
if (l>=r) return ;
int pos;
pos=l;
string si;
for (int i=l;i<r;i++) {
if (ss(i,r)) {
si=s[i];
s[i]=s[pos];
s[pos]=si;
pos++;
}
}
si=s[r];
s[r]=s[pos];
s[pos]=si;
xot(l,pos-1);
xot(pos+1,r);
}
bool ktra(string substr, string str) {
int z[15],l,r;
for (int i=0;i<str.size();i++) {
if (i==0||i>r) {
l=r=i;
while (r-l<substr.size()&&str[r]==substr[r-l]) r++;
if (r-l==substr.size()) return true;
z[l]=r-l;
r--;
} else {
int k=i-l;
if (z[k]<=r-i) z[i]=z[k];
else {
l=i;
while (r-l<substr.size()&&str[r]==substr[r-l]) r++;
if (r-l==substr.size()) return true;
z[i]=r-l;
r--;
}
}
}
return false;
}
int main() {
// freopen("","r",stdin);
// freopen("","w",stdout);
scanf("%d", &n);
for (int i=1;i<=n;i++) {
cin>>s[i];
}
xot(1,n);
// for (int i=n;i>=1;i--) {
// cout<<s[i]<<" ";
// }
// cout<<"\n";
for (int i=n;i>1;i--) {
for (int j=i-1;j>=1;j--) {
if (i!=j) {
if (ktra(s[j],s[i])) {
dem++;
if (s[j].size()==s[i].size()) dem++;
// cout<<s[j]<<" "<<s[i]<<"\n";
}
// if (s[j].size()<=s[i].size())
// if (s[i].size()<=s[j].size()) if (ktra(s[i],s[j])) dem++;
}
}
}
printf("%lld", dem);
return 0;
}
Compilation message
lozinke.cpp: In function 'bool ss(int, int)':
lozinke.cpp:14:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i=0;i<s[x].size();i++) {
~^~~~~~~~~~~~
lozinke.cpp: In function 'bool ktra(std::__cxx11::string, std::__cxx11::string)':
lozinke.cpp:41:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i=0;i<str.size();i++) {
~^~~~~~~~~~~
lozinke.cpp:44:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while (r-l<substr.size()&&str[r]==substr[r-l]) r++;
~~~^~~~~~~~~~~~~~
lozinke.cpp:45:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if (r-l==substr.size()) return true;
~~~^~~~~~~~~~~~~~~
lozinke.cpp:53:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while (r-l<substr.size()&&str[r]==substr[r-l]) r++;
~~~^~~~~~~~~~~~~~
lozinke.cpp:54:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if (r-l==substr.size()) return true;
~~~^~~~~~~~~~~~~~~
lozinke.cpp: In function 'int main()':
lozinke.cpp:65:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &n);
~~~~~^~~~~~~~~~
lozinke.cpp: In function 'bool ktra(std::__cxx11::string, std::__cxx11::string)':
lozinke.cpp:50:15: warning: 'r' may be used uninitialized in this function [-Wmaybe-uninitialized]
if (z[k]<=r-i) z[i]=z[k];
~^~
lozinke.cpp:49:8: warning: 'l' may be used uninitialized in this function [-Wmaybe-uninitialized]
int k=i-l;
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
896 KB |
Output isn't correct |
| 2 |
Correct |
3 ms |
1024 KB |
Output is correct |
| 3 |
Incorrect |
3 ms |
1024 KB |
Output isn't correct |
| 4 |
Correct |
7 ms |
1024 KB |
Output is correct |
| 5 |
Incorrect |
26 ms |
1024 KB |
Output isn't correct |
| 6 |
Incorrect |
64 ms |
1024 KB |
Output isn't correct |
| 7 |
Incorrect |
86 ms |
896 KB |
Output isn't correct |
| 8 |
Correct |
87 ms |
1024 KB |
Output is correct |
| 9 |
Execution timed out |
1069 ms |
1024 KB |
Time limit exceeded |
| 10 |
Execution timed out |
1064 ms |
1024 KB |
Time limit exceeded |
| 11 |
Execution timed out |
1073 ms |
996 KB |
Time limit exceeded |
| 12 |
Execution timed out |
1078 ms |
896 KB |
Time limit exceeded |
| 13 |
Execution timed out |
1084 ms |
896 KB |
Time limit exceeded |
| 14 |
Execution timed out |
1074 ms |
896 KB |
Time limit exceeded |
| 15 |
Execution timed out |
1077 ms |
896 KB |
Time limit exceeded |
| 16 |
Execution timed out |
1075 ms |
896 KB |
Time limit exceeded |
| 17 |
Execution timed out |
1078 ms |
1312 KB |
Time limit exceeded |
| 18 |
Execution timed out |
1078 ms |
1704 KB |
Time limit exceeded |
| 19 |
Execution timed out |
1075 ms |
896 KB |
Time limit exceeded |
| 20 |
Execution timed out |
1076 ms |
1024 KB |
Time limit exceeded |
