Submission #280454

#	Time	Username	Problem	Language	Result	Execution time	Memory
280454		Revo7	Lozinke (COCI17_lozinke)	C++14	85 / 100	145 ms	9264 KiB

lozinke

#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define left 2*i+1
#define righ 2*i+2
#define mid (l+r)/2
#define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);

using namespace std;
const ll maxn=2e4+100;
const ll mod=1e9+9;
const ll base=27;

ll n;
string s[maxn];
unordered_map<ll,ll>cnt;
ll ans=0;
unordered_map<ll,bool>vis;
void solve(ll i){
    vis.clear();
    for(ll l=0;l<s[i].size();l++){
        ll ha=0;
        for(ll r=l;r<s[i].size();r++){
            ha=ha*base%mod;
            ha=(ha+(s[i][r]-'a'+1))%mod;
            if(!vis[ha]){
                ans+=cnt[ha];
                vis[ha]=1;
            }
        }
    }
    ans--;
}
int main()
{
    //setIO("threesum");
    IOS
    cin>>n;
    for(ll i=0;i<n;i++)cin>>s[i];

    for(ll i=0;i<n;i++){
        ll ha=0;
        for(ll j=0;j<s[i].size();j++){
            ha=ha*base%mod;
            ha=(ha+(s[i][j]-'a'+1))%mod;
        }
        cnt[ha]++;
    }

    for(ll i=0;i<n;i++)solve(i);
    cout<<ans<<endl;
    return 0;
}

Compilation message (stderr)

lozinke.cpp: In function 'void solve(long long int)':
lozinke.cpp:21:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |     for(ll l=0;l<s[i].size();l++){
      |                ~^~~~~~~~~~~~
lozinke.cpp:23:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |         for(ll r=l;r<s[i].size();r++){
      |                    ~^~~~~~~~~~~~
lozinke.cpp: In function 'int main()':
lozinke.cpp:43:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |         for(ll j=0;j<s[i].size();j++){
      |                    ~^~~~~~~~~~~~

• Subtask 1: 85 / 100