oj.uz

Submission #223232

# Submission time Handle Problem Language Result Execution time Memory
223232 2020-04-15T05:50:28 Z dantoh000 Trener (COCI20_trener) C++14
0 / 110
 92 ms 12600 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1000000007;
int n,k;
ll KEY = 9999997;
ll f[55];
int v[26];
unordered_map<int,int> ct;
ll HASH(string s){
    ll res = 0;
    for (int i = 0; i < s.size(); i++){
        res = ((res*KEY) + v[s[i]-'a'])%mod;
    }
    return res;
}
ll a[55][1505];
bool can(ll a, ll b, int len){
    for (int i = 0; i < 26; i++){
        if ((a*KEY + v[i])%mod == b || (a + i*f[len])%mod == b) return true;
    }
    return false;
}
int main(){
    iota(v,v+26,1);
    random_shuffle(v,v+26);
    //for (int i = 0; i < 26; i++) printf("%d ",v[i]);
    f[0] = 1;
    for (int i = 1; i <= 50; i++){
        f[i] = (f[i-1]*KEY)%mod;
    }
    scanf("%d%d",&n,&k);
    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= k; j++){
            string s;
            cin >> s;
            a[i][j] = HASH(s);
            //cout << s << " " << a[i][j] << endl;
        }
    }
    for (int i = 1; i <= k; i++) {
        ct[a[n][i]]++;
    }
    for (int i = n-1; i >= 1; i--){
        for (int j = 1; j <= k; j++){
            ll res = 0;
            for (int T = 0; T < 26; T++){
                //printf("%lld -> %lld %lld\n",a[i][j],(a[i][j]*KEY + v[T])%mod,(a[i][j] + v[T]*f[i])%mod);
                res += ct[(a[i][j]*KEY + v[T])%mod];
                if ((a[i][j] + v[T]*f[i])%mod != (a[i][j]*KEY + v[T])%mod) res += ct[(a[i][j] + v[T]*f[i])%mod];
            }
            ct[a[i][j]] = res%mod;
        }
    }
    int sum = 0;
    for (int i = 1; i <= k; i++) {
        sum += ct[a[1][i]];
        sum %= mod;
    }
    printf("%d",sum);
}

Compilation message

trener.cpp: In function 'll HASH(std::__cxx11::string)':
trener.cpp:12:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < s.size(); i++){
                     ~~^~~~~~~~~~
trener.cpp: In function 'int main()':
trener.cpp:32:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d",&n,&k);
     ~~~~~^~~~~~~~~~~~~~

Subtask #1
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 512 KB Output is correct
2 Correct 5 ms 512 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Incorrect 5 ms 384 KB Output isn't correct

Subtask #2
0 / 33.0

# Verdict Execution time Memory Grader output
1 Incorrect 92 ms 12600 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 512 KB Output is correct
2 Correct 5 ms 512 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Incorrect 5 ms 384 KB Output isn't correct