oj.uz

Submission #584221

# Submission time Handle Problem Language Result Execution time Memory
584221 2022-06-27T04:28:19 Z AGE Trener (COCI20_trener) C++14
55 / 110
 569 ms 524288 KB 
#include<bits/stdc++.h>
#define F first
#define S second
#define pb push_back
#define ll long long 
using namespace std;
const int N=1e6,M=1502,mod=1e9+7,p=31;
int a[12]={31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
string s[55][M];
int hashh[55][M][3],ans[55][M];
vector<int>adj[55][M];

int mult(ll x,ll y){
    return ((x%mod)*(y%mod))%mod;
}

int minuss(ll x,ll y){
    return ((x%mod)-(y%mod)+mod)%mod;
}

int summ(ll x,ll y){
    return ((x%mod)+(y%mod))%mod;
}

void compute_hash(int i,int j){

    int hash_val=0;
    int p_pow=1;
    hash_val=s[i][j][0]-'a'+1;
    for(int k=1;k<s[i][j].size()-1;k++){

        p_pow=mult(p_pow,p);
        hash_val=summ(hash_val,mult(s[i][j][k]-'a'+1,p_pow));

    }

    hashh[i][j][0]=hash_val;
    hash_val=0;
    p_pow=1;

    for(int k=1;k<s[i][j].size();k++){

        hash_val=summ(hash_val,mult(s[i][j][k]-'a'+1,p_pow));
        p_pow=mult(p_pow,p);

    }

    hashh[i][j][1]=hash_val;

    hash_val=s[i][j][0]-'a'+1;
    p_pow=1;
    for(int k=1;k<s[i][j].size();k++){

        p_pow=mult(p_pow,p);
        hash_val=summ(hash_val,mult(s[i][j][k]-'a'+1,p_pow));

    }

    hashh[i][j][2]=hash_val;

}
main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    int n,m;
    cin>>n>>m;

    for(int i=0;i<n;i++)
        for(int j=0;j<m;j++)
            cin>>s[i][j];

    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++)
            compute_hash(i,j);
    }

    for(int i=0;i<n-1;i++){
        for(int j=0;j<m;j++){
            for(int k=0;k<m;k++){

                if(hashh[i][j][2]==hashh[i+1][k][0]||hashh[i][j][2]==hashh[i+1][k][1])
                    adj[i][j].pb(k);

            }
        }
    }

    for(int j=0;j<m;j++)
        ans[n-1][j]=1;

    for(int i=n-2;i>=0;i--){
        for(int j=0;j<m;j++){
            for(auto x:adj[i][j]){
                ans[i][j]=summ(ans[i][j],ans[i+1][x]);
            }
        }
    }


    int sum=0;

    for(int i=0;i<m;i++)
        sum=summ(sum,ans[0][i]);

    cout<<sum<<endl;


    return 0;
}

Compilation message

trener.cpp: In function 'void compute_hash(int, int)':
trener.cpp:30:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |     for(int k=1;k<s[i][j].size()-1;k++){
      |                 ~^~~~~~~~~~~~~~~~~
trener.cpp:41:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |     for(int k=1;k<s[i][j].size();k++){
      |                 ~^~~~~~~~~~~~~~~
trener.cpp:52:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |     for(int k=1;k<s[i][j].size();k++){
      |                 ~^~~~~~~~~~~~~~~
trener.cpp: At global scope:
trener.cpp:62:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   62 | main()
      | ^~~~

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4820 KB Output is correct
2 Correct 2 ms 4820 KB Output is correct
3 Correct 3 ms 4884 KB Output is correct
4 Correct 3 ms 4820 KB Output is correct

Subtask #2
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 5488 KB Output is correct
2 Correct 9 ms 5612 KB Output is correct
3 Correct 9 ms 5588 KB Output is correct
4 Correct 15 ms 8020 KB Output is correct
5 Correct 10 ms 5652 KB Output is correct
6 Correct 9 ms 5716 KB Output is correct
7 Correct 15 ms 7956 KB Output is correct

Subtask #3
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4820 KB Output is correct
2 Correct 2 ms 4820 KB Output is correct
3 Correct 3 ms 4884 KB Output is correct
4 Correct 3 ms 4820 KB Output is correct
5 Correct 8 ms 5488 KB Output is correct
6 Correct 9 ms 5612 KB Output is correct
7 Correct 9 ms 5588 KB Output is correct
8 Correct 15 ms 8020 KB Output is correct
9 Correct 10 ms 5652 KB Output is correct
10 Correct 9 ms 5716 KB Output is correct
11 Correct 15 ms 7956 KB Output is correct
12 Correct 373 ms 11188 KB Output is correct
13 Correct 370 ms 11008 KB Output is correct
14 Correct 387 ms 11060 KB Output is correct
15 Correct 373 ms 11036 KB Output is correct
16 Runtime error 569 ms 524288 KB Execution killed with signal 9
17 Halted 0 ms 0 KB -