oj.uz

Submission #98895

# Submission time Handle Problem Language Result Execution time Memory
98895 2019-02-27T09:19:30 Z cfalas Lozinke (COCI17_lozinke) C++14
10 / 100
 1000 ms 66560 KB 
/*

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

*/
#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

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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 384 KB Output isn't correct
2 Correct 3 ms 384 KB Output is correct
3 Incorrect 0 ms 640 KB Output isn't correct
4 Correct 7 ms 1252 KB Output is correct
5 Incorrect 22 ms 3200 KB Output isn't correct
6 Incorrect 39 ms 3704 KB Output isn't correct
7 Incorrect 63 ms 6524 KB Output isn't correct
8 Incorrect 79 ms 7416 KB Output isn't correct
9 Incorrect 446 ms 24212 KB Output isn't correct
10 Incorrect 724 ms 31736 KB Output isn't correct
11 Incorrect 746 ms 38456 KB Output isn't correct
12 Execution timed out 1061 ms 55076 KB Time limit exceeded
13 Incorrect 572 ms 23000 KB Output isn't correct
14 Execution timed out 1032 ms 66560 KB Time limit exceeded
15 Execution timed out 1068 ms 54568 KB Time limit exceeded
16 Incorrect 193 ms 3464 KB Output isn't correct
17 Incorrect 75 ms 2344 KB Output isn't correct
18 Incorrect 70 ms 4076 KB Output isn't correct
19 Execution timed out 1068 ms 54152 KB Time limit exceeded
20 Incorrect 210 ms 15112 KB Output isn't correct