oj.uz

Submission #98937

# Submission time Handle Problem Language Result Execution time Memory
98937 2019-02-27T15:55:34 Z cfalas Lozinke (COCI17_lozinke) C++14
85 / 100
 1000 ms 66560 KB 
/*
COCI 17-lozinke
Idea:   Hash each password
        Create a new string consisting of all passwords, joined by { (ie pass1{pass2)
        Make a sliding window for every size of string from 1 to 10
        Calculate hash of sliding window. If it matches any of the hashes from the passwords, add the connection to a set that have all connections, in order to avoid duplicates (ie pass1=aaa, pass2=aa, aa fits in aaa 2 times)
        Count answer
        Subtract n from the answer, since each password matches itself

Status  70%
        TLE in 4/20 testcases
        WA in 2/20 testcases

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



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

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

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

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

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

    for(ll i=0;i<n;i++){
        ll hash = 0;
        for(ll j=0;j<a[i].size();j++)
            hash = (hash*29) + (a[i][j] - 'a'+1);
        //cout<<hash<<endl;
        hashes[hash] ++;
    }
    for(ll siz=1;siz<=10;siz++){
        //cout<<siz<<": -------------\n";
        ll strcnt = 0;
        ll cnt=0;
        ll currhash = 0;
        while(cnt<siz){
            currhash = currhash * 29 + (b[cnt] - 'a' + 1);
            currhash = currhash;
            if(b[cnt]=='{')
                strcnt++;
            cnt++;
        }
        for(ll 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);
            currhash*=29;
            currhash += (b[i] - 'a' + 1);
            if(b[i]=='{')
                strcnt++;
        }

        if(hashes[currhash]){
            ans[strcnt].insert(currhash);
        }
    }
    ll anss=0;
    for(ll i=0;i<=n;i++){
        for(set<ll>::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:74:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(ll j=0;j<a[i].size();j++)
                    ~^~~~~~~~~~~~
lozinke.cpp:91:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(ll i=cnt;i<b.size();i++){
                      ~^~~~~~~~~

Subtask #1
85.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Correct 4 ms 512 KB Output is correct
4 Correct 7 ms 1280 KB Output is correct
5 Correct 20 ms 3072 KB Output is correct
6 Correct 29 ms 3612 KB Output is correct
7 Correct 51 ms 6392 KB Output is correct
8 Correct 77 ms 7384 KB Output is correct
9 Correct 340 ms 23432 KB Output is correct
10 Correct 493 ms 31592 KB Output is correct
11 Correct 577 ms 37880 KB Output is correct
12 Correct 907 ms 55048 KB Output is correct
13 Correct 518 ms 22068 KB Output is correct
14 Runtime error 744 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
15 Execution timed out 1070 ms 66312 KB Time limit exceeded
16 Correct 213 ms 4872 KB Output is correct
17 Correct 49 ms 3208 KB Output is correct
18 Correct 56 ms 5000 KB Output is correct
19 Execution timed out 1038 ms 53888 KB Time limit exceeded
20 Correct 249 ms 16136 KB Output is correct