Submission #98897

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
98897	2019-02-27T09:28:58 Z	cfalas	Lozinke (COCI17_lozinke)	C++14	70 / 100	1000 ms	66560 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);
            if(currhash<0){
                currhash += ((-currhash) / MOD + 1)*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	2 ms	384 KB	Output is correct
3	Correct	4 ms	512 KB	Output is correct
4	Correct	9 ms	1280 KB	Output is correct
5	Correct	26 ms	3200 KB	Output is correct
6	Correct	36 ms	3580 KB	Output is correct
7	Correct	62 ms	6392 KB	Output is correct
8	Correct	88 ms	7464 KB	Output is correct
9	Correct	404 ms	23484 KB	Output is correct
10	Incorrect	769 ms	31676 KB	Output isn't correct
11	Incorrect	782 ms	37852 KB	Output isn't correct
12	Execution timed out	1076 ms	49860 KB	Time limit exceeded
13	Correct	527 ms	21984 KB	Output is correct
14	Execution timed out	1060 ms	66560 KB	Time limit exceeded
15	Execution timed out	1066 ms	48376 KB	Time limit exceeded
16	Correct	188 ms	4616 KB	Output is correct
17	Correct	77 ms	3120 KB	Output is correct
18	Correct	80 ms	4920 KB	Output is correct
19	Execution timed out	1037 ms	45336 KB	Time limit exceeded
20	Correct	295 ms	15884 KB	Output is correct