oj.uz

Submission #98943

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

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>
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<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:95:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(ll j=0;j<a[i].size();j++)
                    ~^~~~~~~~~~~~
lozinke.cpp:112: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 3 ms 512 KB Output is correct
3 Correct 3 ms 768 KB Output is correct
4 Correct 4 ms 1708 KB Output is correct
5 Correct 14 ms 5684 KB Output is correct
6 Correct 20 ms 5556 KB Output is correct
7 Correct 36 ms 10664 KB Output is correct
8 Correct 31 ms 9992 KB Output is correct
9 Correct 124 ms 26732 KB Output is correct
10 Correct 151 ms 38412 KB Output is correct
11 Correct 234 ms 48908 KB Output is correct
12 Runtime error 232 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
13 Correct 181 ms 25836 KB Output is correct
14 Runtime error 271 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
15 Runtime error 199 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
16 Correct 77 ms 4712 KB Output is correct
17 Correct 50 ms 3052 KB Output is correct
18 Correct 60 ms 4872 KB Output is correct
19 Runtime error 237 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
20 Correct 141 ms 16832 KB Output is correct