Submission #584221

#	Time	Username	Problem	Language	Result	Execution time	Memory
584221		AGE	Trener (COCI20_trener)	C++14	55 / 110	569 ms	524288 KiB

trener

#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 (stderr)

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 / 22
• Subtask 2: 33 / 33
• Subtask 3: 0 / 55