#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define ins insert
#define BIT(x,i) ((1LL<<i)&x)
#define all(x) x.begin(),x.end()
#define pll pair<ll,ll>
#define pii pair<int,int>
#define ll long long
#define ull unsigned long long
#define name "PASS"
const int mod=int(1e9+7);
int pi[8]={0,0,1,-1,1,1,-1,-1};
int pj[8]={-1,1,0,0,1,-1,1,-1};
template<class A,class B> inline void add(A &a,B b) { a+=b;while (a>=mod) a-=mod;}
template<class A,class B> inline void sub(A &a,B b) { a-=b;while (a>=mod) a-=mod;while (a<0) a+=mod;}
template<class A,class B> bool _max(A &a,B b) {if (a<b) return a=b,1; return 0;}
template<class A,class B> bool _min(A &a,B b) {if (a>b) return a=b,1; return 0;}
int n,res;
const int nmax=20010;
string a[nmax];
namespace Subtask1{
bool check(string &s,string &t){
int d=0;
for(auto chr:t) d+=chr==s[d];
return d==s.size();
}
void solve(){
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
if (i!=j) res+=check(a[i],a[j]);
cout<<res;
}
}
namespace Subtask2{
void solve(){
unordered_map<string,int> dp;
for(int i=1;i<=n;i++) dp[a[i]]++;
for(int i=1;i<=n;i++){
dp[a[i]]--;
unordered_map<string,bool> uwu;
for(int mask=1;mask<(1<<a[i].size());mask++)
{
string tmp="";
for(int j=0;j<a[i].size();j++)
if (BIT(mask,j)) tmp+=a[i][j];
res+=dp[tmp]*(uwu[tmp]==0);
uwu[tmp]=1;
}
dp[a[i]]++;
}
cout<<res;
}
}
int main()
{
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
if (fopen(name".INP","r"))
{
freopen(name".INP","r",stdin);
freopen(name".OUT","w+",stdout);
}
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
if (n<=2000) return Subtask1::solve(),0;
Subtask2::solve();
}
Compilation message
lozinke.cpp: In function 'bool Subtask1::check(std::string&, std::string&)':
lozinke.cpp:28:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
28 | return d==s.size();
| ~^~~~~~~~~~
lozinke.cpp: In function 'void Subtask2::solve()':
lozinke.cpp:47:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
47 | for(int j=0;j<a[i].size();j++)
| ~^~~~~~~~~~~~
lozinke.cpp: In function 'int main()':
lozinke.cpp:62:20: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
62 | freopen(name".INP","r",stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
lozinke.cpp:63:20: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
63 | freopen(name".OUT","w+",stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
856 KB |
Output isn't correct |
| 2 |
Incorrect |
1 ms |
860 KB |
Output isn't correct |
| 3 |
Incorrect |
1 ms |
860 KB |
Output isn't correct |
| 4 |
Incorrect |
2 ms |
860 KB |
Output isn't correct |
| 5 |
Incorrect |
8 ms |
940 KB |
Output isn't correct |
| 6 |
Incorrect |
20 ms |
860 KB |
Output isn't correct |
| 7 |
Incorrect |
27 ms |
860 KB |
Output isn't correct |
| 8 |
Incorrect |
36 ms |
860 KB |
Output isn't correct |
| 9 |
Incorrect |
297 ms |
5320 KB |
Output isn't correct |
| 10 |
Execution timed out |
1014 ms |
65536 KB |
Time limit exceeded |
| 11 |
Incorrect |
529 ms |
12224 KB |
Output isn't correct |
| 12 |
Runtime error |
594 ms |
65536 KB |
Execution killed with signal 9 |
| 13 |
Incorrect |
885 ms |
3528 KB |
Output isn't correct |
| 14 |
Runtime error |
500 ms |
65536 KB |
Execution killed with signal 9 |
| 15 |
Runtime error |
543 ms |
65536 KB |
Execution killed with signal 9 |
| 16 |
Execution timed out |
1010 ms |
1624 KB |
Time limit exceeded |
| 17 |
Execution timed out |
1067 ms |
1116 KB |
Time limit exceeded |
| 18 |
Correct |
609 ms |
1116 KB |
Output is correct |
| 19 |
Execution timed out |
1049 ms |
49416 KB |
Time limit exceeded |
| 20 |
Incorrect |
508 ms |
1368 KB |
Output isn't correct |
