oj.uz

Submission #98939

# Submission time Handle Problem Language Result Execution time Memory
98939 2019-02-27T16:08:26 Z cfalas Lozinke (COCI17_lozinke) C++14
80 / 100
 257 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

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



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



*/
#include<bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
const int RANDOM = chrono::high_resolution_clock::now().time_since_epoch().count();
struct chash {
    const int RANDOM = (long long)(make_unique<char>().get()) ^ chrono::high_resolution_clock::now().time_since_epoch().count();
    static unsigned long long hash_f(unsigned long long x) {
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }
    static unsigned hash_combine(unsigned a, unsigned b) { return a * 31 + b; }
    int operator()(int x) const { return hash_f(x); }
};

#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+="{";
    }
    gp_hash_table<ll, int, chash> hashes;
    vector<unordered_set<ll> > ans;
    ans.assign(n+1, unordered_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(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(unordered_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:93:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(ll j=0;j<a[i].size();j++)
                    ~^~~~~~~~~~~~
lozinke.cpp:110:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i=cnt;i<b.size();i++){
                       ~^~~~~~~~~

Subtask #1
80.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 1 ms 512 KB Output is correct
3 Correct 3 ms 768 KB Output is correct
4 Correct 6 ms 1836 KB Output is correct
5 Correct 20 ms 5684 KB Output is correct
6 Correct 18 ms 5556 KB Output is correct
7 Correct 32 ms 10664 KB Output is correct
8 Correct 35 ms 9984 KB Output is correct
9 Correct 139 ms 26400 KB Output is correct
10 Correct 174 ms 38552 KB Output is correct
11 Correct 257 ms 48432 KB Output is correct
12 Runtime error 200 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
13 Correct 194 ms 25964 KB Output is correct
14 Runtime error 244 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
15 Runtime error 227 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
16 Correct 85 ms 5376 KB Output is correct
17 Correct 59 ms 3464 KB Output is correct
18 Correct 59 ms 5288 KB Output is correct
19 Runtime error 219 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
20 Correct 137 ms 16136 KB Output is correct