Submission #98895

#	Time	Username	Problem	Language	Result	Execution time	Memory
98895		cfalas	Lozinke (COCI17_lozinke)	C++14	10 / 100	1068 ms	66560 KiB

lozinke

/*

  ______      _                _____ 
  |  ____/\   | |        /\    / ____|
  | |__ /  \  | |       /  \  | (___  
  |  __/ /\ \ | |      / /\ \  \___ \
  | | / ____ \| |____ / ____ \ ____) |
  |_|/_/    \_\______/_/    \_\_____/ 
                                            
                                            

*/
#include<bits/stdc++.h>
using namespace std;

#define ll long long
#define INF 1000000
#define MOD 1000000007

typedef pair<ll, ll> ii;
typedef vector<ll> vi;
typedef pair<ii, ll> iii;
typedef vector<ii> vii;

#define F first
#define S second

#define mp make_pair
#define endl '\n'
#define priority_queue pq

ll modpow(ll x, ll y){
    if(y==0)
        return 1;
    if(y==1)
        return x%MOD;

    ll z = modpow(x, y/2);
    z = (z*z)%MOD;

    if(y%2==1)
        z = z*x;
    return z%MOD;
}

int main(){
    int n;
    cin>>n;
    string a[n];
    string b = "";

    for(int i=0;i<n;i++){
        cin>>a[i];
        b+=a[i];
        b+="{";
    }
    map<ll, ll> hashes;
    vector<set<int> > ans;
    ans.assign(n+1, set<int>());

    for(int i=0;i<n;i++){
        ll hash = 0;
        for(int j=0;j<a[i].size();j++)
            hash = (hash*29) % MOD + (a[i][j] - 'a'+1);
        //cout<<hash<<endl;
        hashes[hash] ++;
    }
    for(int siz=1;siz<=10;siz++){
        //cout<<siz<<": -------------\n";
        int strcnt = 0;
        int cnt=0;
        ll currhash = 0;
        while(cnt<siz){
            if(b[cnt]=='{')
                strcnt++;
            currhash = currhash * 29 + (b[cnt] - 'a' + 1);
            cnt++;
        }
        for(int i=cnt;i<b.size();i++){
            //cout<<strcnt<<" "<<currhash<<endl;
            if(hashes[currhash]){
                
                ans[strcnt].insert(currhash);
            }
            currhash -= modpow(29, siz - 1)*(b[i-siz] - 'a' + 1);
            if(currhash<0){
                currhash+=MOD;
            }
            currhash*=29;
            currhash%=MOD;
            currhash += (b[i] - 'a' + 1);
            if(b[i]=='{')
                strcnt++;
        }

        if(hashes[currhash]){
            ans[strcnt].insert(currhash);
        }
    }
    int anss=0;
    for(int i=0;i<=n;i++){
        for(set<int>::iterator it=ans[i].begin();it!=ans[i].end();it++){
            anss += hashes[(*it)];
        }
    }
    cout<<anss-n<<endl;
    

}

Compilation message (stderr)

lozinke.cpp: In function 'int main()':
lozinke.cpp:63:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j=0;j<a[i].size();j++)
                     ~^~~~~~~~~~~~
lozinke.cpp:79:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i=cnt;i<b.size();i++){
                       ~^~~~~~~~~

• Subtask 1: 10 / 100