Submission #98896

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
98896	2019-02-27T09:23:22 Z	cfalas	Lozinke (COCI17_lozinke)	C++14	70 / 100	1000 ms	62216 KB

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);
            currhash = currhash%MOD;
            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);
            while(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

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:80:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i=cnt;i<b.size();i++){
                       ~^~~~~~~~~

Subtask #1

70.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	384 KB	Output is correct
2	Correct	3 ms	384 KB	Output is correct
3	Correct	4 ms	640 KB	Output is correct
4	Correct	8 ms	1280 KB	Output is correct
5	Correct	23 ms	3200 KB	Output is correct
6	Correct	41 ms	3448 KB	Output is correct
7	Correct	78 ms	6476 KB	Output is correct
8	Correct	92 ms	7536 KB	Output is correct
9	Correct	435 ms	23552 KB	Output is correct
10	Incorrect	800 ms	31520 KB	Output isn't correct
11	Incorrect	783 ms	37752 KB	Output isn't correct
12	Execution timed out	1056 ms	47408 KB	Time limit exceeded
13	Correct	660 ms	21988 KB	Output is correct
14	Execution timed out	1088 ms	62216 KB	Time limit exceeded
15	Execution timed out	1075 ms	48632 KB	Time limit exceeded
16	Correct	220 ms	4744 KB	Output is correct
17	Correct	69 ms	3076 KB	Output is correct
18	Correct	74 ms	4872 KB	Output is correct
19	Execution timed out	1062 ms	47240 KB	Time limit exceeded
20	Correct	289 ms	15860 KB	Output is correct