oj.uz

Submission #98945

# Submission time Handle Problem Language Result Execution time Memory
98945 2019-02-27T16:27:32 Z cfalas Lozinke (COCI17_lozinke) C++14
100 / 100
 919 ms 52692 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

UPDATE: 85%
        Solved WAs by completely removing the MOD in order to avoid collisions

UPDATE2:    80%
            Replaced map with policy based data structures to decrease constant times, but this increased memory usage, so I lose the testcases from

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



*/
#include<bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>

#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+="{";
    }
    unordered_map<ll, int> hashes;
    vector<set<ll> > ans;
    ans.assign(n+1, set<ll>());

    ll hash = 0;
    for(ll i=0;i<n;i++){
        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(int siz=1;siz<=10;siz++){
        //cout<<siz<<": -------------\n";
        int strcnt = 0;
        int cnt=0;
        ll currhash = 0;
        while(cnt<siz){
            currhash = currhash * 29 + (b[cnt] - 'a' + 1);
            currhash = currhash;
            if(b[cnt]=='{')
                strcnt++;
            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);
            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:82:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(ll j=0;j<a[i].size();j++)
                    ~^~~~~~~~~~~~
lozinke.cpp:99:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i=cnt;i<b.size();i++){
                       ~^~~~~~~~~

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 356 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 3 ms 512 KB Output is correct
4 Correct 8 ms 1152 KB Output is correct
5 Correct 13 ms 2480 KB Output is correct
6 Correct 20 ms 2700 KB Output is correct
7 Correct 52 ms 4872 KB Output is correct
8 Correct 64 ms 6508 KB Output is correct
9 Correct 279 ms 20392 KB Output is correct
10 Correct 479 ms 26252 KB Output is correct
11 Correct 483 ms 28684 KB Output is correct
12 Correct 680 ms 35840 KB Output is correct
13 Correct 294 ms 19660 KB Output is correct
14 Correct 715 ms 46696 KB Output is correct
15 Correct 919 ms 52692 KB Output is correct
16 Correct 92 ms 4488 KB Output is correct
17 Correct 66 ms 3000 KB Output is correct
18 Correct 96 ms 4872 KB Output is correct
19 Correct 578 ms 37372 KB Output is correct
20 Correct 139 ms 15400 KB Output is correct