oj.uz

Submission #223231

# Submission time Handle Problem Language Result Execution time Memory
223231 2020-04-15T05:47:50 Z dantoh000 Trener (COCI20_trener) C++14
0 / 110
 15 ms 1408 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1000000007;
int n,k;
ll KEY = 93993939;
ll f[55];
int v[26];
unordered_map<ll,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;
}
int dp[2][1505];
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++) {
        dp[n&1][i] = 1;
        ct[a[n][i]]++;
    }
    for (int i = n-1; i >= 1; i--){
        for (int j = 1; j <= k; j++){
            assert(ct[a[i][j]] == 0);
            dp[i&1][j] = 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);
                dp[i&1][j] += ct[(a[i][j]*KEY + v[T])%mod];
                if ((a[i][j] + v[T]*f[i])%mod != (a[i][j]*KEY + v[T])%mod) dp[i&1][j] += ct[(a[i][j] + v[T]*f[i])%mod];
            }
            ct[a[i][j]] = dp[i&1][j];
        }
    }
    int sum = 0;
    for (int i = 1; i <= k; i++) {
        sum += dp[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:33: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 384 KB Output is correct
2 Runtime error 6 ms 640 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -

Subtask #2
0 / 33.0

# Verdict Execution time Memory Grader output
1 Runtime error 15 ms 1408 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Runtime error 6 ms 640 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -